Javascript中的平方模幂运算不能正常工作？

Question

在过去的几个小时里，我一直在尝试用Javascript实现Exponentiation by squaring。基本上，我一直在尝试应用Fermat Little Theorem来求解模乘逆。它看起来应该是直截了当的，但我得到了不正确的结果：

const MAX = 10**9 + 7
const inv2 = expBySquare(2, MAX-2)
// inv2 should be 500000004 but is 437533240

function expBySquare(x, n) {
  if (n < 0) throw 'error'
  if (n === 0) return 1
  if (n === 1) return x

  if (n % 2 === 0) return expBySquare((x * x) % MAX, n / 2) % MAX
  return (x * expBySquare((x * x) % MAX, (n - 1) / 2)) % MAX
}

我刚刚尝试用C https://onlinegdb.com/H1tsx4TY7实现这个算法，它工作起来没有任何问题。我知道我应该预料到JS中的溢出问题，但我认为它可以处理这些数字，因为在所有的弱点中都使用了模。

Answer 1

JavaScript数字始终使用64位浮点格式。因此，您只能使用52位的尾数，它给您提供了有效的53位。您的场景中的中间值超过了这些值，这将引入舍入误差。第一次发生这种情况的是279,632,277的平方。这应该是78,194,210,340,204,729 (57位)，但会四舍五入为78,194,210,340,204,730。