c - Unsigned Long Int 在计算 pow 时溢出

Question

我正在尝试制作一个快速计算 x^y mod z 的函数。它在计算 2^63 mod 3 之类的东西时效果很好，但在 2^64 mod 3 和更高的指数下它只返回 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 位。可移植代码将避免那个魔数(Magic Number)。 unsigned long在各种平台上都是 64 位的。

LL这里不需要。 U对于消除各种编译器警告仍然有用。

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