如何计算 2 的 10000000 次方

Question

如何在不使编译器崩溃的情况下计算 2 的 10000000 次幂。 c/c++ 中超大整数的数据类型应该是什么。

原文由 Prashant 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

对于非常具体的值 2 提高到 1000 double 就足够了。

 #include <stdio.h>
#include <math.h>

int main(int argc, const char *argv[]) {
    printf("%f\n", pow(2., 1000));
    return 0;
}

但是，通常您需要实现任意精度乘法算法来计算那么大的数字（或使用提供该数字的库）。

C++ 没有针对这种计算的预定义标准函数。

如果您想实现自己的版本作为练习，那么我的建议是使用以 10000 为底的数字。它们足够小，一位数乘法不会溢出，并且将结果转换为十进制非常简单快捷结束，因为您可以将基数为 10000 的数字映射为十进制，而不必实现除法模数。

同样要计算如此大的幂（10,000,000），您需要通过平方来实现幂，即

BigNum pow(BigNum a, int b) {
    if (b == 0) {
        return 1;
    } else if (b & 1) {
        return a*pow(a, b-1);
    } else {
        BigNum x = pow(a, b/2);
        return x*x;
    }
}

这将允许计算 pow(a, b) 与 O(log(b)) 而不是 O(b) 乘法。

原文由 6502 发布，翻译遵循 CC BY-SA 3.0 许可协议