October 2004 archive

Exponential Secant Root Finder

Given a function ƒ, find x such that ƒ(x) = 0. Sounds simple enough…

Root finding is a hobby of mine. It’s kind of a lame hobby. It can be lots of fun though, and of course there are many real world usages for it. Once in a while, I’ll read through papers and methods on the general subject and implement new algorithms. I once even had an “algorithm war” program which would pit two against each other: given an arbitrary function with one root, which method would find it first? Most consistently first? Highest accuracy with fewest function calls?

I was faced with an interesting more specific problem yesterday. A simple secant solver had been used on a function with great results, except at a few extreme software inputs. In general, the solver only knew that 0 < x <= ?, and, in fact, ƒ could not be evaluated for values <= 0. “Hm…. the secant method worked so well for this nice, smooth function… if only there was a way to prevent it from going negative,” I thought.

What if the secant method were drawn on a semi-log plot, rather than a cartesian plot? That would cause the root finder to never go negative. It would have greater resolution at smaller values with fewer iterations, but could suffer from requiring more iterations at higher values (for the same tolerance).

/wsimages/plot-linear.png

Figure A: Function plotted on a cartesian scale.

The function being solved looked similar to figure A. In figure A, if the secant method were to hit points between 5 and 10 billion, it would quickly be thrown off by the straight slope into values less than zero, where the function cannot be evaluated.

/wsimages/plot-log.png

Figure B: Function plotted on a semi-log scale.

If it is instead plotted on a semi-log scale, as shown in figure B, the flattened area would throw the values off to very small numbers (around 1E-10). This function would have a very high slope at those values, and the secant method would throw it back into a reasonable range very quickly.

Implementing this modified secant method idea was pretty simple. The standard secant root solver is used, but with a variation of how the next point is chosen:

  • Rather than fitting y = m * x + b to two points on the curve, an exponential function y = m * exp(x) + b was fitted to the two points.
    1. The m value was calculated with m = (y1 - y2) / (log(x1) - log(x2)),
    2. the b value was calculated as b = y1 - log(x1) * m.
  • A new x coordinate by solving the equation for y == 0, which simplifies down to x = exp((y1 * log(x2) - log(x1) * y2) / (y1 - y2)).

This method proved to be as quick as a normal secant solution, and very effective for functions which cannot be evaluated at values <= 0.

Some Nifty Things

Lately I seem to have pushed a large number of important projects to the side to make room for some smaller personal projects. Here’s what I’ve been thinking about lately that’s kinda nifty:

  • I gave notice of resignation to my employer earlier this week. October 8th is my final work day. I’ll be free for a few months to persue some contract work that I’ve got waiting in the wings, and then I’m into a new job in the new year. I’ll be working as the head of software development at a small start-up company. Exciting!

  • I built a new photo gallery system. This one builds on a number of features in flickr. It has tag based image catagorizing, EXIF photo information, and a small number of different image sizes that can be viewed. You can see it in action on my pictures page.

  • A new version of Java was released today. Java 1.5, Tiger, contains a number of boring features: autoboxing (saves some typing), a new for/in loop (saves some typing), and generics (saves some typing – may find some ClassCastExceptions waiting to happen at compile time). These seem to be the features everyone thinks are cool, but I think they’re pretty lame.

    That said, there are a couple of features that are cool. Java 1.5 adds the ability to change a function’s return type when it is being overridden. You can only change it to a subclass of the original type, but this makes a lot of sense. When you really think about it… it turns out that all it does is save you some typing. In any situation where you’d actually use this, you’d be doing some casting that you wouldn’t have to do anymore.

    Hmmm… so… what does it have that’s cool? Variable length argument lists… I’ve never missed these in Java before. Annotations look pretty cool, but if you think about the pretty static applications they have unless you recode your own compiler, they seem to be pretty much just a couple nice builtin features and a new way to add documentation. So… static imports? Yeah, that’s nice. Yay!

    I really wanted to be impressed with Java 1.5′s new features, since I’m doing a lot of Java development these days. But I can just type faster, and I’ll still retain backwards compatibility with people using Java 1.4.

  • I added HTTP Digest authentication into my Twisted based weblog aggregator. This allows me to view LiveJournal RSS feeds with a logged in user, and hence getting links to protected LiveJournal entries that m yuser can see. I submitted a small patch to urllib2 to make it work with those same LiveJournal feeds, and I may add real authentication support to twisted.web.client rather than the hacked support I’m currently using. Maybe this weekend, if I have the inclination.