자바 스크립트에서 Karatsuba 곱셈을 구현 하시겠습니까?

Question

아래 코드를 사용하여 karatsuba algorithm을 구현하려고했습니다. x 및 y (매개 변수)의 자릿수가 recursive call과 일치하지 않으면이 문제는 다음 논리와 함께 작동하지 않습니다. 현재 x와 y의 자릿수가 같을 때 올바른 출력을 얻고 있습니다.

정확하게 말하면, 문제는 z1과 z3의 계산에서 시작한다고 생각합니다. x와 y의 자릿수가 자주 일치하지 않기 때문입니다.

m을 정의하는 방법에 대한 논리를 이끌어 내면 혼란스러워하며 여기에 기반을두고 있습니다. 내 문제와 관련하여 명확하게 밝히고있다. (자바 스크립트에서 방금 여행을 시작했을 때 더 많은 최적화 제안이 도움이 될 것입니다.)

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