如何在javascript中实现唐津乘法 [英] How to implement Karatsuba Multiplication in javascript?

问题描述

我尝试使用以下代码实现 karatsuba算法.当x和y中的位数(参数)不匹配时，问题开始，因为在以下情况下recursive call在这种情况下不起作用.截至目前，当x和y中的位数相同时，将获得正确的输出.

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.

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

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.

对于派生如何定义m的逻辑(这是这里的基础的力量)，我也有些困惑.我相信我的问题很明确吗? (由于我刚刚开始使用Java脚本，因此任何有关优化的建议都会更有帮助.)

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

推荐答案

您编写算法的方式有两个错误.下面的代码应该可以工作.

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

这篇关于如何在javascript中实现唐津乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！