It Begs The Question
Hey…I'm just saying… And while we're at it, why are you defending them?

SumOfPowers BIG NUMBERS – More Clarity February 20, 2015

 

BigIntegerNotes

Original Notes

 

 

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

 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  <   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 *****************

 


Categories Uncategorized
  1. Jacob Kayos Code says:

    Good explanation. Deft application of the simple. My first reaction would have been to code one of the many root finding algorithms (e.g. one of the Newton’s or a derivative) but this attack was simple and elegant. So was the testing method mentioned in the prior big number post.

    I’m also curious about how Math.Pow() works. Please post it if you find out (I’m subscribed so I will get notified). Thanks in advance.

    Jacob

  2. me too says:

    I’m curious too about math.pow.

Leave a Reply

Your email address will not be published. Required fields are marked *