函数实现一个大位数乘法，可以计算出诸如1865459497823＊6349526719336的结果

  1. // 直接
  2. 1865459497823 * 6349526719336
  3. 1.1844784925266256e+25

ES6 BigInt

function multiplyBig(a, b) {
    let A = BigInt(a), B = BigInt(b);
    let res = A * B;
    return res;
}

console.log(multiplyBig(3, 4))
console.log(multiplyBig(1865459497823, 6349526719336))


// 12n
// 11844784925266255224005528n

43. 字符串相乘

  • num1 和 num2 的长度小于110。
  • num1 和 num2 只包含数字 0-9。
  • num1 和 num2 均不以零开头，除非是数字 0 本身。
  • 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

方法一： 实现相乘运算-竖乘（暴力）

时间复杂度 O(n^2)
需要辅助函数，字符串相加
注意： num1 cur问题在于，大数相乘精度丢失。需要实现 一位数一位数。
'0'.repeat(3) // '000'

var multiply = function(num1, num2) {
    if ([num1, num2].includes('0')) return '0';
    let res = '';
    const len1 = num1.length, len2 = num2.length;
    for(let i = 0; i < len2;i++) {
        let cur2 = num2.charAt(len2 - i - 1);
        let tmp = '';
        for(let j = 0; j < len1; j++) {
            let cur1 = num1.charAt(len1 - j - 1);
            tmp = addString(tmp, cur1 * cur2 + ('0'.repeat(j)));
            // console.log(cur1, tmp);
        }
        res = addString(res, tmp + ('0'.repeat(i)));
    }
    return res
};

 function addString(s1, s2) {
    let nums1 = s1.split('').map(d => parseInt(d));
    let nums2 = s2.split('').map(d => parseInt(d));
    let res = [];
    let tmp = 0;
    while(nums1.length || nums2.length) {
        let num1 = nums1.pop() || 0;
        let num2 = nums2.pop() || 0;
        let sum = num1 + num2 + tmp;
        if (sum > 9) {
            sum -= 10;
            tmp = 1;
        } else {
            tmp = 0;
        }
        res.unshift(sum)
    }
    if (tmp) res.unshift(tmp);
    return res.join('');
}
// @lc code=end
// console.log(multiply('0', '63'), '0')
// console.log(multiply('25', '63'), 1575)
// console.log(multiply('123', '456'), 56088)
// console.log(multiply('123456789', '987654321'), '121932631112635269')
// console.log(multiply('9333852702227987', '85731737104263'), '800207406037324579815815608581')

参考：
https://leetcode-cn.com/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/

方式二：分治

[算法]大数相乘(字符串相乘)？ - 图1
➕ 为权重➕， 至于进位

AB=a1b110^n+(a1b0+b1a0）10^(2/n)+a0*b0

参考：
https://www.jianshu.com/p/b5af56d676b2

方式三：Karatsuba算法


时间复杂度：

伪代码

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)
  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

image.png**
参考：
https://mp.weixin.qq.com/s/GCCEJWbNscJyf4K5nleOnA
https://zh.wikipedia.org/wiki/Karatsuba%E7%AE%97%E6%B3%95
https://zhuanlan.zhihu.com/p/64631681