Paradise ponders...

Paradise ponders...  It's raining today; started late yesterday afternoon in a stop-and-go kind of way.  There hasn't been much accumulation out.  The temperature is in the mid-50s, and it's 100% humidity (naturally), so it feels fairly chilly out even when it's not actually raining.  It will be mostly an inside day today, I think.  The dogs and I will have to live without our beloved morning walk.

I've been working away on a couple of tough (and therefore interesting) programming challenges.  The first one is comparing the result of a double precision floating point with zero, where we want the result of the comparison to zero to be true even when the result of the subtraction is slightly different than zero.  That's a far harder problem than one might think, a special variant of the also tough general case of simply comparing two floats.  Click on the link to that article if you'd like to know more about the whys and wherefores.

I had an insight yesterday that led to a nice solution for me.  In my original formulation, I did something like this:

if( nearlyEqual( a - b, 0.0, epsilon ) {...}

Where a and b are doubles, and epsilon is how close a - b and 0.0 must be in order to be considered equal.  This is a conventional comparison: you subtract the two numbers and compare the result to zero.  In this case, however, the results can be wildly different than what you expected, as that linked article explains.

The solution was crazy simple: I simply rewrote the formulation as:

if( nearlyEqual( a, b, epsilon ) {...}

Voila!  No more problem.  It always gives me a kick when I beat my head against the wall working on a tough problem, and the solution turns out to be easy!

The reason this solution worked is that epsilon is relative to the exponents of the numbers being compared.  In the first formulation, if one or both a and b are computed and should be considered equal, there will likely be a very small difference between a - b – but exactly how small depends on the size of those numbers.  In general, the exponent of the difference will be roughly 16 (base 10) less than the exponent of the given numbers.  So if the two numbers were on the order of 10^100, the difference would be on the order of 10^84 – a tiny difference relative to the given numbers, but a long, long way from zero!  So of course they don't look like they're nearly equal.  In the second formulation, because a and b are the inputs to the nearlyEqual() function, the function knows what their exponents are, and can accurately judge what's close enough.  Oh, so easy!

The second issue I haven't solved yet.  I need a hash function over an array that is sensitive to each nonzero value and its index.  The function should generate different results if the values at a pair of indices are swapped, and should generate the same results no matter what order the values and indices happen to be presented in.  I'm still pondering that one...