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。