How Accurate is my Algorithm?

I wrote an algorithm.

It was fast.

It worked.

It was wrong.

Replicant tears did fall.

Fast… a couple of minutes versus the hours needed by its R cousin.

Worked… Final results showed an optimised selection of sites and management actions remarkably similar to the test-results that came with the R script.

Wrong… Optimised, but with species penalties reporting a value of 490, where the R script reported zero species penalty. 490… the smallest it would go. 490… a bizarre artefact, where it otherwise seemed to have work as intended.

Tears… in the rain. Lost in time… all those moments…

Buy a unicorn, stingemeister!

Buy a unicorn, stingemeister!

The algorithm cut across from R to .NET last Friday morning.  Since then, that number… 490, again and again. Convergence at the 80,0000 iteration mark; attempts to try other paths; re-convergence; 490, .NET, stuck at 490. Remarkably similar to the R script, except… 490, where R had zeros. Shiny, happy species receiving full target benefit, represented by zeros.

But not for .NET, and yet… damn me, but those tiny decimal, near-zero values for a recurring set of species, all hinted at it having worked.

The rabbit hole.  Google-fu; The only way to fly. Suspicion. Floating-point arithmetic, rounding errors. I’m late! I’m late!

Should have swallowed the red pill…

Today. Zeros where once only 490 would appear.  Shiny, happy species receiving full target benefit but this time, also via .Net.

Lessons learned:

  • A branch of computer science called “Numerical Analysis” that needs deeper groking.
  • Floating-point arithmetic algorithms can be stable, or unstable. Stable is where all the accurate algorithms hang out.
  • Against personal intuition:
    • multiplication and division are relatively stable (with caveats around significant digits).
    • addition and subtraction are not.
  • Things get very unstable where one very small decimal is subtracted from another. Subtractive cancellation makes Deckard a drunk boy.

Rules of thumb (gonna need more thumbs) until grok-time is sourced:

  • Just don’t subtract one very small decimal from another whilst looping hard.  Find some other way. Subtractive cancellation makes Deckard a paper unicorn crumpling boy.
  • When adding, try to add in order from smallest to largest number.
  • Be aware of the number of significant digits between operands.  Everything that isn’t significant in the resulting number may very well BE insignificant, but it’s still there, like a tiny little cancer spot…
  • Remember, when everything is insignificant, NOTHING is significant

Latest algorithm gets to finally hang out with the stable (more accurate) ones.

Getting there though… I’ve seen things you people wouldn’t believe. Tears… in the rain. Lost in time… all those moments…

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s