How to implement Karatsuba Multiplication in javascript?

Question

I have tried to implement karatsuba algorithm using the below code. The problem starts when the number of digits in x and y(parameters) mismatch as the recursive call doesn't work in that case with the below logic. As of now, am getting the correct output when the number of digits in x and y is the same.

To be more precise, I think the problem starts with the calculations of z1 and z3 because that is where the number of digits for x and y mismatches frequently.

I also am a bit confused about deriving a logic on how to define m which is the power for the base here. I believe am making it clear regarding my issue? (Any suggestion for more optimization would be more helpful as i have just started my journey in java script).

function karatSuba(x,y)
{
  var x1,x0,y1,y0,base,m;
  var dummy_x = x.toString();
  var dummy_y = y.toString();
  var n = (dummy_x.length>dummy_y.length) ? dummy_y.length : dummy_x.length;
  m = Math.round(n/2);
  base  = 10;

  //base case
  if((x<base)||(y<base))
  return x * y;
  //base case

  var bm = Math.pow(base ,m);

  var dummy_x1 = dummy_x.substring(0,n/2);
  var x1 = parseInt(dummy_x1);
  dummy_x1 = null;

  var dummy_x1 = dummy_x.substring(n/2,n);
  var x0 = parseInt(dummy_x1);
  dummy_x1 = null;

  var dummy_y1 = dummy_y.substring(0,n/2);
  var y1 = parseInt(dummy_y1);
  dummy_y1 = null;

  var dummy_y0 = dummy_y.substring(n/2,n);
  var y0 = parseInt(dummy_y0);
  dummy_y = null;

  var p = x1 + x0;
  var q = y1 + y0;

  var a   =   karatSuba(x1,y1);
  var b   =   karatSuba(x0,y0);
  var z1  =   karatSuba(a,Math.pow(bm,2));
  var z2  =   b;
  //var z3  =   karatSmul(bm ,((karatSmul(p,q) - a - b)));
  var z3  = bm * ((p*q) - (a) - (b)); 
  var z   =   z1 + z2 + z3;
  return z;

 }

console.log(karatSuba(344,100));

Answer 1

There are couple of mistakes in the way you have written the algorithm. Below code should work.

function karatSuba(x,y)
{

  var x1,x0,y1,y0,base,m;
  base  = 10;


  if((x<base)||(y<base)){
    console.log( " X - y = " , x,y, x*y)
    return x * y;
  }

  var dummy_x = x.toString();
  var dummy_y = y.toString();

  var n = (dummy_x.length > dummy_y.length) ? dummy_y.length : dummy_x.length;
  m = Math.round(n/2);



  var high1 = parseInt(dummy_x.substring(0,dummy_x.length-m));
  var low1 = parseInt(dummy_x.substring(dummy_x.length-m,dummy_x.length  )) ;

  var high2 = parseInt(dummy_y.substring(0,dummy_y.length-m)); 
  var low2 = parseInt(dummy_y.substring(dummy_y.length-m,dummy_y.length));


  var z0   =   karatSuba( low1, low2);
  var z1   =   karatSuba(low1+high1, low2+high2);
  var z2   =   karatSuba(high1,high2);

  var res  =   (z2 *  Math.pow(10, 2 * m )  ) + ( (z1-z2-z0) * Math.pow(10,  m )) + z0;

  return res;

 }

var a = 12345;
var b = 6789;
console.log(karatSuba(a,b));
console.log(a * b);