This post is about stuff related to enhancing the Sum Of Powers program to work for REALLY BIG NUMBERS and about related testing techniques. And in a sense it’s also about USEFUL TAUTOLOGIES.
How often does one even encounter “Useful Tautologies” let alone actually get to use one, even a really trivial one, in a real problem? There’s more about “Useful Tautologies” (aka lemmas) in this short post if you are interested. But I digress; back to the BIG NUMBERS story.
If you aren’t familiar with the Sum Of Powers program you can read these two prior posts first:
https://itbegsthequestion.com/sumofpowers/
https://itbegsthequestion.com/sum-of-powers-code-optimization/
Now we begin… A limitation of the prior version of the program was that the sum of the TERMs had to be less than 264 . Yes, that’s a BIG number
18,446,744,073,709,551,616
but historically it’s not big enough. For example, here is a counter example to Euler’s conjecture cited in Wikipedia:
555 + 31835 + 289695 + 852825 = 853595 (Frye, 2004).
Here’s a link http://en.wikipedia.org/wiki/Euler%27s_sum_of_powers_conjecture
In Microsoft’s C#, the largest integer available is 264 . There are some other “Big Number” libraries that are available to use integers/numbers of arbitrary size (i.e. HUGE) but the problem is that using these libraries in C# is a pain in the ass (so I read) so I did not want to use them. However, Microsoft does have a BigInteger class that’s available for C#. Here’s a link
https://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx
Adding a processing option and associated code path to use BigInteger, and hence HUGE numbers was conceptually straightforward but there was one major problem (it’s always something!). And that is, the BigInteger class does NOT have the ability to compute Nth ROOTS. Although it has a method to compute Nth powers of an integer, it does NOT have the capability to compute a power less than 1. For example, here is how we might find the cube root of 8 using the standard Math.Pow() method:
double dNthRoot = Math.Pow(8, (1.0 / 3));
The prior version of the SumsOfPowers program heavily leveraged the “exponent < 1.0” capability and fast speed and simplicity of using Math.Pow().
However, in the BigInteger class the exponent must be a positive Integer. So what to do? I could use a “binary search” method to find the Nth root of a number but I’ve been down that road before and I am NOT A FAN! After a couple of days thinking about that problem I settled on what I think is an interesting and clever technique (clever for me at least). The technique leverages on the fact that:
1. The Nth root of ( A*B ) == (Nth root of A) * (Nth root of B);
Let’s say we want to find the Nth root of SUM (SUM is the sum of the terms). Like so…
An + Bn + Cn = SUM
A “USEFUL TAUTOLOGY” Gets Some Action
What we REALLY want to figure out however is the Nth root of SUM if it exists. So…
SUM == SUM * (L/L) <—– Useful Tautology !!! I.e. SUM == SUM * 1)
SUM == (SUM /L) * L Now we have SUM /L as the A and the L by itself as the B of 1 above.
Then we can say
Nth Root of SUM == ( Nth Root of (SUM /L) ) * (Nth Root of L) No matter what L is
So let’s let L be the max size of a long integer. As you will see, by doing that, and with a little magic, we can shortly make use of the standard Math.Pow() that I love so dearly and which is so useful and fast. But first we have to use a few more tricks that follow (and remember that L == 264 == max size of a long integer)…
To compute SUM / L OUR ONLY OPTION is to use BigInteger.DivRem() (because SUM could be > 264 ) so here is how we do it.
BigInteger.DivRem() yields 2 things we need. a QUOTIENT and a REMAINDER which we will call biQ and biR. bi stands for BigInteger. Keep in mind that each of these will be < 264 . So we do this:
biQ = BigInteger.DivRem(SUM, L, out biR);
See Here –> https://msdn.microsoft.com/en-us/library/system.numerics.biginteger.divrem(v=vs.110).aspx
This gets us our quotient (biQ) and remainder (biR). Then
SUM / L == biQ + (biR / L) and this is the A part in
The Nth root of A*B == (Nth root of A) * (Nth root of B);
L by itself is the B part in the above.
Now we just cast biQ and biR to long integers and compute our A and B as long (the form needed for our goal of using Math.Pow()).
long lA = (long)biQ + ((long)biR / L);
long lB = (long)L;
// now we can use Math.Pow() again. HOORAY! Get the Nth root of A and the Nth root of B
long lAnthRoot = (long)Math.Pow(lA, (1.0 / nExponent));
long lBnthRoot = (long)Math.Pow(L, (1.0 / nExponent));
// The BigInteger biSearchStartingPoint below is what all this was about calculating!
biSearchStartingPoint = BigInteger(lAnthRoot * lBnthRoot);
// Rest of code is like before but now using BigIntegers instead of longs
Does all this seem complicated? It really isn’t. What’s complicated is the alternatives!!! All we really need to know is that
The Nth root of ( A*B ) == (Nth root of A) * (Nth root of B);
and we’re looking to get A and B small enough to be <= 264 in order to
leverage existing code and logic and to be able to use Math.Pow() for its speed and simplicity.
Did you notice that 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 SUM this new BigInteger version could handle is (264 ) * (264 ) or 2128 . As Dundee would say, “Now that’s a knife!” With a little more effort we could make it handle much bigger numbers but this is good enough for me (It’s a hobby!).
So what about performance?
For the very best case, when using BigIntegers where regular long integers would work ok, then the BigInteger code path takes about 8 times as long to run (i.e. where the SUM of the terms is less than 264 ). As soon as the SUM of the terms exceeds 264 then the code path takes an additional 3-4 times to run (or about 30 times as long to run as when regular long integers would be ok to use… except they can’t be used when SUM > 264 ).
In other words, it takes anywhere from 8 to 30 times as long to run when using BigIntegers… depending on what SUM is at any particular time.
Whew!
A Very Interesting Note About Testing
From the movie Jeremiah Johnson – Jeremiah and Bear Claw (Will Geer) are out hunting elk.
Jeremiah Johnson: The wind’s right, but he’ll just run soon as we step out of these trees.
Bear Claw Trick to it. Walk out on this side of your horse.
Jeremiah Johnson: What if he sees our feet?
Bear Claw Elk don’t know how many feet a horse has!
So how does the above relate to testing? You will soon see…
It’s very interesting to note that the code path when using BigIntegers is a little different depending on whether the value of biSUM is <= LMAX. I put in a #define in the program called LMAX and the default value for “LMAX” is, of course, 264 (LMAX stands for “long maximum”). Anyway, in simple pseudo code here is what happens…
If (biSUM <= LMAX) {
Just convert the BigInteger biSUM to a long called lSUM
compute lNthRootOfSum = Nth Root of lSUM using Math.Pow();
BigInteger biStartingPoint = BigInteger(lNthRootOfSum)
// *** biStartingPoint is what we are after and
// *** is used for Check4Solution code later in the pgm
}
ELSE {
Jump thru the hoops described above to compute biStartingPoint
to be used for Check4Solution code below
}
I won’t get into the reasons for it, but trust me… the reality is that it’s difficult to test the code using actual HUGE numbers ( such that the SUM > 264 and/or where 1 or more TERMs are > 264 ) . However, the SumOfPowers program and the BigInteger library don’t care or even know about “264 ” per se !!! All that code cares about is that numbers > LMAX are handled differently than numbers <= LMAX! “Elk don’t know how many feet a horse has!”
So, for the vast majority of testing we can simply set LMAX to some low value (e.g. 1000, or 100, or 10) and the code will process those “small” TERMs and SUMs exactly the same as if those values were HUGE numbers, by using the “huge number” code path (which uses the BigInteger class).
An added benefit is that the “BigInteger” code path should produce results identical to the “normal” code path.
For example, consider this… A2 + B2 = C2
Does it look familiar? If we run the program using the default processing options and set and test for A=3 and B=4, then the code will go thru the “normal long integer” processing path and determine that C==5. However, we can switch to “big number” processing simply by:
Checking the Checkbox for the “Use Biginteger” option (bottom of screen) and then
Settting the LMAX value to 2 (also on the screen next to the BigInteger option checkbox).
Now the program will take the “Big Number” code path and will process everything using BigIntegers!!! Why do we want to do this? Because it simplifies testing because, once again, the “BigInteger” code path should produce results identical to the “normal” code path (which is already well tested!!!).
Of course, eventually we have to test using actual HUGE numbers and the default LMAX value of 264
Pretty cool eh? Elk don’t know…
************************ end of post ****************