4

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.

Matteo Monti
  • 8,362
  • 19
  • 68
  • 114
  • You should apply the dynamic programming since `5^2 = 4^2 + 3^2` >> [Fibonacci](http://algorithms.tutorialhorizon.com/introduction-to-dynamic-programming-fibonacci-series/) , in order to minimize the calculation as possible – Null Jan 28 '17 at 09:50
  • I think you lost me...? Can you elaborate a bit more? – Matteo Monti Jan 28 '17 at 09:51
  • don't you agree that `b^e = (b-1)^e + (b-2)^e` ? – Null Jan 28 '17 at 09:53
  • 2
    @Null You mean like 7^2 = 6^2 + 5^2? – user3386109 Jan 28 '17 at 09:55
  • @Null - user3386109 has provided a counter-example. – Peter Jan 28 '17 at 09:56
  • 1
    I'd suggest you post this question on http://math.stackexchange.com. Programmers, as you see, don't have much sense of maths :) – GOTO 0 Jan 28 '17 at 09:57
  • 1
    @Null `5^2 * 4^2 + 3^2` because `(3, 4, 5)` is a Pythagorean triple.. – Matteo Monti Jan 28 '17 at 09:58
  • Please have your question show what information might be available to `pow()` in addition to `b` and `e`. If it was `b**(e-1)`, this didn't look drab -? – greybeard Jan 28 '17 at 10:00
  • Well, if it was a matter of computing `b^(e - 1)` from `b^e`, I agree that it would be quite easy, as it would reduce to dividing by `b`. But my issue here is computing `(b - 1)^e`, the exponent will need to stay the same. – Matteo Monti Jan 28 '17 at 10:02
  • I wasn't suggesting to compute something else. I request specifying what information is available, giving an example that would have made the question moot. I understood `(b - 1)^e` was available to compute "b^e" - what about "(b-2)^e", …? What _will be available_? Will there be a fixed limit on the amount of input? For any _fixed_ `j`/`e`, there will be non-trivial formulae _in lower powers_, I guess. – greybeard Jan 28 '17 at 10:21

2 Answers2

1

You may want to use the binomial expansion of (n+1)^j as n^j + jn^(j-1)+j(j-1)/2 * n^(j-2) +... + 1 and memoize lower powers already computed and reuse them to compute (n+1)^j in O(n) time by addition. If you compute the coefficients j, j*(j-1)/2,... incrementally while adding each term, that can be done in O(n) too.

Sandipan Dey
  • 21,482
  • 2
  • 51
  • 63
  • 1
    This sounds like a great solution. Sadly, it will also require a huge amount of memory. Each number in the order of `2000000^2000000` will require around `8 MB` to be stored, and I can't afford `1 TB` or RAM... – Matteo Monti Jan 28 '17 at 10:07
  • 1
    May be then we can use 2^j*((n+1)/2)^j, when n is odd, 2^j can be computed by just left shift. – Sandipan Dey Jan 28 '17 at 10:17
  • What if we have some disk operations too, are we going to optimize for speed too? – Sandipan Dey Jan 28 '17 at 10:18
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)

Community
  • 1
  • 1
user1952500
  • 6,611
  • 3
  • 24
  • 37