javascript - JS中如何实现数字乘法

Question

我想创建一个将数字逐位相乘的函数，就像我们在学校所做的那样。例如，在 445 * 456 中，我们首先将 5 乘以 6，然后将 4 乘以 4，然后将 4 乘以 5，依此类推。我想这样做是为了在字符串中获取非常非常长的乘法的答案。

这里，numArray是数组中存储的数字，例如563是[5,6,3]； 类似地，另一个数字可以是例如621 转换为 [6, 2, 1]

   for(var i = 1; i <= anotherNumArray.length; i++) {
        var multiplier = anotherNumArray[anotherNumArray.length-i]
        for(var j = 1; j <= numArray.length; j++) {
            var multiplicand = numArray[numArray.length-j]
            answer.unshift(multiplicand*multiplier);
   }

我正在尝试循环数字乘法。但我得到了奇怪的结果。

Answer 1

问题比提出的更复杂

假设实际的“长乘法”模拟，即只允许数字乘法和求和，请参阅下面的注释和工作代码。

首先，代码忽略了两个数字的乘法会溢出并产生一个非零进位值的事实，该值应与下一个乘法相加

其次，正如我们在学校学到的那样，对于每个数字，我们都会收到与第二个数字的所有其他数字相乘的新结果。最后我们需要对这些乘法结果求和

下面的代码适用于非负十进制数。它可以简化，但已尽力保持初始算法的精神

// parameters
const lhs = "445";
const rhs = "456";

// utilities
const createZeros = length => new Array(length).fill(0);
const padArrayEnd = (length, padding, array) => [...array, ...createZeros(length - array.length)];
const last = array => array[array.length - 1];

// given a carray and an array of digits, add the carry to the last digit.
// if the result overflows, add the remainder as a new digit instead
// example;
//   array = [3, 4, 5]; addCarry(2, array); array == [3, 4, 7]
//   array = [3, 4, 9]; addCarry(2, array); array == [3, 4, 0, 1]
function addCarry(carry, digits) {
    if (carry == 0) {
        return;
    }

    let value = last(digits) + carry;
    if (value > 10) {
        digits[digits.length - 1] = 0;
        digits.unshift(value % 10);
    } else {
        digits[digits.length - 1] = value;
    }
}

console.log({ message: "start", lhs, rhs });

// state
const answer = [];
const entries = [];
let carry = 0;

// perform digit by digit multiplication.
// remember that the result array for each digit should have N leading zeros, where N is the position of that digit.
// this is the reason we keep an array of entries. each entry, is the result array corresponding to that digit
for(let lcur = 0; lcur < lhs.length; lcur++) {
    const leftDigit = lhs[lhs.length - 1 - lcur];

    // the multiplications entry
    const multiplications = createZeros(lcur);

    for(let rcur = 0; rcur < rhs.length; rcur++) {
        const rightDigit = rhs[rhs.length - 1 - rcur];

        // perform multiplication, but notice that in case of overflow we keep
        // only the ones, and remember carry for next iteration
        const times = (leftDigit * rightDigit) + carry;
        const ones = times % 10;
        carry = Math.floor(times / 10);

        multiplications.unshift(ones);
        console.log({ message: "step", expr: `${leftDigit} * ${rightDigit}`, times, ones, carry });
    }

    if (carry != 0){
        multiplications.unshift(carry);
        carry = 0;
    }

    // update entries
    entries.push(multiplications); 
    console.log({ message: "entry", multiplications });
}

// add the final carry
addCarry(carry, last(entries));

console.log({ message: "entries", entries });

// sum all entries with carries
const maxLength = entries
    .map(entry => entry.length)
    .reduce((acc, entry) => Math.max(acc, entry), 0);

// for convinience, reverse all entries - this can by bypassed with messing around with indices
entries.forEach(entry => entry.reverse());

carry = 0;
for (let idx = 0; idx < maxLength; ++idx) {
    const sum = entries
        .map(entry => entry[idx] || 0)
        .reduce((acc, value) => acc + value, carry);

    const ones = sum % 10;
    carry = Math.floor(sum / 10);

    answer.unshift(ones);
    console.log({ message: "summation", sum, ones, carry, answer });
}

// add final summation carry
// remember that we reversed stuff before, reverse back
// answer.reverse()
addCarry(carry, answer);

// finalize a result 
const result = answer.join("");
const expected = (parseInt(lhs) * parseInt(rhs)).toString(); // string for some reason
console.log({ message: "finish", expr: `${lhs} * ${rhs} = ${answer.join("")}`, answer, expected });