Беззнаковое переполнение Long Int при расчете Pow - PullRequest
Новая
       23

Беззнаковое переполнение Long Int при расчете Pow

0 голосов
/ 10 мая 2018

Я пытаюсь сделать функцию, которая быстро вычисляет x ^ y mod z.Он хорошо работает при расчете чего-то вроде 2 ^ 63 mod 3, но при 2 ^ 64 mod 3 и более высоких показателях он просто возвращает 0.

Я подозреваю, что переполнение где-то, но я не могу определить это.Я пробовал явное приведение в тех местах, где выполняются вычисления (* и mod), я также сделал свои переменные хранения (resPow, curPow) unsigned long long int (как предложено здесь ), но этоне сильно помогло. 

typedef unsigned long int lint;

lint fastpow(lint nBase, lint nExp, lint nMod) { 
    int lastTrueBit = 0;
    unsigned long long int resPow = 1ULL;

    unsigned long long int curPow = nBase;
    for (int i = 0; i < 32; i++) {
        int currentBit = getBit(nExp, i);

        if (currentBit == 1) {
            for (lint j = 0; j < i - lastTrueBit; j++) {
                curPow = curPow * curPow;
            }
            resPow =resPow * curPow;
            lastTrueBit = i;
        }
    }
    return resPow % nMod;
}

1 Ответ

0 голосов
/ 10 мая 2018

Я подозреваю, что переполнение где-то,

Да, и curPow * curPow, и resPow * curPow могут математически переполняться.

Обычный способ сдерживания переполнения здесьдля выполнения mod на промежуточных продуктах. 

        // curPow = curPow * curPow;
        curPow = (curPow * curPow) % nMod;
    // resPow =resPow * curPow;
    resPow = (resPow * curPow) % nMod;

Этого достаточно, когда nMod < ULLONG_MAX/(nMod - 1).(Значение мода составляет половину точности unsigned long long).В противном случае требуются более крайние меры, такие как: Модульное возведение в степень без ограничения диапазона .

Незначительные вещи

for(int i = 0; i < 32; i++) предполагает, что lint/unsigned long составляет 32 бита.Переносимый код позволит избежать этого магического числа .unsigned long - это 64-битная версия на разных платформах.

LL здесь не требуется.U остается полезным для подавления различных предупреждений компилятора. 

// unsigned long long int resPow = 1ULL;
unsigned long long int resPow = 1U;
...