比pow()更快的速度来计算C++中的整数幂10？

Question

我知道2的幂可以使用<<运算符来实现.10的力量怎么样？喜欢10 ^ 5？在C++中有没有比pow(10,5)更快的方法？这是一个非常直接的计算手工.但由于数字的二进制表示,计算机似乎并不容易......让我们假设我只对整数幂,10 ^ n感兴趣,其中n是整数.

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,所以当我决定优化循环变体时我删除了它)

Answer 2

有一些方法可以比使用更快地计算10的整数幂std::pow()!第一个实现是pow(x, n)可以在O(log n)时间内实现.下一个实现就是pow(x, 10)一样(x << 3) * (x << 1).当然,编译器知道后者,即,当您将整数乘以整数常量10时,编译器将执行最快的任何乘以10.根据这两个规则,很容易创建快速计算,即使x是一个大整数类型.

如果你对这样的游戏感兴趣:

1. 在编程元素中讨论了通用的O(log n)版本的功率.
2. Hacker's Delight讨论了很多有趣的"整数"技巧.

Answer 3

使用模板元编程的任何基础的解决方案:

template<int E, int N>
struct pow {
    enum { value = E * pow<E, N - 1>::value };
};

template <int E>
struct pow<E, 0> {
    enum { value = 1 };
};

然后它可以用于生成可在运行时使用的查找表:

template<int E>
long long quick_pow(unsigned int n) {
    static long long lookupTable[] = {
        pow<E, 0>::value, pow<E, 1>::value, pow<E, 2>::value,
        pow<E, 3>::value, pow<E, 4>::value, pow<E, 5>::value,
        pow<E, 6>::value, pow<E, 7>::value, pow<E, 8>::value,
        pow<E, 9>::value
    };

    return lookupTable[n];
}

这必须与正确的编译器标志一起使用,以便检测可能的溢出.

用法示例:

for(unsigned int n = 0; n < 10; ++n) {
    std::cout << quick_pow<10>(n) << std::endl;
}

Answer 4

整数幂函数（不涉及浮点转换和计算）很可能比pow()：

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

    return r; 
}

编辑：基准测试 - 朴素的整数取幂方法似乎比浮点数高出大约两倍：

h2co3-macbook:~ h2co3$ cat quirk.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
#include <string.h>
#include <math.h>

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

    return r; 
}

int main(int argc, char *argv[])
{
    int x = 0;

    for (int i = 0; i < 100000000; i++) {
        x += powerfunc(i, 5);
    }

    printf("x = %d\n", x);

    return 0;
}
h2co3-macbook:~ h2co3$ clang -Wall -o quirk quirk.c -Dpowerfunc=integer_pow
h2co3-macbook:~ h2co3$ time ./quirk
x = -1945812992

real    0m1.169s
user    0m1.164s
sys 0m0.003s
h2co3-macbook:~ h2co3$ clang -Wall -o quirk quirk.c -Dpowerfunc=pow
h2co3-macbook:~ h2co3$ time ./quirk
x = -2147483648

real    0m2.898s
user    0m2.891s
sys 0m0.004s
h2co3-macbook:~ h2co3$