Unsigned Long Int 在计算 pow 时溢出

Question

我正在尝试制作一个可以快速计算 x^y mod z 的函数。它在计算 2^63 mod 3 之类的东西时效果很好，但在 2^64 mod 3 和更高的指数时它只是 returns 0。

我怀疑某处溢出，但无法确定。我在进行计算 (* 和 mod) 的地方尝试了显式转换，我还制作了我的存储变量 (resPow、curPow) unsigned long long int（如建议的那样here) 但这并没有多大帮助。

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;
}

Answer 1

I am suspecting an overflow somewhere,

是的，curPow * curPow 和 resPow * curPow 都可能在数学上溢出。

这里遏制溢出的常用方法是对中间产品执行mod。

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

当nMod < ULLONG_MAX/(nMod - 1)时，这就足够了。（mod 值是 unsigned long long 精度的一半）。否则需要采取更极端的措施，如：Modular exponentiation without range restriction.

小东西

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;

Unsigned Long Int 在计算 pow 时溢出

Unsigned Long Int overflow when calculating pow

c

multiplication

unsigned-long-long-int

exponential