Fastest way to compute (n + 1)^j from (n^j)

Question

I need to compute 0^j, 1^j, ..., k^j for some very large k and j (both in the order of a few millions). I am using GMP to handle the big integer numbers (yes, I need integer numbers as I need full precision). Now, I wonder, once I have gone through the effort of computing n^j, isn't there a way to speed up the computation of (n + 1)^j, instead of starting from scratch?

Here is the algorithm I am currently using to compute the power:

mpz_class pow(unsigned long int b, unsigned long int e)
{
    mpz_class res = 1;
    mpz_class m = b;

    while(e)
    {
        if(e & 1)
        {
            res *= m;   
        }

        e >>= 1;
        m *= m;
    }

    return res;
}

As you can see, every time I start from scratch, and it takes a lot of time.

Answer 1

To compute n^j, why not find at least one factor of n, say k perform n^j = k^j * (n/k)^j ? By the time n^j is being computed, both k^j and (n/k)^j should be known.

However the above takes potentially O(sqrt(n)) time for n. We have a computation of n^j independently in O(log(j)) time by Exponentiation by Squaring as you have mentioned in the code above.

So you could have a mix of the above depending on which is larger:

1. If n is much smaller than log(j), compute n^j by factorization.

2. Whenever n^j is known compute {(2*n)^j, (3*n)^j, ..., ((n-1)*n)^j, n * n^j} and keep it in a lookup table.

3. If n is larger than log(j) and a ready computation as above is not possible, use the logarithmic method and then compute the other related powers like above.

4. If n is a pure power of 2 (possible const time computation), compute the jth power by shifting and calculate the related sums.

5. If n is even (const time computation again), use the factorization method and compute associated products.

The above should make it quite fast. For example, identification of even numbers by itself should convert half of the power computations to multiplications. There could be many more thumb rules that could be found regarding factorization that could reduce the computation further (especially for divisibility by 3, 7 etc)