Karatsuba Algorithm in Javascript

Question

I implemented the Karatsuba's algorithm in Javascript.

const multiply = (a, b) => {
    let sizeA = numOfDigits(a);
    let sizeB = numOfDigits(b);
    if(sizeA < sizeB) {
        a = '0'.repeat(sizeB-sizeA).concat(a);
    }
    else if(sizeB < sizeA) {
        b = '0'.repeat(sizeA - sizeB).concat(b);
    }
    if (numOfDigits(a) === 1 && numOfDigits(b) === 1) {
        return a * b;
    } else {
        let n = numOfDigits(a);
        n = ( n % 2 === 0 ) ? n : n + 1;
        let n_2 =  parseInt(Math.ceil(n /2));
        let splitA = reduceInHalf(a);
        let splitB = reduceInHalf(b);
        let p = splitA[0];
        let q = splitA[1];
        let r = splitB[0];
        let s = splitB[1];
        let u = multiply(p, r);
        let v = multiply((q - p).toString(), (s - r).toString());
        let w = multiply(q, s);
        let product = u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w;
        return product;
    }
}

It fails when I pass extremely large numbers , say 2 numbers of 64 digits. I get into the maximum call stack issue. I also came across another implementation which returned a wrong result.

Things work fine with 2 numbers of 32 digits each as well. It gets into a non- terminating recursion as soon as I enter 2 64 digit numbers. Can this be made to work ?

score 3 · Accepted Answer · edited May 23 '17 at 11:46

It looks like you're relying on JavaScript numeric functionality for various pieces (e.g. q - p, and all of u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w); but JavaScript numbers are double-precision floating-point values. They can't exactly represent integers of more than 16 digits. (See "biggest integer that can be stored in a double".)

If you want to do math with very large integers, you'll need to either find a big-integer library, or manage it yourself (using strings or arrays or whatnot).

Karatsuba Algorithm in Javascript

1 Answers1