Karatsuba

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.For example, the Karatsuba algorithm requires 310 = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the traditional algorithm requires (210)2 = 1,048,576 (a speedup of 17.75 times). The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n.

function karatsuba(x,y)
{
  //Logic
  var xlen = x.toString(10).length;
  var ylen = y.toString(10).length;
  var n = Math.max(xlen, ylen);

  if(n < 10)
  {
    return x*y;
  }
  n = (n / 2) + (n % 2);
  //Refer to Power Post for details of the function
  var multiplier = power(10, n);
  var b = x / multiplier;
  var a = x - b*multiplier;
  var d = y / multiplier;
  var c = y - d*n;
  var z0 = karatsuba(a, c);
  var z1 = karatsuba(a + b, c + d);
  var z2 = karatsuba(b, d);
  return (z0 + ((z1 - z0 - z2) * multiplier) + (z2*Math.pow(0, 2*n)));
}