anxious-coder-lhs · November 16, 2019 19:04 · anxious-coder-lhs · Nov 16, 2019
diff --git a/multiply.js b/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("")
 }
	/**
	* 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("")
	}