Equations and Methods

Instead of my usual whining, I thought I'd write a few blog entries that are more technical. I've been playing with a lot of stuff lately. Lots of threads of ideas to play with. Mostly just fragments, not adding up to much. This is the start of one thread that's been wandering through my head for years. I'll need to add several more blog entries before this one even starts to make sense.
Ignore computer science for a moment, including everything you know about programming languages. Think back to the math courses you took in school. There are many things in that space that are programming-language-ish, but missing from programming languages. Consider Newton's Method:

Newton's method, from Wikipedia:

In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the zeroes (or roots) of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method.

The Newton-Raphson method in one variable:

Given a function ƒ(x) and its derivative ƒ'(x), we begin with a first guess x0. Provided the function is reasonably well-behaved a better approximation x1 is

Geometrically, x1 is the intersection point of the tangent line to the graph of f, with the x-axis. The process is repeated until a sufficiently accurate value is reached:

So what is Newton's Method? It's kind of like a function that takes two functions as parameters (f(x) and f'(x)). But the second parameter is should really be derived from the first. f'(x) can be approximated by a little numerical trickery, but it's a numerically dicey thing to do. One of the big drawbacks with closures and function pointers is that you just get to execute the function. You can't do any introspection. This is one of those times where I miss Lisp macros: the ability to rip open a function and do wild things like symbolic differentiation was wonderful. My PhD thesis project was filled with such hackery.

Instead, people rarely code Newton's method in the abstract. They usually apply it on paper to some concrete function, like f(x)=x2-V (finding the zeros computes sqrt(V)). The code you end up with looks like this:

public double xyzzy(final double v) {
        long lt = Double.doubleToRawLongBits(v);
        double t = Double.longBitsToDouble((((1L<<52)-1)|(1L<<63)) & lt |
        t = 0.5*(t+v/t);
        t = 0.5*(t+v/t);
        t = 0.5*(t+v/t);
        t = 0.5*(t+v/t);
        t = 0.5*(t+v/t);
        return t;
(This actually works, it's almost good to the last bit) If someone emailed this code fragment to you, I'll bet that you'd be hard pressed to figure out what it does. The 5x loop unrolling might be a good hint, but the long bit-bashing expression at the beginning is pretty opaque. Both f(x) and Newton's method have become totally obscure. The code is hard to fix or modify. It's very brittle.

This isn't just a specific rant about Newton's method. There are lots of other "method"s that map from some problem to a piece of code for computing the result. The domains that are particularly problematic these days are the zillion techniques for using multicore machines and clusters of them to solve some problem. Straightforward solutions get twisted and pulled as they're mapped to frameworks like MPI or Hadoop until they're totally obscure and wound into a ton of boilerplate.

More on this another day...

February 1, 2011