相关疑难解决方法(0)

将整数提升到C中另一个整数的幂的最有效方法是什么？

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

这里发生了什么:

#include <stdio.h>
#include <math.h>
int main(void) {
    printf("17^12 = %lf\n", pow(17, 12));
    printf("17^13 = %lf\n", pow(17, 13));
    printf("17^14 = %lf\n", pow(17, 14));
}

我得到这个输出:

17^12 = 582622237229761.000000
17^13 = 9904578032905936.000000
17^14 = 168377826559400928.000000

13和14与wolfram alpa cf 不匹配:

12: 582622237229761.000000
    582622237229761

13: 9904578032905936.000000
    9904578032905937

14: 168377826559400928.000000
    168377826559400929

而且,一些奇怪的部分并没有错 - 一个错了!

如果这是我达到pow()可以为我做什么的限制,有没有可以计算这个的替代方案？我需要一个可以计算的函数x^y,其中x^y始终小于ULLONG_MAX.

我正在考虑ax = 1 mod p用p prime 来解决一致性的算法.我在考虑使用费马定理.因为我知道

a ^ (p-1) = 1 mod p

然后

a ^ (p-1) = a * (a ^ (p-2))

这意味着这a ^ (p-2) mod p就是解决方案.不幸的是,这个解决方案虽然在数学上是正确的,但对于计算机并不好,因为对于我必须做的大素数,a ^ (p-2)这通常是不可计算的.

哪种算法对计算机科学有好处？