search

AnotherZjuturtle / Gitalk

For zjuturtle.com Gitalk system
1 stars 0 forks source link

任意长度的 FFT 算法-混合基算法及雷德算法 | zjuturtle's blog #14

Open AnotherZjuturtle opened 6 years ago

AnotherZjuturtle commented 6 years ago

https://zjuturtle.com/2017/12/26/fft/

之前我写的 FFT 用的是最基本的 库利-图基算法，而且是取模2，因此只能实现 2 的幂次方长度的运算。那么如果点数不是 2 的幂次方该怎么办呢？当点数为合数的时候，可以用库利-图基混合基算法；当点数为质数的时候，可以用雷德算法

ArianaGu commented 3 years ago

很清楚，赞