On a New Road

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.

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 x₀. Provided the function is reasonably well-behaved a better approximation x₁ is

Geometrically, x₁ 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:

Instead, people rarely code Newton's method in the abstract. They usually apply it on paper to some concrete function, like f(x)=x²-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 | (((long)((((int)((lt>>52)&((1<<11)-1))-1023)>>1)+1023))<<52)); 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...