The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

这段 FFT 导论从多项式乘法切入。先把两个多项式在同一组足够多且互不相同的点上求值，再把对应值相乘，就能得到乘积多项式在这些点上的值。影片接着解释怎样选点来加快求值：在它讨论的二次幂规模下，把项按次数的奇偶拆开，再把单位根平方，就会得到下一层递归所需的那组单位根。

存档字幕（转写方式未注明） ↗ · 引文按字幕原文展示，可点时间戳回看片段。