如何用vanilla.js实现超大数字乘法
October 05, 2018
背景
今年年初的时候在网上看到了一家心仪的科技创业公司，于是便按捺不住躁动的心，在 LinkedIn 上加了该公司的 CTO，毛遂自荐一番，看能不能被我这个小白捡个漏，进入高大上的 AI 行业——继续做 web……哈哈哈
运气不错，我居然真的得到了一个面试机会。其中一道面试题让面经不足的我当场懵逼——实现一个超大数字乘法的函数。在一个小时的尝试之后，面试时间到了，解决方法还是没做出来，含恨 GG。时隔数月，我又想起这道题来，终于得出了一个比较满意的解决方法。
分析
先来分析一下问题：
- 在 JavaScript 中，
Number的取值范围从最小-(2^53 - 1)到最大(2^53 - 1)(参考 MDN)。如果变量的值超过这两个界限的话就会变成-Infinite和Infinite。因此，假如我们要做千位数以上的乘法，就不能使用Number作为变量类型，而只能使用String。同样的，返回的结果也应该是String才能避免溢出。 - 在计算过程中，需要应用分治思想，一个数字一个数字地乘上去，然后再考虑数字进位的问题。
- 将最终得到的结果转换成为
String的格式输出
实际操作
第一步 定义输入与输出
根据分析，函数的输入与输出应该规定如下。
/**
* 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
}
第二步 使用数组储存每个数字
首先，num1和num2现在都是String。为了方便我们计算，我们必须将每个数组拆分成以单个数字为单位的数组。
如：'123456' 转换为 [1, 2, 3, 4, 5, 6]
- 使用
toString()将变量转换为String - 使用
split()将字符串变量的每一个字符分开并生成一个字符数组 - 使用
map()将字符数组里面的所有字符通过parseInt()方法转换成Number - 使用
reverse()将数组的顺序倒转过来，便于计算，因为数组的第一位是最大位数，而计算是从最小位数开始的
代码如下：
// 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 也重复删除变量从而导致性能问题。（亲测）
代码如下：
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，完成
代码如下：
// 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()生成一个完整的字符串即可。
代码如下：
return result.reverse().join("");
大功告成！
完整代码：
/**
* 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("");
}