快速傅立叶变换( FFT )实现 js 大数相乘。一般的大数相乘复杂度是 N^2,FFT 的算法复杂度是 Nlog2(N)。
FFT 算法本身比较难理解,需要了解关于虚数,复数,矩阵等知识。下面是 js 实现的:
其实只要了解了原理,实现起来并不复杂,难点也就在原理上。
我花了很长时间看 FFT 的运行原理,写了这篇文章,里面介绍了如何通过 FFT 来实现大数相乘。
文章地址:http://www.qiutianaimeili.com/html/page/2018/01/xca0r6dmkha.html
如果是第一次接触 FFT,可能无法马上理解文章内容,需要慢慢消化。
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.