为什么对于大数，模幂运算在Python和Javascript中的工作方式不同? [英] Why Modular Exponentiation functions work differently in Python and Javascript for large numbers?

问题描述

我需要在python3和javascript上对相当大的数字执行模幂运算.我有执行任务的函数，但是它们给了我不同的输出.

I need to perform modular exponentiation on quite large numbers on both python3 and javascript. I have functions that do the task, but they give me different outputs.

Python(这三个工具都以相同的方式工作):

Python (all of the three work in the same way):

pow(176672119508, 55, 200000023499)

def expmod_iter(a,b,c):
    x = 1
    while(b>0):
        if(b&1==1): x = (x*a)%c
        a=(a*a)%c
        b >>= 1
    return x%c

def pow_mod(x, y, z):
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number

# The result is always 124912252967

和现在的JavaScript(两个函数以相同的方式工作):

and now JavaScript (both functions work in the same way):

function powMod(x, y, z) {
  let number = 1;
  while (y) {
      if (y & 1) {
          number = number * x % z;
      }
      y >>= 1;
      x = x * x % z;
  }
  return number;
}

function expmod_iter(a, b, c) {
  let x = 1;

  while (b > 0) {
    if (b & 1 === 1) {
      x = (x * a) % c;
    }
    a = (a * a) % c;
    b >>= 1
  }
  return x % c;
}

console.log(powMod(176672119508, 55, 200000023499));
console.log(expmod_iter(176672119508, 55, 200000023499));

// The result is always 138693107570

此外，当我使用此服务时用我的电话号码，我还得到了138693107570.

And moreover, when I used this service with my numbers, I also got 138693107570.

为什么会这样?我什至不知道现在哪个变体是正确的.但是，对于较小的数字，这些函数可以提供相同的结果.

Why does this happen? I'm not even sure what variant is correct now. However, on smaller numbers the functions give identical results.

是否有可能以某种方式从这些函数中获得相同的结果?结果在数学上是正确的，甚至无关紧要，结果应该至少是相同的.

Is it possible to somehow get the same result from the functions? It doesn't even matter that much that the result is mathematically correct, the results should be at least the same.

能否请您解释为什么会这样?是功能设计吗?对我来说，两种语言的功能似乎都是相同的.

Could you please explain why this happens? Is it the function design? To me, functions on both languages seem to be identical.

是否可以通过两种语言的功能获得相同的结果?

Is there a way to get the same result from functions of both languages?

推荐答案

Python的结果正确.

Python's result is correct.

Python使用任意精度的整数表示形式，而Javascript将所有数字存储为IEEE754 64位浮点数(并临时将其强制转换为32位整数以进行按位运算).这意味着对于大整数，Javascript代码开始失去精度，而Python代码在整个计算过程中保持所有结果的精确值.

Python uses an arbitrary-precision integer representation, while Javascript stores all numbers as IEEE754 64-bit floating point (and temporarily coerces them to 32-bit integers for bitwise operations). This means that for large integers, the Javascript code starts losing precision, while the Python code maintains the exact values of all results throughout the calculation.

如果您想完全使用Javascript处理大整数，则需要使用库.另外，您说您不太在乎结果是否正确.这是一件很奇怪的事情，不用关心，但是如果您真的有这种感觉:

If you want to handle large integers exactly in Javascript, you will need to use an appropriate library. Alternatively, you say you don't care much about the result being correct. That is a really weird thing to not care about, but if you really feel that way:

# Python
def wrongpow(a, b, c):
    return 0

// Javascript
function wrongpow(a, b, c) {
    return 0;
}

这篇关于为什么对于大数，模幂运算在Python和Javascript中的工作方式不同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！