This post is an attempt to be more clear about the technique for using the BigInteger class in the SumOfPowers program.

First of all, after a fair amount of effort, the SumOfPowers program ended up having simple and clear logic and it was/is FAST! And it was FAST mainly due to its use of Math.Pow() for finding the Nth root of integers. I don’t know what goes on behind the scenes but thru experimentation I determined that Math.Pow() can approximate Nth roots of an integer X very quickly. And you can then use the resulting approximation to very quickly determine if X has an Nth root that is also an integer. Keep in mind that determining whether some integer X has an Nth root that is also an integer is what the SumOfPowers program is all about!

To enhance the SumOfPowers program to support BIG NUMBERS (greater than 2^64) I decided to use the BigInteger class. But there were problems.

- BigInteger is slow.
- BigInteger does NOT have a Pow() method for calculating (or approximating) Nth roots.

So what to do? It eventually occurred to me to “convert” a BigInteger into 2 or more “normal” **long** integers that Math.Pow() could then be applied against. So let’s say we have

A^{n} + B^{n} + C^{n }_{= }X where X > 2^{64}

we want to know whether X has an nth root that is an integer.

let X == X * (L/L) where L == 2^{64}

then X == (X/L) * L

Now from basic math we know that

Nth root of ( A*B ) == (Nth root of A) * (Nth root of B); so…

Nth root of X == (Nth root of X/L) * (Nth root of L);

Now if we apply BigInteger.DivRem() against X/L

BigInteger biQ;

BigInteger biR;

biQ = BigInteger.DivRem(X, L, out biR);

long **A **= (long)biQ + ( (long) biR/L );

long **B** = (long) L;

Now we have the A and B parts of Nth root of ( A*B ) == (Nth root of A) * (Nth root of B) and both A and B are < 2^{64 }so we can achieve our goal of using Math.Pow() against them to find their Nth roots.

long lNthRootOfA = (long)Math.Pow(lA, (1.0 / nExponent));

long lNthRootOfB = (long)Math.Pow(L, (1.0 / nExponent));

If we convert the product of these back into a BigInteger then we can, in just a couple of simple trial-and-error computations determine whether or not there is an integer solution for the Nth root of X keeping in mind that our goal was to:

Determine whether X has an nth root that is an integer for something like:

A^{n} + B^{n} + .. C^{n }_{= }X where X > 2^{64}

or in other words whether there’s an integer I such that

A^{n} + B^{n} + .. C^{n }_{= }I^{n} where I^{n} > 2^{64}

Another huge benefit to all the above is that it required only minor changes to the code! Once the technique was understood using pencil and paper then the actual implementation was mostly just cutting and pasting of existing code to create a BigInteger code path and a BigInteger processing option on the screen/form.

As mentioned in the prior post, I said “to get A and B small enough to be <= 2^{64 } ?” It may not be obvious but If you think about it you may realize that this means that the largest X (sum) this new BigInteger version could handle is (2^{64 }) * (2^{64 }) or 2^{128 }. With a little more effort we could make it handle much bigger numbers but this is good enough for me (It’s a hobby!).

************** end of post *****************

## Leave a Reply