Wednesday, March 4, 2009

Excusatio Non Petita

The year probably was 1994, so I guess its understandable that I don't exactly recall how did I come across a copy of Numerical Recipes in C: The Art of Scientific Computing. But while skimming through the pages, I eventually got to the part on evaluating polynomials, and read something that struck me very deeply. The paragraph that described what I now know is Horner's scheme read as follows:
We assume that you know enough never to evaluate a polynomial this way:

p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x +c[4]*x*x*x*x;

or (even worse!),


Come the (computer) revolution, all persons found guilty of such criminal behavior will be summarily executed, and their programs won’t be! It is a matter of taste, however, whether to write




Boy was I guilty! Who would have ever thought there was another way of evaluating a polynomial than the obvious one? And that it would be so much more elegant and efficient?

Would be nice if it was just a polynomial thing, but of course it isn't, and the more complicated the math you are trying to get your computer to do, the larger the chance you are doing it terribly bad. And although much has been written about algorithms, the gospel doesn't seem to be spreading too swiftly: as I am writing this, the first match for a search of "prime numbers python " that google returns is this. And he is not alone...

So what am I in for? The idea is to bridge the gap between straightforward brute force (a sin I have been as guilty as anyone else of) and the elegant simplicity of efficient code. Hopefully, this will allow me to escape the guillotine when the Jacobins take over...

There are some simple rules that I intend to follow, at least until I decide not to:

  1. Uncomplicated complexity. The math content will be kept reasonably simple. Or maybe simple isn't the word, as things may get utterly complex. But I will try to stay out of unnecessary complications, so a high school diploma should be all you need to come along on the ride...

  2. Plain python. Sure, C++ is a zillion times faster, but python takes care of most gory details, and makes it easier to concentrate on the algorithm. Plus, it's so cool and trendy!

  3. No libraries. Sage, SciPy, PARI, qhull, FFTW... whatever it is you are trying to achieve computationally, there is a faster way than replicating the code you find in this blog. And interesting as that may be, it would take a lot of the charm of writing this blog, if it turned into a description of somebody else's API. So yes, we will even code our own FFTs!


  1. Jaime me parece usted un auténtico erudito en la materia, ojalá hubiera más gente con este tipo de inquietudes. Felicidades, siga usted por este camino...

  2. Glad to discover you have a blog. I look forward to reading more.

  3. Your resolution on not using any libraries has earned you a place in my "must come back and check" list. Good luck.

  4. Hope I won't dissapoint you...

    In the weeks to come I have the intention of dealing with prime numbers, FFTs, and then some algorithmic geometry, at least convex hulls and Voronoi diagrams...

    And, of course staying away from those nasty libraries that take all the fun away!

    Do feel free as well to leave your suggestions for topics you'd like to see worked out in detail.

  5. I just wanted to throw out a word of appreciation. The posts so far haven't been new information for me, but your code and writing are so lucid I feel I have a much better handle on these topics. I'm looking forward to future posts!