快速傅立叶变换( FFT )实现 js 大数相乘。一般的大数相乘复杂度是 N^2,FFT 的算法复杂度是 Nlog2(N)。
FFT 算法本身比较难理解,需要了解关于虚数,复数,矩阵等知识。下面是 js 实现的:
其实只要了解了原理,实现起来并不复杂,难点也就在原理上。
我花了很长时间看 FFT 的运行原理,写了这篇文章,里面介绍了如何通过 FFT 来实现大数相乘。
文章地址:http://www.qiutianaimeili.com/html/page/2018/01/xca0r6dmkha.html
如果是第一次接触 FFT,可能无法马上理解文章内容,需要慢慢消化。
1
qiayue 2018-01-06 16:27:18 +08:00
文章很好,可是为什么下载需要登录,然后注册登录都需要填写家乡地址和出生年月日
虽然看了一下知道你是为了省去密码,虽然可能你是加密后保存,但还是不敢填 |
2
geelaw 2018-01-06 16:32:51 +08:00
然而,真的使用复数会带来浮点误差的问题。一般来说会选择使用 Z/(p) 上的 Fourier 变换,也就是所谓数论变换。
https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform |
3
qiutianaimeili OP @geelaw 受教了,有时间研究研究
|
4
yangg 2018-01-06 17:33:35 +08:00 via iPhone
有没有位运算的?
|
5
codermagefox 2018-01-06 17:33:41 +08:00
看到这些 FFT 这些东西想起来以前其实都学过,全忘光了,唉。
|
6
qiutianaimeili OP @qiayue 这个,主要是考虑到记密码不方便,但是我又要识别用户身份。之所以填这么多,是因为如果拿用户名作为唯一标识的话,很容易重复。所以就搞了这么个不伦不类的东西出来。。。其实在浏览器里面可以看到 demo 里面完整的代码,js 也没有压缩,可以直接看的。
|
7
qiutianaimeili OP @codermagefox 上大学那会逃课太严重,我都不记得我学过。。。
|
8
qiutianaimeili OP @yangg 没遇到过,遇到了再研究研究。
|
9
hchechao2 2018-01-06 17:42:31 +08:00 via Android
之前 c ++算法课第一个作业就是这个,然而并没有写出来 FFT
|
10
qiutianaimeili OP @hchechao2 网上好多 c++,c 的 FFT,很少看到其他语言的,我想应该就是为了完成作业才弄的。。。但是我觉得好的东西就应该保留下来,算法才是突破问题和效率的关键。
|
11
d4rkb1ue 2018-01-06 19:25:40 +08:00
@yangg
``` /** * @param {string} num1 * @param {string} num2 * @return {string} */ var multiply = function(num1, num2) { // max digits, may less than this let digits = new Array(num1.length + num2.length).fill(0); num1 = num1.split("").reverse(); num2 = num2.split("").reverse(); for (let i = 0; i < num1.length; i++) { for (let j = 0; j < num2.length; j++) { digits[i + j] += Number(num1[i]) * Number(num2[j]); } } // carry for (let i = 0; i < digits.length - 1; i++) { digits[i + 1] += Math.floor(digits[i] / 10); digits[i] = digits[i] % 10; } while (digits.length > 0 && digits[digits.length - 1] === 0) { digits.pop(); } return digits.length === 0 ? "0" : digits.reverse().join(""); }; ``` |
12
nutting 2018-01-06 20:21:29 +08:00 via Android
这种不是模拟手工式子即可吗?傅里叶变换?好复杂啊
|
13
Pastsong 2018-01-06 20:36:52 +08:00 via Android
可以跑下 js perf 看一下
|
14
qiutianaimeili OP @nutting 其实平时我们模拟手工乘法就够了,这个是进阶版的。确实复杂了点,看个人需求,如果想提升自己当然就得下功夫了。而且你一旦看懂,你就会觉得这个算法很牛逼。
|
15
lsmgeb89 2018-01-07 08:00:14 +08:00 via Android
算法导论上也有
|
16
gnaggnoyil 2018-01-07 23:04:34 +08:00
我就扔坨代码,扔完就走.
https://github.com/gnaggnoyil/bignumplusplus @qiutianaimeili 基于 Z/p 上的 FFT 由于最后将 Z/p 上序列转换成 Z 上的序列只能使用 trival 的映射,所以 Z/p 选取时 p 必须足够大保证卷积计算完毕后的结果不能在 Z/p 上溢出.这就意味着随着大整数长度的增加 p 的大小要求也会水涨船高,所以在 Schönhage – Strassen 算法中大整数长度长到一定地步时 Z/p 本身也需要通过高精度计算来获得结果.这也是为什么 Schönhage – Strassen 算法的复杂度会比 FFT 多一个 lglgn 因子. |
17
qiutianaimeili OP @gnaggnoyil v 友大神果然多,虽然我一句没听懂,但是我以后会好好学习的。
|