fork(5) download
  1. from math import pi, e, cos, sin
  2.  
  3. def FFT(array, n, inverse):
  4. if n == 1:
  5. return
  6. theta = (pi*2) / n
  7. if inverse:
  8. Wn = pow(e, (-2*pi*1j)/ n)
  9. else:
  10. Wn = pow(e, (2*pi*1j)/ n)
  11.  
  12. W = 1
  13.  
  14. a = [0]* (n/2)
  15. b = [0]* (n/2)
  16.  
  17. for i in xrange(n):
  18. if (i & 1):
  19. b[i/2] = array[i]
  20. else:
  21. a[i/2] = array[i]
  22.  
  23. FFT(a, n/2, inverse)
  24. FFT(b, n/2, inverse)
  25.  
  26. for i in xrange(n/2):
  27. array[i] = a[i] + W*b[i]
  28. array[i+n/2] = a[i] - W*b[i]
  29. W *= Wn
  30.  
  31. a = [1,1,2,0,0,0,0,0]
  32. b = [1,3,0,0,0,0,0,0]
  33.  
  34. FFT(a, 8, 0)
  35. FFT(b, 8, 0)
  36.  
  37. res = []
  38. #print a
  39. #print b
  40. for i in xrange(8):
  41. res.append(a[i]*b[i])
  42. FFT(res, 8, 1)
  43. for i in xrange(8):
  44. res[i] /= 8
  45.  
  46. for i in res:
  47. print i.real
  48.  
Success #stdin #stdout 0.01s 9016KB
stdin
Standard input is empty
stdout
1.0
4.0
5.0
6.0
1.66533453694e-16
4.4408920985e-16
0.0
4.4408920985e-16