Karatsuba Multiplication

[nitin42]

Can provide the code for karatsuba multiplication (<=20 lines).

[ovidiuch]

Sounds good. I'll keep the thread open if you post it here and label it with something like visualisation needed.

[nitin42]

Here is the code

function karatsubaMulti(x, y) {
  let n = Math.min(('' + x).length, ('' + y).length); // Implicit coercision

  if(n == 1)
    return x * y;

  let bm = Math.pow(10, parseInt(n / 2));
  let bm2 = Math.pow(10, 2 * parseInt(n / 2));
  let a = parseInt(x / bm);
  let b = x % bm;
  let c = parseInt(y / bm);
  let d = y % bm;

  let caller = arguments.callee; // For recursive call, not using TCO
  return bm2 * caller(a, c) + bm * (caller(a, d) + caller(b, c)) + caller(b, d);
}

let a = karatsubaMulti(12345, 6789);
console.log(a); // 83810205

Works fine but exceeds the maximum call stack size when arrow functions are used instead.

[vmasto]

Just a heads up that arguments.callee is not allowed in strict mode.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/arguments/callee

[nitin42]

Oh ! Thanks for pointing this. I'll rewrite the code 😄