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
An + Bn + Cn = X where X > 264
we want to know whether X has an nth root that is an integer.
let X == X * (L/L) where L == 264
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
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 < 264 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:
An + Bn + .. Cn = X where X > 264
or in other words whether there’s an integer I such that
An + Bn + .. Cn = In where In > 264
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 <= 264 ?” 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 (264 ) * (264 ) or 2128 . 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 *****************