python實現fft

① 計算機快速計算2^N是如何實現的

計算乘方是有快速演算法的，並不是一個一個蠻力乘上去的。比如想算2^10000，計算機先算2^5000，再算一次平方，即兩個數的乘法。而物局為了計算2^5000，計算機會先算2^2500再算一次平方。這個演算法叫快速冪演算法罩茄讓，對於2^N的計算，如果認為每次乘法的時間復雜度是O(1)的話，那整體的時間復雜度只有O(logN)級別。
一般來說，為了實現快速冪演算法，首先把指數做二進製表示，比如你要算A的23次方，可以把23分解為16+4+2+1。然後計算B=A^2，C=B^2=A^4，D=(C^2)^2=A^16。最終結果為ABCD相乘。
但這里乘法的復雜度並不是O(1)，因為它是無限精度的，也就是所謂的大數乘法。大數乘法也有很多演算法，最樸素的，類似手算的方法，復雜度是O(N^2)，其他一些方法有分治法，復雜度O(N^1.58)，FFT方法，復雜度O(N logN loglogN)等。快速冪的O(logN)次大數乘法中，最復雜的只有最後一次，也就是2^5000的那次，前面的復雜度幾何級數衰減，所以整體復雜度也就是最後一次計算的復雜度。如果你用FFT方法的話，復雜度也就是比線性多了一點點，一般計算機上隨便算算就出來了。
CPU沒有全速運行是因為這納亂個程序只用了1個核心在做計算，而你顯示的是總的使用率，所以大概會保持在四分之一的水平。
是否用到了移位操作涉及Python大數運算的具體設計，我不是很懂就不多講了。但原理上講也是很有可能的，如果用比特串存儲大數的話，那麼計算2^N只需要在數組的第N位設置一個1，其餘設置為0即可，那麼轉換到十進制是這段代碼中最消耗計算量的部分。

② 如何用Python編寫一個素數環

代碼：
n = int(input("請輸入最大數n："))
lists = [[1]]#多個素數環
surplusnum = list(range(1,n+1)) #剩餘的數
def sumisprime(x, y):
#x與y之和是否是素數
isprime=True#是否是素數
s = x + y#和
for i in range(2, int(s**0.5)+1):
#素數判定法：從2開始直到此數的開方內的整數都不能被該數整除，則此數為素數
if s%i == 0:#能被整除
isprime = False#不是素數
break#跳出循環
return isprime#返回後否是素數（是：True，否：False）
changelast=lambda listx,addvalue:listx[0:-1]+[addvalue]#改變列表末尾的函數
while len(lists[0] if len(lists) else [0]*n) < n:#當素數環長度小於最大數時
n2 = len(lists[0]) #n2為判定，理論當前列表長度最大值
for listn in lists:#遍歷各個可能的素數環
surplusnum=list(range(1,n+1))#默認值
for j in listn:#遍歷當前列表的數
surplusnum.remove(j)#剩餘的數中刪除此數
for i in surplusnum:#遍歷剩餘的數
if sumisprime(listn[n2-1], i):#最後一個數與它的和是素數
if len(listn) == n2:#如果現在這個列表是沒有被添加過的
listn.append(i)#增加在這個列表
else:#如果該列表已經被添加過
lista = changelast(listn, i)#要加入的列表
if lista not in lists:#如果不在這個列表裡
lists.append(lista)#添加到另一個列表
for listn in lists.():#防止lists被刪造成影響
if len(listn) != n2+1:#如果長度沒有達到預期（+1）
lists.remove(listn)#刪除該列表（取消此可能性）
if len(lists[0]) == n:#已經符合條件
for listn in lists:#遍歷列表，檢查首尾
if sumisprime(listn[-1], listn[0]):#如果首尾相加等於素數
print(listn)#環成立，列印出來
break#結束循環
說明：經試驗，都沒什麼問題，n=12也能很快運算完（但我勸你不要打出來），如果你只需要1個素數環，可以把break的縮進調到print(listn)並列。

③ Python ifft

1.傅利葉逆變換得到原始信號

注意fft的結果是個復數，這時取絕對值得到頻率對應的振幅。ifft的結果也是復數，有正有負，因為原始信號也是有正有負，這時不能取絕對值，而應取實數部分。虛數部分都接近於0.當然如果原始信號沒有負數，也可取絕對值。

2.模擬去除高頻雜訊

現在原始信號中加入了頻率為450，500的兩個小幅的高頻信號，模擬高頻雜訊，可以發現信號波形中有很多毛刺。fft的結果頻率是正頻率從0到最高，然後負頻率再從最高到0，所以去除高頻信號就是讓中間那部分為0。