V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
qiutianaimeili
V2EX  ›  分享创造

js 大数相乘

  •  
  •   qiutianaimeili · 2018-01-06 16:06:08 +08:00 · 4561 次点击
    这是一个创建于 2512 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

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

    17 条回复    2018-01-07 23:31:19 +08:00
    qiayue
        1
    qiayue  
       2018-01-06 16:27:18 +08:00
    文章很好,可是为什么下载需要登录,然后注册登录都需要填写家乡地址和出生年月日

    虽然看了一下知道你是为了省去密码,虽然可能你是加密后保存,但还是不敢填
    geelaw
        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
    qiutianaimeili
        3
    qiutianaimeili  
    OP
       2018-01-06 17:27:10 +08:00
    @geelaw 受教了,有时间研究研究
    yangg
        4
    yangg  
       2018-01-06 17:33:35 +08:00 via iPhone
    有没有位运算的?
    codermagefox
        5
    codermagefox  
       2018-01-06 17:33:41 +08:00
    看到这些 FFT 这些东西想起来以前其实都学过,全忘光了,唉。
    qiutianaimeili
        6
    qiutianaimeili  
    OP
       2018-01-06 17:33:50 +08:00
    @qiayue 这个,主要是考虑到记密码不方便,但是我又要识别用户身份。之所以填这么多,是因为如果拿用户名作为唯一标识的话,很容易重复。所以就搞了这么个不伦不类的东西出来。。。其实在浏览器里面可以看到 demo 里面完整的代码,js 也没有压缩,可以直接看的。
    qiutianaimeili
        7
    qiutianaimeili  
    OP
       2018-01-06 17:35:01 +08:00
    @codermagefox 上大学那会逃课太严重,我都不记得我学过。。。
    qiutianaimeili
        8
    qiutianaimeili  
    OP
       2018-01-06 17:37:01 +08:00
    @yangg 没遇到过,遇到了再研究研究。
    hchechao2
        9
    hchechao2  
       2018-01-06 17:42:31 +08:00 via Android
    之前 c ++算法课第一个作业就是这个,然而并没有写出来 FFT
    qiutianaimeili
        10
    qiutianaimeili  
    OP
       2018-01-06 17:55:54 +08:00
    @hchechao2 网上好多 c++,c 的 FFT,很少看到其他语言的,我想应该就是为了完成作业才弄的。。。但是我觉得好的东西就应该保留下来,算法才是突破问题和效率的关键。
    d4rkb1ue
        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("");
    };
    ```
    nutting
        12
    nutting  
       2018-01-06 20:21:29 +08:00 via Android
    这种不是模拟手工式子即可吗?傅里叶变换?好复杂啊
    Pastsong
        13
    Pastsong  
       2018-01-06 20:36:52 +08:00 via Android
    可以跑下 js perf 看一下
    qiutianaimeili
        14
    qiutianaimeili  
    OP
       2018-01-06 20:39:06 +08:00
    @nutting 其实平时我们模拟手工乘法就够了,这个是进阶版的。确实复杂了点,看个人需求,如果想提升自己当然就得下功夫了。而且你一旦看懂,你就会觉得这个算法很牛逼。
    lsmgeb89
        15
    lsmgeb89  
       2018-01-07 08:00:14 +08:00 via Android
    算法导论上也有
    gnaggnoyil
        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 因子.
    qiutianaimeili
        17
    qiutianaimeili  
    OP
       2018-01-07 23:31:19 +08:00
    @gnaggnoyil v 友大神果然多,虽然我一句没听懂,但是我以后会好好学习的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   936 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:07 · PVG 05:07 · LAX 13:07 · JFK 16:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.