This post talks about how the desire to eliminate duplicate solutions from the SumsOfPowers program let to an optimization of the code/logic that resulted in a processing “savings” of over 99%.
While playing with the SumsOfPowers program I noticed early on that many of the solutions it would find were “duplicates” of other solutions. Consider this…
An + Bn + Cn = Zn is the same as
Bn + Cn + An = Zn
That is, the order of the Terms does not matter. Unfortunately the early code made no such distinction and would list multiple “solutions” even though many of them were merely duplicates. So, an effort was eventually made to eliminate the reporting of duplicate solutions. The resulting code/logic change for eliminating duplicate solutions had a beneficial side-effect of producing a very substantial performance increase resulting in a decrease of cpu usage of over 99% in many (and maybe most) executions. As it would turn out, it would take a couple of days of effort using pencil and paper trying to come up with a solution to the “duplicate elimination” problem but it would turn out to only require less than 10 lines of additional code to implement (which may have been largely a matter of luck!). I won’t attempt to get into the actual code/logic but I will outline the technique here (you may find it interesting).
Let’s use a simple example (from above)…
Let’s say we have the formula An + Bn + Cn = Zn
There are 3 “TERMS” (A, B, and C) and let’s say that each term can have a value of 1..3. That is, each Term has a “Range” (in this example it’s 1..3).
Think of the TERMs (e.g. A or B or C) and their possible values as a “TREE”
Visually, it looks something like the following (maximize your browser window now)
The “Tree” of the SumOfPowers Terms and their values.
A 1 2 3
B 1 2 3 1 2 3 1 2 3
C 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
.A==1, B==2, C==X is logically equivalent to A==2, B==1, C==X.
There are, of course, other equivalent tree branch pairs, triplets, quadruplets, and so on that get pruned during processing depending on the number of terms and their ranges. To test all combinations for a solution we simply traverse the “tree” from left to right and top to bottom. For example, the first possibility we compute is
A==1, B==1, and C==1 Followed by
A==1, B==1, and C==2 and so on until our very last possibility is
A==3, B==3, and C==3.
Notice that after we process all of the A==1 possibilities, we will then process all of the A==2 possibilities… The very first of which is
A==2, B==1, and C==1.
BUT, as soon as we see that B < A then we don’t need to go any further on that entire branch of the tree since we had effectively processed it earlier. In other words,
A==1, B==2, C==AnyValue
is equivalent to
A==2, B==1, C==AnyValue
The technique works for more than just 3 terms, each with the same range. In fact, the processing savings get very large, very fast, the more TERMS there are and the bigger their ranges. The exponent n has no effect except that the bigger the exponent then the better the chance we’ll exceed the capacity of the numeric types (2^64 is the limit without going to the BIGNUM library which apparently is a major pain in the ass for C# but easy for C++ (or so I read)).
So initially the goal was simply to eliminate duplicate solutions but as luck would have it, there was also a huge performance benefit. And also as luck would have it, it would turn out to be ridiculously easy to implement in the context of the then existing program code. My momma always said…