C 乘方求幂的实现

Question

我试图在 C 中实现 "exponentiation by squareing" 算法，但我的程序有一个奇怪的行为。首先，这是一个小代码片段：

long long fast_power_1(long long base, long long power){
    long long result = 1;
    while (power > 0)
    {
        if (power % 2 == 0)
        {
            power = power / 2;
            base = base * base;
        }
        else
        {
            power = power - 1;
            result = (result*base);
            power = power / 2;
            base = (base * base);
        }
    }
return result;}

如果我调用该函数：

printf("%d\n",fast_power_1(2,100));

我希望输出类似于 976371285，但结果是 0，我不太明白为什么。

Answer 1

long long 应该使用 %lld 格式说明符打印，否则它是未定义的行为。此外，对于 power 的大值，此方法已经溢出 - 因为 long long 不能保持 2^100（截至目前在 32 或 64 位系统中 - 当它是 128位系统当然可以）。

截至目前，在您的代码中，如果您提供的指数值不是太大并使用 printf("%lld",..)，那么它会给您一个有效的结果。

也许您想对其进行模块化运算。（一般要求就此止步——比如对一些大素数进行模运算，即 10^9+7 ）。

C 乘方求幂的实现

C implementation of exponentiation by squaring

c

algorithm

performance

computation-theory