Почему функции модульной экспоненциальности работают по-разному в Python и Javascript для больших чисел?

Question

Мне нужно выполнить модульное возведение в степень на довольно больших числах как на python3, так и на javascript. У меня есть функции, которые выполняют эту задачу, но они дают мне разные результаты.

Python (все три работы точно так же):

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 (обе функции работают точно так же):

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 

И к тому же, когда я this service с моими номерами, я также получил 138693107570.

---

Почему это происходит? Я даже не знаю, какой вариант сейчас правильный. Однако на меньших числах функции дают одинаковые результаты.

Возможно ли как-то получить тот же результат от функций? Это даже не так важно, что результат математически корректен, результаты должны быть по крайней мере одинаковыми.

Не могли бы вы объяснить, почему это происходит? Это дизайн функции? Для меня функции на обоих языках кажутся одинаковыми.

Есть ли способ получить тот же результат от функций обоих языков?

Answer 1

Результат Python правильный.

Python использует целочисленное представление произвольной точности, в то время как Javascript хранит все числа как 64-разрядную плавучую точку IEEE754 (и временно принуждает их к 32-разрядным целым для побитовых операций). Это означает, что для больших целых чисел код Javascript начинает терять точность, в то время как код Python поддерживает точные значения всех результатов во всех вычислениях.

Если вы хотите обрабатывать большие целые числа точно в Javascript, вам нужно будет использовать an appropriate library. В качестве альтернативы, вы говорите, что вас не волнует правильный результат. Это действительно странно, чего не волнует, но если вы действительно так себя чувствуете:

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

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