js 大数相乘

[qiutianaimeili]

快速傅立叶变换（ FFT ）实现 js 大数相乘。一般的大数相乘复杂度是 N^2,FFT 的算法复杂度是 Nlog2(N)。

FFT 算法本身比较难理解，需要了解关于虚数，复数，矩阵等知识。下面是 js 实现的：

其实只要了解了原理，实现起来并不复杂，难点也就在原理上。

我花了很长时间看 FFT 的运行原理，写了这篇文章，里面介绍了如何通过 FFT 来实现大数相乘。

文章地址:http://www.qiutianaimeili.com/html/page/2018/01/xca0r6dmkha.html

如果是第一次接触 FFT，可能无法马上理解文章内容，需要慢慢消化。

[qiayue]

文章很好，可是为什么下载需要登录，然后注册登录都需要填写家乡地址和出生年月日

虽然看了一下知道你是为了省去密码，虽然可能你是加密后保存，但还是不敢填

[geelaw]

然而，真的使用复数会带来浮点误差的问题。一般来说会选择使用 Z/(p) 上的 Fourier 变换，也就是所谓数论变换。

https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform

[qiutianaimeili]

@geelaw 受教了，有时间研究研究

[yangg]

有没有位运算的？

[codermagefox]

看到这些 FFT 这些东西想起来以前其实都学过，全忘光了，唉。

[qiutianaimeili]

@qiayue 这个，主要是考虑到记密码不方便，但是我又要识别用户身份。之所以填这么多，是因为如果拿用户名作为唯一标识的话，很容易重复。所以就搞了这么个不伦不类的东西出来。。。其实在浏览器里面可以看到 demo 里面完整的代码，js 也没有压缩，可以直接看的。

[qiutianaimeili]

@codermagefox 上大学那会逃课太严重，我都不记得我学过。。。

[qiutianaimeili]

@yangg 没遇到过，遇到了再研究研究。

[hchechao2]

之前 c ＋＋算法课第一个作业就是这个，然而并没有写出来 FFT

[qiutianaimeili]

@hchechao2 网上好多 c++，c 的 FFT，很少看到其他语言的，我想应该就是为了完成作业才弄的。。。但是我觉得好的东西就应该保留下来，算法才是突破问题和效率的关键。

[d4rkb1ue]

@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("");
};
```

[nutting]

这种不是模拟手工式子即可吗？傅里叶变换？好复杂啊

[Pastsong]

可以跑下 js perf 看一下

[qiutianaimeili]

@nutting 其实平时我们模拟手工乘法就够了，这个是进阶版的。确实复杂了点，看个人需求，如果想提升自己当然就得下功夫了。而且你一旦看懂，你就会觉得这个算法很牛逼。

[lsmgeb89]

算法导论上也有

[gnaggnoyil]

我就扔坨代码,扔完就走.
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 因子.

[qiutianaimeili]

@gnaggnoyil v 友大神果然多，虽然我一句没听懂，但是我以后会好好学习的。