算法 大数乘法的 javascript 实现

阅读(5155)

如果两个数字本身较大,则其相乘的结果可能超出当前语言能表示的范围,下面描述了一种基础算法。

/**
 * 大数乘法
 * 思路:逐位相乘,不算进位;最后算进位并拼接字符串
 * @param {number} a 被乘数
 * @param {number} b 乘数
 */
var LargeNumberTimes = function(a, b) {
    var result = [],
        // 转换为整型数组
        aArr = a.toString().split('').map(t => parseInt(t)),
        bArr = b.toString().split('').map(t => parseInt(t)),
        aLen=aArr.length,
        bLen=bArr.length;

    // 逐位相乘,不算进位,与计算方向无关
    for (var bIndex=bLen-1; bIndex>=0; bIndex--) {
        for (var aIndex=aLen-1; aIndex>=0; aIndex--) {
            !result[bIndex + aIndex] && ( result[bIndex + aIndex] = 0 );

            result[bIndex + aIndex] += bArr[bIndex] * aArr[aIndex];
        }
    }

    // 因为是从左到右的计算顺序,所以进位要反向
    // (也方便最高位进位时,数组可扩)。
    result.reverse();

    // 最高位可能会进位,所以每次循环重新计算length。
    for (var i=0; i<result.length; i++) {
        var more;

        !result[i] && (result[i] = 0);

        more = parseInt(result[i] / 10);
        if (more > 0) {
            !result[i + 1] && (result[i + 1] = 0);
            result[i + 1] += more;
        }
        result[i] = result[i] % 10;
    }

    return result.reverse().join('');
};

// 可在 Google 输入框进行验证,如果输入的乘数大小超过了范围
// (或js会转换为科学计数法),需要以字符串传入
// Result: 2492816912877266687794240983772975935013386905490061131076320
console.log( LargeNumberTimes('1234567891011121314151617181920', '2019181716151413121110987654321') );
// Result: 999999999998000000000001
console.log( LargeNumberTimes(999999999999, 999999999999) );

以上是两个任意大的数进行乘法运算的 Javascript 实现。