Any way faster than pow() to compute an integer power of 10 in C++?

Something like this:

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

    return pow10[n]; 
}

Obviously, can do the same thing for long long.

This should be several times faster than any competing method. However, it is quite limited if you have lots of bases (although the number of values goes down quite dramatically with larger bases), so if there isn't a huge number of combinations, it's still doable.

As a comparison:

#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;
}

Compiled with g++ 4.6.3, using -Wall -O2 -std=c++0x, gives the following results:

$ 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

(I did have an option for using pow as well, but it took 1m22.56s when I first tried it, so I removed it when I decided to have optimised loop variant)

There are certainly ways to compute integral powers of 10 faster than using std::pow()! The first realization is that pow(x, n) can be implemented in O(log n) time. The next realization is that pow(x, 10) is the same as (x << 3) * (x << 1). Of course, the compiler knows the latter, i.e., when you are multiplying an integer by the integer constant 10, the compiler will do whatever is fastest to multiply by 10. Based on these two rules it is easy to create fast computations, even if x is a big integer type.

In case you are interested in games like this:

1. A generic O(log n) version of power is discussed in Elements of Programming.
2. Lots of interesting "tricks" with integers are discussed in Hacker's Delight.

An integer power function (which doesn't involve floating-point conversions and computations) may very well be faster than pow():

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

    return r; 
}

Edit: benchmarked - the naive integer exponentiation method seems to outperform the floating-point one by about a factor of two:

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$ 

A solution for any base using template meta-programming :

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 };
};

Then it can be used to generate a lookup-table that can be used at runtime :

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];
}

This must be used with correct compiler flags in order to detect the possible overflows.

Usage example :

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