javascript - karatsuba 算法，超出最大调用堆栈大小

Question

我正在编写自己的 karatsuba algh 变体，但无法使其与真正的大整数一起使用

'use strict';

const karatsuba = function (x, y) {
  if (x < 10 || y < 10) return x * y;

  const strX = String(x);
  const strY = String(y);

  const n = Math.min(strX.length, strY.length);
  const m = Math.ceil(n / 2);

  const leftX = strX.slice(0, strX.length - m),
        rightX = strX.slice(strX.length - m, strX.length),

        leftY = strY.slice(0, strY.length - m),
        rightY = strY.slice(strY.length - m, strY.length);

  const prod1 = karatsuba(leftX, leftY),
        prod2 = karatsuba(rightX, rightY),
        prod3 = karatsuba(addAny(leftX, rightX), addAny(leftY, rightY));

  const a = prod1 + String(Math.pow(10, 2 * m)).slice(1),
        b = (prod3 - prod1 - prod2) + String(Math.pow(10, m)).slice(1),
        ab = addAny(a, b);

  return addAny(ab, prod2);
};

function addAny(a, b) {
  const MAX_INT = 9007199254740992,
      intA = parseInt(a),
      intB = parseInt(b);

  if ((intA + intB) < MAX_INT) return intA + intB;

  return sumStrings(a + '', b + '');
}



function sumStrings(a, b) {
  let res = '', c = 0;

  a = a.split('');
  b = b.split('');

  while (a.length || b.length || c) {
    c += ~~a.pop() + ~~b.pop();
    res = c % 10 + res;
    c = c > 9;
  }

  return res.replace(/^0+/, '');
}

它适用于像 3957322621233333 和 5548313756335578 这样的整数 但是当我尝试将它与大整数一起使用时，如 76715432964249374812219365555 和 32141964835273822784327848699719 代码崩溃

RangeError: Maximum call stack size exceeded

Answer 1

你在调用中省略了引号，对吗？

> katsuba(76715432964249374812219365555,32141964835273822784327848699719)
RangeError: Maximum call stack size exceeded
    at karatsuba (repl:2:5)
    at karatsuba (repl:16:15)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)
    at karatsuba (repl:17:9)

76715432964249374812219365555 大于 5**53，即代码中的 MAX_INT。数字文字被隐式转换为 float 7.671543296424938e+28，您的算法会因数字格式而窒息。

然而，你的实现有一些错误，因为即使你使用字符串文字，计算结果也是错误的:

> karatsuba('76715432964249374812219365555', '32141964835273822784327848699719')
'1045731853714033916818600413783559075'

代替

'2465784748659709650840276767201870909665028593909797886779045'