如何在javascript中实现Karatsuba乘法？

Question

我尝试使用以下代码实现karasuba 算法。当 x 和 y（参数）中的位数不匹配时，问题就开始了，因为recursive call在这种情况下，以下逻辑不起作用。到目前为止，当 x 和 y 中的位数相同时，我得到正确的输出。

更准确地说，我认为问题始于 z1 和 z3 的计算，因为这是 x 和 y 的位数经常不匹配的地方。

m我也对推导如何定义此处的基础力量的逻辑感到有点困惑。我相信我的问题已经说清楚了吗？（任何关于更多优化的建议都会更有帮助，因为我刚刚开始我的 java 脚本之旅）。

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

您编写算法的方式存在一些错误。下面的代码应该可以工作。

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