Javascript самодельный pow с модулем

Я получил этот код, написанный на JavaScript, но он возвращает неправильное число для больших входных данных.
Он должен вычислять основание в степени экспоненты (ex) по модулю (mo).
Я написал эквивалентный код на C и работает. Пожалуйста, может кто-нибудь сказать мне, что не так.
Попробуйте проверить теорему Ферма по модулю 10^9 +7.

function powFun(base, ex, mo) {
    var r;
    if(ex === 0) 
        return 1;
    else if(ex % 2 === 0) {
        r = powFun(base, ex/2, mo) % mo ;
        return (r * r) % mo;
    }else 
        return (base * powFun(base, ex - 1, mo)) % mo;
}

javascript algorithm pow
person Sim    schedule 03.06.2015    source источник
comment
пожалуйста, добавьте некоторые тестовые данные. на каком входе он терпит неудачу и каков ожидаемый результат?   -  person Luboš Turek    schedule 04.06.2015
comment
Насколько велики числа? См. stackoverflow.com/questions/307179/ для максимального целого числа, которое может быть точно представлено в JS.   -  person Barmar    schedule 04.06.2015
comment
входные значения: base = 4, ex = 1000000006, mo = 1000000007.   -  person Sim    schedule 04.06.2015
comment
Вы пробовали mathjs.org?   -  person lmcarreiro    schedule 04.06.2015
comment
я решил проблему в C, мне просто любопытно, почему это не работает в javascript.   -  person Sim    schedule 04.06.2015
comment
Прочитайте страницу, на которую ссылается @Barmar — Javascript может обрабатывать только целые числа размером до 53 бит. Чтобы правильно рассчитать модульные продукты, наибольший модуль, с которым вы можете работать, равен 2 ^ (53/2) = 94906265. Это намного меньше, чем 10 ^ 9 + 7. Таким образом, вам нужно либо найти библиотеку Javascript, которая поддерживает большие целые числа, или напишите свои собственные процедуры.   -  person r3mainer    schedule 04.06.2015
comment
2^(53/2) = 94906265 — как вы получили эти числа?   -  person Sim    schedule 04.06.2015
comment
@squeamishossifrage: разве это не будет (2^53)/2 ? (или 2^(53-1))   -  person slebetman    schedule 04.06.2015
comment
@slebetman Так бы и было, если бы алгоритм работал путем сложения чисел. Вы можете вычислить (r+r)%m без переполнения, если r является 52-битным числом, но для вычисления (r*r)%m вы получите переполнение перед тем, как взять модуль, если r является 27-битным числом.   -  person r3mainer    schedule 04.06.2015
comment
@squeamishossifrage: А, хорошо. Я понимаю. Я забыл, что результат операции двоичного умножения в два раза превышает количество битов входных данных.   -  person slebetman    schedule 04.06.2015
comment
@Sim: 53/2 потому что операции умножения в двоичном формате приводят к удвоению количества битов входных данных. Таким образом, единственными безопасными входными данными являются 53/2 биты.   -  person slebetman    schedule 04.06.2015

Ответы (1)


arrow_upward
1
arrow_downward

Переполнение происходит в этой строке:

return (r * r) % mo;

Обратитесь к ответам на этот вопрос для некоторых простых алгоритмов для реализации a*a mod n без переполнения. Я адаптировал один из ответов на Javascript ниже:

function addmod(x, y, n)
{
    // Precondition: x<n, y<n
    // If it will overflow, use alternative calculation
    if (x + y <= x) x = x - (n - y) % n;
    else x = (x + y) % n;
    return x;
}

function sqrmod(a, n)
{
    var b;
    var sum = 0;

    // Make sure original number is less than n
    a = a % n;

    // Use double and add algorithm to calculate a*a mod n
    for (b = a; b != 0; b >>= 1) {
        if (b & 1) {
            sum = addmod(sum, a, n);
        }
        a = addmod(a, a, n);
    }
    return sum;
}

function powFun(base, ex, mo) {
    var r;
    if(ex === 0) 
        return 1;
    else if(ex % 2 === 0) {
        r = powFun(base, ex/2, mo) % mo ;
        // return (r * r) % mo;
        return sqrmod(r, mo);
    }else 
        return (base * powFun(base, ex - 1, mo)) % mo;
}

result = powFun(4, 1000000006, 1000000007);

alert(result);

Чтобы поддерживать еще большие числа, используйте библиотеку, поддерживающую большие целые числа.

person samgak    schedule 04.06.2015
comment
Хороший ответ, но вам, вероятно, следует изменить первую строку addmod() на if (x + y <= x) x = (x - (n - y))%n; - person r3mainer; 04.06.2015