在 C 中计算 10 的整数幂比 pow() 更快吗？

Question

我知道 2 的幂可以使用 << 运算符来实现。 10的幂呢？像 10^5？有没有比 C++ 中的 pow(10,5) 更快的方法？这是一个非常简单的手动计算。但是由于数字的二进制表示，计算机似乎并不容易……让我们假设我只对整数幂 10^n 感兴趣，其中 n 是整数。

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

Answer 1

像这样的东西：

 int quick_pow10(int n)
{
    static int pow10[10] = {
        1, 10, 100, 1000, 10000,
        100000, 1000000, 10000000, 100000000, 1000000000
    };

    return pow10[n];
}

显然，可以为 long long 做同样的事情。

这应该比任何竞争方法快几倍。然而，如果你有很多基数，它是非常有限的（尽管随着基数的增加值的数量会急剧下降），所以如果没有大量的组合，它仍然是可行的。

作为对比：

 #include <iostream>
#include <cstdlib>
#include <cmath>

static int quick_pow10(int n)
{
    static int pow10[10] = {
        1, 10, 100, 1000, 10000,
        100000, 1000000, 10000000, 100000000, 1000000000
    };

    return pow10[n];
}

static int integer_pow(int x, int n)
{
    int r = 1;
    while (n--)
       r *= x;

    return r;
}

static int opt_int_pow(int n)
{
    int r = 1;
    const int x = 10;
    while (n)
    {
        if (n & 1)
        {
           r *= x;
           n--;
        }
        else
        {
            r *= x * x;
            n -= 2;
        }
    }

    return r;
}

int main(int argc, char **argv)
{
    long long sum = 0;
    int n = strtol(argv[1], 0, 0);
    const long outer_loops = 1000000000;

    if (argv[2][0] == 'a')
    {
        for(long i = 0; i < outer_loops / n; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                sum += quick_pow10(n);
            }
        }
    }
    if (argv[2][0] == 'b')
    {
        for(long i = 0; i < outer_loops / n; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                sum += integer_pow(10,n);
            }
        }
    }

    if (argv[2][0] == 'c')
    {
        for(long i = 0; i < outer_loops / n; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                sum += opt_int_pow(n);
            }
        }
    }

    std::cout << "sum=" << sum << std::endl;
    return 0;
}

使用 g++ 4.6.3 编译，使用 -Wall -O2 -std=c++0x ，得到以下结果：

 $ g++ -Wall -O2 -std=c++0x pow.cpp
$ time ./a.out 8 a
sum=100000000000000000

real    0m0.124s
user    0m0.119s
sys 0m0.004s
$ time ./a.out 8 b
sum=100000000000000000

real    0m7.502s
user    0m7.482s
sys 0m0.003s

$ time ./a.out 8 c
sum=100000000000000000

real    0m6.098s
user    0m6.077s
sys 0m0.002s

（我也有使用 pow 的选项，但我第一次尝试时花了 1m22.56s，所以当我决定优化循环变体时我删除了它）

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

Answer 2

基于 constexpr 函数的通用表生成器。浮点部分需要 c++20 和 gcc，但非浮点部分适用于 c++17。如果将“auto”类型参数更改为“long”，则可以使用 c++14。未正确测试。

 #include <cstdio>
#include <cassert>
#include <cmath>

// Precomputes x^N
// Inspired by https://stackoverflow.com/a/34465458
template<auto x, unsigned char N, typename AccumulatorType>
struct PowTable {
    constexpr PowTable() : mTable() {
        AccumulatorType p{ 1 };
        for (unsigned char i = 0; i < N; ++i) {
            p *= x;
            mTable[i] = p;
        }
    }

    AccumulatorType operator[](unsigned char n) const {
        assert(n < N);
        return mTable[n];
    }

    AccumulatorType mTable[N];
};

long pow10(unsigned char n) {
    static constexpr PowTable<10l, 10, long> powTable;
    return powTable[n-1];
}

double powe(unsigned char n) {
    static constexpr PowTable<2.71828182845904523536, 10, double> powTable;
    return powTable[n-1];
}

int main() {
    printf("10^3=%ld\n", pow10(3));
    printf("e^2=%f", powe(2));
    assert(pow10(3) == 1000);
    assert(powe(2) - 7.389056 < 0.001);
}

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