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
comments (?)
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
https://ideone.com/KpcCVG
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!