Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # modulo fft
- from math import *
- def fft(m, f=[]): #genera fft
- result = []
- n=2<<(m-1)
- nesp=0.5
- for k in range(1,m+1):
- d=n/(2<<(k-1)
- nesp=nesp*2
- s=0
- for i in range(1,nesp+1):
- r=s
- z1=r>>(m-k)
- z=0
- for q in range(k):
- z=(((z1>>q) & 01) | (z<<1)
- w=2*pi*z/(2<<(k-1))
- e=cos(w)-sin(w)j
- for l in range (d):
- r=l+s
- r1=r+d
- t=e*f[r1]
- f[r1]=f[r]-t
- f[r]=f[r]+t
- s=s+2*d
- #bitReversal(n, m, f=[])
- for x in range(1, n-1):
- y=0
- for i in range(m):
- y=(((x>>i) & 01) | (y<<1))
- if x<y :
- t=f[x]
- f[x]=f[y]
- f[y]=t
- #Ampiezze fasi
- nmezzi=n/2
- for i in range(n):
- f[i]=f[i]/nmezzi
- A[0]=f[0].real
- phi[0]=0
- for k in range(1, nmezzi+1):
- A[k]=sqrt(f[k].real*f[k].real+f[k].imag*f[k].imag])
- result.append(A[k])
- if f[k].real == 0:
- if f[k].imag>0:
- phi[k]=pi
- if f[k].imag==0:
- phi[k]=0
- if f[k].imag<0:
- phi[k]=2*pi-pi/2
- if f[k].real>0:
- if f[k]>=0:
- phi[k]=atan(f[k].imag, f[k].real)
- if f[k]<0:
- phi[k]=2*pi + atan(f[k].imag, f[k].real)
- if f[k].real<0:
- phi[k]=atan(f[k].imag, f[k].real)
- return result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement