Karatsuba Integer Multiplication

multiply.js

/**
 * Multiply any two numbers as strings using the linear method of operation. Takes O(n)
 * Returns the result as an array of numbers in the reverse order.
 * 
 * @param {*} first 
 * @param {*} second 
 */
function mulitiplyLinear(first, second) {
    let larger, factor;
    if (first.length > second.length) {
        larger = first;
        factor = second;
    } else {
        larger = second;
        factor = first;
    }

    const result = Array(larger.length + 1).fill(0);
    let k = larger.length;
    for (let i = larger.length - 1; i >= 0; i--) {
        const product = result[k] + parseInt(larger[i]) * factor;
        result[k] = (Math.floor(product % 10));
        result[k - 1] = Math.floor(product / 10);
        k--;
    }

    let nonZeroIndex = 0;
    for (; nonZeroIndex < result.length; nonZeroIndex++) {
        if (result[nonZeroIndex] !== 0) {
            break;
        }
    }
    return nonZeroIndex === result.length ? "0" : result.slice(nonZeroIndex).join("")
}

/**
 * Multiply the 2 numbers given as string using the Karatsuba multiplication.
 * Uses the linear multiplication of O(n) using the linear method when one of the numbers
 * is of size 1 or less.
 * 
 * @param {*} first 
 * @param {*} second 
 */
function multiply(first, second) {
    if (first.length < 2 || second.length < 2) {
        return mulitiplyLinear(first, second);
    }

    const minLength = Math.min(first.length, second.length);
    const splitPow = Math.floor(minLength / 2);
    const x1 = first.substr(0, first.length - splitPow);
    const x0 = first.substr(first.length - splitPow);
    const y1 = second.substr(0, second.length - splitPow);
    const y0 = second.substr(second.length - splitPow);

    const z2 = multiply(x1, y1);
    const z0 = multiply(x0, y0)
    const z1Product = multiply(add(x1, x0), add(y1, y0));
    const z1 = substract(substract(z1Product, z2), z0);

    return add(add(z2 + Array(splitPow * 2).fill(0).join(""), z1 + Array(splitPow).fill(0).join("")), z0);
}

/**
 * Adds the 2 large numbers represented as reverse arrays.
 * 
 * @param {*} first 
 * @param {*} second 
 */
function add(first, second) {
    let i = first.length - 1;
    let j = second.length - 1;
    // const result = Array(Math.max(first.length, second.length) + 1).fill(0);
    const result = [];
    // let k = result.length - 1;
    let carryOver = 0;
    while (i >= 0 || j >= 0) {
        const sum = carryOver + parseInt(first[i] || 0) + parseInt(second[j] || 0)
        result.push(Math.floor(sum % 10));
        carryOver = Math.floor(sum / 10);
        i--; j--;
        //  k--
    }

    const sum = carryOver > 0 ? carryOver : "";
    return result.reduceRight((sum, curr) => {
        return `${sum}${curr}`;
    }, sum);
}

/**
 * Subtract two large numbers as reverse arrays.
 * 
 * @param {*} first 
 * @param {*} second 
 */
function substract(first, second) {
    const result = Array(first.length).fill(0);
    let i = first.length - 1;
    let j = second.length - 1;
    let k = result.length - 1;
    let carryFrom = 0;
    while (i >= 0 || j >= 0) {
        const a = parseInt(first[i] || 0)
        const b = parseInt(second[j] || 0)
        if (a - carryFrom >= b) {
            result[k] = a - carryFrom - b;
            carryFrom = 0;
        } else {
            result[k] = a - carryFrom + 10 - b;
            carryFrom = 1;
        }
        i--;
        j--
        k--
    }

    let nonZeroIndex = 0;
    for (; nonZeroIndex < result.length; nonZeroIndex++) {
        if (result[nonZeroIndex] !== 0) {
            break;
        }
    }
    return nonZeroIndex === result.length ? "0" : result.slice(nonZeroIndex).join("")
}

Test Snippets

console.log(multiply("0", "0"));
console.log(multiply("1", "1"))
console.log(multiply("1", "5"))
console.log(multiply("5", "5"))
console.log(multiply("11", "5"))
console.log(multiply("9", "9"))
console.log(multiply("11", "11"))
console.log(multiply("99", "99"))
console.log(multiply("12345", "99"))
console.log(multiply("1224", "12355"))