Aqib12

Untitled

Dec 2nd, 2020
587
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from cmath import exp, pi
  2.  
  3.  
  4. def fft(x):
  5.     N = len(x)
  6.     if N <= 1: return x
  7.     even = fft(x[0::2])
  8.     odd = fft(x[1::2])
  9.     T = [exp(-2j * pi * k / N) * odd[k] for k in range(N // 2)]
  10.     return [even[k] + T[k] for k in range(N // 2)] + \
  11.            [even[k] - T[k] for k in range(N // 2)]
  12.  
  13.  
RAW Paste Data