Implementing Karatsuba Multiplication in javascrip

问题:

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 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.

Also am bit confused on 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));

回答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);

回答2:

function range(start, stop, step) {
    if (typeof stop == 'undefined') {
        // one param defined
        stop = start;
        start = 0;
    }
    if (typeof step == 'undefined') {
        step = 1;
    }
    if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) {
        return [];
    }
    var result = [];
    for (var i = start; step > 0 ? i < stop : i > stop; i += step) {
        result.push(i);
    }
    return result;
};
function zeroPad(numberString, zeros, left = true) {
    //Return the string with zeros added to the left or right.
    for (var i in range(zeros)) {
        if (left)
            numberString = '0' + numberString
        else
            numberString = numberString + '0'
    }

    return numberString
}
function largeMultiplcation(x, y) {
    x = x.toString();
    y = y.toString();

    if (x.length == 1 && y.length == 1)
        return int(x) * int(y)

    if (x.length() < y.length)
        x = zeroPad(x, y.length - x.length);

    else
        y = zeroPad(y, x.length - y.length);

    n = x.length
    j = Math.floor(n/2);

    //for odd digit integers
    if ( n % 2 != 0)
        j += 1    
    var BZeroPadding = n - j
    var AZeroPadding = BZeroPadding * 2

    a = parseInt(x.substring(0,j));
    b = parseInt(x.substring(j));
    c = parseInt(y.substring(0,j));
    d = parseInt(y.substring(j));

    //recursively calculate
    ac = LargeMultiplication(a, c)
    bd = LargeMultiplication(b, d)
    k = LargeMultiplication(a + b, c + d)
    A = int(zeroPad(str(ac), AZeroPadding, false))
    B = int(zeroPad(str(k - ac - bd), BZeroPadding, false))
    return A + B + bd
}