如何用vanilla.js实现超大数字乘法

背景

今年年初的时候在网上看到了一家心仪的科技创业公司,于是便按捺不住躁动的心,在 LinkedIn 上加了该公司的 CTO,毛遂自荐一番,看能不能被我这个小白捡个漏,进入高大上的 AI 行业——继续做 web……哈哈哈

运气不错,我居然真的得到了一个面试机会。其中一道面试题让面经不足的我当场懵逼——实现一个超大数字乘法的函数。在一个小时的尝试之后,面试时间到了,解决方法还是没做出来,含恨 GG。时隔数月,我又想起这道题来,终于得出了一个比较满意的解决方法。

分析

先来分析一下问题:

  • 在 JavaScript 中,Number的取值范围从最小-(2^53 - 1)到最大(2^53 - 1) (参考 MDN)。如果变量的值超过这两个界限的话就会变成-InfiniteInfinite。因此,假如我们要做千位数以上的乘法,就不能使用Number作为变量类型,而只能使用String。同样的,返回的结果也应该是String才能避免溢出。
  • 在计算过程中,需要应用分治思想,一个数字一个数字地乘上去,然后再考虑数字进位的问题。
  • 将最终得到的结果转换成为String的格式输出

实际操作

第一步 定义输入与输出

根据分析,函数的输入与输出应该规定如下。

1
2
3
4
5
6
7
8
9
/**
* Multiplication of two big numbers
* @param {String} num1 big number which may exceed javascript native number limitation
* @param {String} num2 big number which may exceed javascript native number limitation
* @returns {String} The product of the two big numbers
*/
function bigNumberMultiplication(num1, num2) {
// Implementation
}

第二步 使用数组储存每个数字

首先,num1num2现在都是String。为了方便我们计算,我们必须将每个数组拆分成以单个数字为单位的数组。

如:'123456' 转换为 [1, 2, 3, 4, 5, 6]

  1. 使用toString()将变量转换为String
  2. 使用split()将字符串变量的每一个字符分开并生成一个字符数组
  3. 使用map()将字符数组里面的所有字符通过parseInt()方法转换成Number
  4. 使用reverse()将数组的顺序倒转过来,便于计算,因为数组的第一位是最大位数,而计算是从最小位数开始的

代码如下:

1
2
3
4
5
6
7
8
9
10
11
// reverse the array to start calculation from the smallest digit
const a = num1
.toString()
.split("")
.map(x => parseInt(x))
.reverse();
const b = num2
.toString()
.split("")
.map(x => parseInt(x))
.reverse();

第三步 储存相乘的积

当我们得到两个存有数字的数组之后,我们就可以开始做乘法,将对应的两个数字一一乘起来,并存入一个新的result数组里面。

如果是 521 乘以 710,结合第一步倒转数组,将会得到果第一个数组是[1, 2, 5], 第二个数组是[0, 1, 7]

那么最终result将会得到[0, 1, 9, 19, 35],这相当于结果里面的每一位数再做进位之前是多少。

注意:位数是使用i + j实时计算的,而不是新建一个变量储存后使用,这是因为在大量循环里重复新建变量会导致 GC 也重复删除变量从而导致性能问题。(亲测)

代码如下:

1
2
3
4
5
6
7
const result = [];
// iterate every digit and construct an array to record every digit
b.forEach((vb, j) => {
a.forEach((va, i) => {
result[i + j] = (result[i + j] ? result[i + j] : 0) + va * vb;
});
});

第四步 处理进位

result数组里,每一位数都不一定是个位数。所以这个时候我们就得处理进位的问题。进位问题很容易解决。对每一位数,只要它大于等于 10,就将它缩小 10 倍,然后将它的下一位加 1。直到这一位数处理完毕之后,再对下一位数进行处理。比如:

[0, 1, 9, 19, 35] 处理第一位数 0,0 <= 10,去下一位

[0, 1, 9, 19, 35] 处理第二位数 1,1 <= 10,去下一位

[0, 1, 9, 19, 35] 处理第三位数 1,9 <= 10,去下一位

[0, 1, 9, 19, 35] 处理第四位数 19,19 > 10,更新第四位数位19 % 10,第五位数加19 / 10

[0, 1, 9, 9, 36] 处理第四位数 9,9 <= 10,去下一位

[0, 1, 9, 9, 36] 处理第五位数 36,19 > 10,更新第五位数位36 % 10,第六位数加36 / 10

[0, 1, 9, 9, 6, 3] 处理第五位数 6,6 <= 10,去下一位

[0, 1, 9, 9, 6, 3] 处理第六位数 3,3 <= 10,完成

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
// adding the extra values to next digit until every digit is reduced to unit digit
let currDigit = 0;
let nextDigit;
while (result[currDigit] !== undefined) {
if (result[currDigit] >= 10) {
nextDigit = currDigit + 1;
result[nextDigit] =
(result[nextDigit] ? result[nextDigit] : 0) +
Math.floor(result[currDigit] / 10);
result[currDigit] = result[currDigit] % 10;
}
currDigit++;
}

第五步 返回字符串

最终,result成为了一个只有个位数的数组。此时,我们只需要将其再倒转回来,再通过join()生成一个完整的字符串即可。

代码如下:

1
return result.reverse().join("");

大功告成!

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Multiplication of two big numbers
* @param {String} num1 big number which may exceed javascript native number limitation
* @param {String} num2 big number which may exceed javascript native number limitation
* @returns {String} The product of the two big numbers
*/
function bigNumberMultiplication(num1, num2) {
// reverse the array to start calculation from the smallest digit
const a = num1
.toString()
.split("")
.map(x => parseInt(x))
.reverse();
const b = num2
.toString()
.split("")
.map(x => parseInt(x))
.reverse();

const result = [];
// iterate every digit and construct an array to record every digit
b.forEach((vb, j) => {
a.forEach((va, i) => {
result[i + j] = (result[i + j] ? result[i + j] : 0) + va * vb;
});
});
// adding the extra values to next digit until every digit is reduced to unit digit
let currDigit = 0;
let nextDigit;
while (result[currDigit] !== undefined) {
if (result[currDigit] >= 10) {
nextDigit = currDigit + 1;
result[nextDigit] =
(result[nextDigit] ? result[nextDigit] : 0) +
Math.floor(result[currDigit] / 10);
result[currDigit] = result[currDigit] % 10;
}
currDigit++;
}
return result.reverse().join("");
}