Karatsuba Algorithm implemented in JavaScript not accurate

Question

I am trying to implement the Karatsuba Algorithm in JavaScript. Below is my Implementation:

var bigInt = require("big-integer");

function bigKaratsuba(num1, num2) {
 if (Number(num1) < 10 || Number(num2) < 10) {
  return (Number(num1)*Number(num2)).toString();
 }
 var len1 = String(num1).length;
 var len2 = String(num2).length;
 var m = Math.max(len1, len2);
 var m2 = Math.floor(m/2);

 var high1 = String(num1).substring(0, m-m2);
 var low1 = String(num1).substring(m-m2, len1);
 var high2 = String(num2).substring(0, m-m2);
 var low2 = String(num2).substring(m-m2, len2);

 var high1 = bigInt(String(num1).substring(0, m-m2));
 var low1 = bigInt(String(num1).substring(m-m2, len1));
 var high2 = bigInt(String(num2).substring(0, m-m2));
 var low2 = bigInt(String(num2).substring(m-m2, len2));

 var low1AndHigh1 = low1.add(high1).toString();
 var low2AndHigh2 = low2.add(high2).toString();
 
 var high1 = String(high1);
 var low1 = String(low1);
 var high2 = String(high2);
 var low2 = String(low2);

 var z0 = bigKaratsuba(low1, low2);
 var z1 = bigKaratsuba(low1AndHigh1, low2AndHigh2);
 var z2 = bigKaratsuba(high1, high2);

 var z0_int = bigInt(z0);
 var z1_int = bigInt(z1);
 var z2_int = bigInt(z2);

 var product = z2_int.times(Math.pow(10, m2*2)).add(z1_int.minus(z2_int).minus(z0_int).times(Math.pow(10, m2))).add(z0_int);

 return String(product);
}

bigKaratsuba(15, 15);

<script src="http://peterolson.github.com/BigInteger.js/BigInteger.min.js"></script>

This implementation works perfectly for small value, however while I am trying to calculate 3141592653589793238462643383279502884197169399375105820974944592 times 2718281828459045235360287471352662497757247093699959574966967627, the answer gose wrong, what I got is 8541020071716445382689180042569347598344699394502900911882868254737925119641226981222291225174629534283004908305569988292269254, which is not correct. The correct answer is 8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184 which I got it from here. I have tried search on the stackoverflow but I haven't find any solution to my problem. There is no error or anything when I run my code. Any help or pointer will be highly appreciated. Thanks in advance for all the people who are being helpful.

You used first/most-significant parts of equal length - think about the lengths of the lower/least-significant parts and what that implies regrading scaling. — greybeard, Jul 12 '17 at 09:52
transforming to from string seems counter productive either compute on strings or on numbers (convert just once before and once after the whole multiplication) using `pow(10 ,...)` for multiplication is crazy why not add zeros to result string ? using base=16 simplifies things for the transition `num<->string` , are you sure you are not overflowing the final addition? see [fast bignum sqr](https://stackoverflow.com/q/18465326/2521214) I got similar problem (which @greybeard repaired btw) so just compare the old and new Karatsuba code in there ... and check if yours is handling this as should — Spektre, Jul 12 '17 at 12:24
My bet is your usage of `Math.pow(10,...)` truncates mantissa ... for higher powers .... — Spektre, Jul 12 '17 at 12:33

Leonard Ge · Answer 1 · 2017-07-17T01:39:45.277

With the great help of @Spektre and @greybeard, I managed to solve this problem. Below is the correct code:

var bigInt = require("big-integer");

function bigKaratsuba(num1, num2) {
 if (Number(num1) < 10 || Number(num2) < 10) {
  return (Number(num1)*Number(num2)).toString();
 }
 var len1 = String(num1).length;
 var len2 = String(num2).length;
 var m = Math.max(len1, len2);
 var m2 = Math.floor(m/2);

 var high1 = bigInt(String(num1).substring(0, len1-m2));
 var low1 = bigInt(String(num1).substring(len1-m2, len1));
 var high2 = bigInt(String(num2).substring(0, len2-m2));
 var low2 = bigInt(String(num2).substring(len2-m2, len2));

 var low1AndHigh1 = low1.add(high1).toString();
 var low2AndHigh2 = low2.add(high2).toString();
 
 var high1 = String(high1);
 var low1 = String(low1);
 var high2 = String(high2);
 var low2 = String(low2);

 var z0 = bigKaratsuba(low1, low2);
 var z1 = bigKaratsuba(low1AndHigh1, low2AndHigh2);
 var z2 = bigKaratsuba(high1, high2);

 var z0_int = bigInt(z0);
 var z1_int = bigInt(z1);
 var z2_int = bigInt(z2);     
    var z1MinusZ2MinusZ0 = z1_int.minus(z2_int).minus(z0_int).toString();

 var product = bigInt(addTrailingZero(z2, m2*2)).add(bigInt(addTrailingZero(z1MinusZ2MinusZ0, m2))).add(z0);

 return String(product);
}

function addTrailingZero (numericString, numberOfZeroAdded) {
    for (var i = 0; i < numberOfZeroAdded; i++) {
     numericString = numericString + "0";
    }
    return numericString;
}

<script src="http://peterolson.github.com/BigInteger.js/BigInteger.min.js"></script>

As @Spektre pointed out, my original solution does truncate the mantissa since the biggest safe integer is 2^53-1. So one should add zero instead of doing the multiplication, besides it's also faster to add zero I believe.(Let me know if I am wrong).

Besides after trying the number suggested by @greybeard, I found that my original code snippet doesn't provide the correct solution so I changed it to

    var high1 = bigInt(String(num1).substring(0, len1-m2));
    var low1 = bigInt(String(num1).substring(len1-m2, len1));
    var high2 = bigInt(String(num2).substring(0, len2-m2));
    var low2 = bigInt(String(num2).substring(len2-m2, len2));

(A spelling checker would have pointed you to `bigget`, but telling `dose` from *does* (in the question: *goes* instead of`gose`) would take a semantic check, as *one should add trailing zeroes* instead of `it should add zero` (sticking with `bigInt`, one would multiply with the power of ten corresponding with `m2`/the modulus, using *Horner scheme* or appropriate powers).) — greybeard, Jul 13 '17 at 06:48
I've fixed the spelling and grammar mistakes you pointed out. But I am still confused about the last part in your comment about sticking with `bigInt` and use Horner scheme. — Leonard Ge, Jul 17 '17 at 01:47
At the top of `bigKaratsuba()`, you have six coercions of `num1/2` to `String`, the last four thereof in as many instantiations of `bigInt`. After the `add()`s, you explicitly instantiate `String`s from these `bigInt`s (with the same values you didn't keep eight lines before), just to pass them to `bigKaratsuba()`. Have a (an "inner") Karatsuba procedure that gets passed numbers of known representations and known order of magnitude. I don't know of a multiply for ECMAScript `String`, so just stay with `BigInt`: *base conversion* is costly with none of the bases a power of the other. — greybeard, Jul 17 '17 at 07:15

Karatsuba Algorithm implemented in JavaScript not accurate

1 Answers1