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

Sum Of Powers – C# January 6, 2015

How Plato helped debug a C# Program

 Short Background

An  +  Bn  =  Cn

Where A B C and n are all positive integers and n>2.  The first “Fermat program” let you assign a range of test values to A and B and to specify the exponent (n).   When you clicked on GO it would plow thru the possible combinations and list values of A and B and C and n that are solutions to Fermat’s Last Theorem.  Of course, we know there are not any solutions but it was instructive to go thru the process of creating the program anyway.

This Project/Exercise  –  Fermat is Generalized To Become The SumsOfPowers Program

A couple of weeks after playing with the Fermat Program I thought it would be interesting to “generalize” it.  I wasn’t going to cure cancer that week and I had nothing better to do.

The idea was to generalize the concept to allow for an arbitrary number of TERMs on the left side of the equation (the Ts are the “TERMs”):

T1n  +  T2n  + .. Txn  =  Zn

Ease of Use – UI Considerations

Each TERM (each T1..Tn) needs its own Range of values.  It must be easy to assign the same Range to all Terms at once (all Ts) or to assign different Ranges to 1 or more Terms.  And remember that for any particular press of the GO button you might want 2 Terms or you may want 22 Terms or you may want…

It must be easy to assign a value for the Exponent (n).   This one is simple.

It must be easy to specify which TERMs will actually be used (and which ones will not be used).  For example, I might want to assign a Range of 1..1000 to all TERMs but then be able to quickly specify that for the first execution, only Terms T1..T2 will be used in the test for solutions.  And then to quickly and easily change the test to look for solutions for 3 Terms or 4 Terms and so on.  For example, to test for solutions of

T1n  +  T2n  =  Zn

and then to very quickly and very easily change the setup to look for solutions to:

T1n  +  T2n  +  T3n  =  Zn

It turned out that use of a Multi-Selection  ListBox control was key to making this possible.  You simply “select” which Term(s) will participate when you click GO.

Other processing options are also needed.  Experience had shown that, for example, a Checkbox for “Show Solutions Details” is handy to specify whether you actually want to see the details for solutions.  Leave it unchecked if you just want to know how many solutions were found – without the details.  It turns out that most of the time we only want to know whether there are solutions (and maybe how many) without needing to see the actual details for each solution.  And, obviously, we need someplace to “print” all of this (a Multi-line TextBox works well).   The SumsOfPowers program currently has 7 “processing options” which I won’t get into here.  It’s interesting to note (and probably obvious) that one doesn’t know what processing options are desirable until they actually start coding or using the program (Duh!).

Again, a LOG is needed for displaying Solution Details, Execution Stats, and so on.   Again, Duh!

If you are interested, a screen print of the SumsOfPowers program appears at the end of this post and from it you can get the gist of how the UI works.  Though it’s pretty simple, it took a few days of pondering the problem using a small white board before deciding on what the UI should look like and how it should operate.

 

Program Logic – Recursion Is The Key

The original Fermat program had only 2 Terms (A and B) so that lent itself to using a nested for loop:

 For Each value of A in its range

compute A^n

For Each value of B in its range

compute B^n

Compute Cresult = A^n + B^n

if (Cresult has a “perfect nth root”)

Success! Print it!

else

nothing to do – try next B Range value

end for each B

end for each A

 

When there are only 2 terms involved it seems natural to gravitate to a solution with 2 FOR loops (one inside the other).   At one point I was going to put the “A” loop inside the “B” loop but decided against it. It’s a joke!

 

However, for a more generalized program where we can have an arbitrary number of  TERMs instead of just 2 Terms (A and B),   I kept concluding that using FORs or WHILEs or FOREACHs was too complicated and unwieldly.   After some days of thinking about it,  the notion of using a RECURSIVE function bubbled to the surface.   It was a Eureka!  moment. The whole problem instantly collapsed to a very simple one. It was time to code the project.

 

In the end, what surprised me was that use of Recursion did not come to mind almost immediately! On the other hand, although use of Recursion is commonly taught in the classroom (and books), I can’t remember ever using or even seeing the technique used in the “real” world of GTE/Verizon;   I guess Recursion did not often lend itself to the types of problems common in that environment. From that perspective it’s not surprising that it was not at the top of the list of techniques to think about.

All that said, you may want to toy with the problem yourself to see what you think about FORs and WHILES vs Recursion  for a SumsOfPowers type of problem.   Again, the key part of the problem is to allow for an arbitrary number of Terms.  On a side note, I did remember that one needs to be wary of the Recursion “Depth” getting out of hand. For this problem, the Recursion “Depth” is extremely modest and is only as deep as the number of TERMs participating in the “Solutions Search.”

 Plato

Plato

So let me tell you how Plato reached out across the world and across thousands of years to point out a bug in this new SumsOfPowers program…   Somewhere along the line I started running the program with the option of using the C# MATH libraries.   I.e.  I had created the program with 3 alternative code paths one of which was to do much of the computations using the C# MATH libraries.   I started using the “MATH Library” code path option because it ran a bit faster (it’s the “Use Pow Function” option on the screen print at the end of this doc).    While playing with the program I noticed that the following did not appear to have any solutions.

T13 + T23 + T33 = Z3

I made a mental note of that because it seemed very unusual.   But I continued on for days playing with and refining the program.   Eventually I followed up on that observation and said to myself :

“Self, don’t you think that if indeed there are not any solutions,  that after all these years

you would have heard about it?   Let’s investigate.”

 

So where does one start such an investigation? You guessed it.    Google.    I have forgotten the details and search terms used but nonetheless it didn’t take long to  Goomble” into “Plato’s Number.” Yes, “goomble” is a combination of “google” and “stumble.”   Anyway, here’s a couple of links for “Plato’s Number.

http://mathworld.wolfram.com/PlatosNumbers.html

http://en.wikipedia.org/wiki/Plato’s_number

Plato’s number is 216 because it is the cube of 6.   From the formula 

33  +  43  +  53   =   63

And amazingly,   216   is also a sum of the cubes for the Pythagorean triple 3,4,and 5 !!!  This pointed out that there was a bug in the code. It had failed to detect that there were indeed solutions, and one of  them was famous!!!

T13 + T23 + T33 = Z3

So I ran the program using the processing option to NOT USE the C# MATH library Math.Pow()  function and sure enough, the “Plato’s Number” solution was found immediately!   The problem must concern itself  with the use of Math.Pow().   Fire up the debugger and immediately…

The Math.Pow() function uses doubles.   And instead of returning 6 for the cube root of 216 it returns 5.999…993.   Pretty close to 6… but it’s not 6!   And when you cast the double = 5.9999999999 to a  long integer the compiler truncates and you get 5 (instead of 6)!    Damn!!      should have seen that one coming because it’s a warning shot anytime the compiler makes you explicitly cast!

So that’s how Plato reached across thousands of years,      and the internet,        and Google,        to let me know that there was a bug.

It’s extremely interesting that this discovery allowed me to leverage that truncation behavior as a hugely superior alternative to the “Binary Search” method that I had been using to bypass evaluation of  large numbers of non-productive possibilities.

Using Math.Pow() to obtain the Nth root of a number may return the “wrong”  RESULT when cast to an integer but it will yield an integer RESULT no more than 1 less than the true integer Result! 

You may want to read that again. 

In this way the code only needs to test (at most) 2 numbers to determine whether there’s a “perfect Nth root integer” for Zn . I.e. It  only has to test RESULT, or,   RESULT+1. This is hugely superior to looking for a nth root candidate evaluation starting point by using Binary Search methods.   And the code gets simplified tremendously.   Now that’s a silver lining that the “bug” pointed out!!!!!!!!   Thanks Plato.   Once again, you may want  to read this again.

Euler’s Conjecture And

The CDC 6600 Computer

Euler

During the “Plato’s Number” investigation I also stumbled on Euler’s Conjecture.  Here are 2 links.

http://en.wikipedia.org/wiki/Euler’s_sum_of_powers_conjecture

http://mathworld.wolfram.com/EulersSumofPowersConjecture.html

Euler conjectured that at least n nth powers are required for n>2 to  provide a sum that is itself an nth power.   

It sounds complicated on first reading but it really  isn’t.  For example, for 5th  powers,  any solution would require 5 (or more) TERMs on the left side of the equation.   

Like so  for n = 5 (x must be >= 5).

T15  +  T25  + .. Tx5  =  Z5

The conjecture was disproved by Lander and Parkin (1967 on a CDC 6600 computerwith the counterexample shown below (less than 5 terms on the left side of a 5th power equation):

275 + 845 + 1105 + 1335 = 1445

http://www.ams.org/journals/mcom/1967-21-097/S0025-5718-1967-0220669-3/S0025-5718-1967-0220669-3.pdf

http://en.wikipedia.org/wiki/Euler’s_sum_of_powers_conjecture

So I tried a solution search with the new SumsOfPowers program using 4 TERMs with all Terms having a Range of 1..200.   It only took 9 seconds elapsed to find the  Lander/Parkin result (using just 1 of the 4 CPUs on the PC!). That solution search evaluated 62.7 million combinations of the 4 Terms in just 9 seconds! Any guesses on how long it took on a  CDC 6600 in 1967 (which I believe was the fastest computer in 1967)?   Or how long it took to write the program?   I tried to  find out but could not find any details. If you ever find something then let me  know!!!   But seriously!!! 9 seconds!?   That’s not even time enough for a sip of coffee let alone a whole cup!   Euler would have flipped out if he’d had a $600 PC. Of course, then he’d have to figure  out how to get electricity, and how to type, etc.    But realistically, if he’d had a PC he would probably have spent all his time surfing for Puritan Porn!

 Using Arrays

PCs today have lots of memory.  GIGAbytes of memory. So I thought I would try a technique whereby, at the start of a “solution search,” the code would calculate all nths for all range values of all Terms  and store them in large arrays in memory. This is why there’s a “Use Arrays” CheckBox on the screen.   In theory,  it might be faster to calculate all the needed values just once at the beginning of a run  and then pull these values from memory as needed rather than compute them every time they are needed (and they are needed a lot!).   Also, the amount of code and effort needed to implement the  use of arrays as a processing option was minimal. So the “Use Arrays” processing option (and code path) was added. “    AND THE SURVEY SAYS…”

SurveySays

Using arrays is significantly faster than “compute on demand.”   But it’s only about 25%  faster… which is OK but nothing to write home about.   I was hoping for “order(s) of magnitude” faster but apparently  the machine code to pull numbers out of arrays in memory is not hugely faster than computing the numbers each time you need them…  which makes some sense considering that the vast majority of  the computations for this problem uses integer arithmetic (which computers and compilers are very very very good at).

Click on the sample screen print to enlarge it.  It’s from the SumsOfPowers program to give you the gist.   It’s a screen print from a Euler Conjecture / Lander-Parkin solution search as discussed perviously. Also, a CDC 6600 circa 1967 follows.

SumsOfPowers

CDC 6600 follows (1967)

CDC6600

Categories Uncategorized

Leave a Reply

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