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:

http://itbegsthequestion.com/sumofpowers/

http://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 2^{64 }. 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:

55^{5 }+ 3183^{5} + 28969^{5} + 85282^{5} = 85359^{5} (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 2^{64 }. 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…

A^{n} + B^{n} + C^{n }_{= }_{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 N*ow 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 == 2^{64 }== max size of a long integer)…

To compute **SUM / L** **OUR ONLY OPTION** is to use BigInteger.DivRem() (because SUM could be > 2^{64 }) 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 < 2^{64 }. 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 <= 2^{64 } 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 <= 2^{64 } ?” 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 (2^{64 }) * (2^{64 }) or 2^{128 }. 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 2^{64 }). As soon **as the SUM of the terms exceeds 2 ^{64 } 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 > 2

^{64 }).

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, 2^{64 }(LMAX stands for “**l**ong **max**imum”). 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 > 2^{64 } and/or where 1 or more TERMs are > 2^{64 }) . However, the SumOfPowers program and the BigInteger library don’t care or even know about “2^{64 }” 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… A^{2} + B^{2} = C^{2}

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 2^{64 }

Pretty cool eh? Elk don’t know…

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

## Leave a Reply