A few years ago I was reading Embedded Computing on a regular basis and there was a fellow by the name of Jack Crenshaw who wrote a series of articles about writing a piece of code for finding the root of a complicated equation*.
Many formulas only function in one direction. You can put a value in and turn the crank and it will produce an answer, but if you know what value you want, there is no good way to compute what value you need to start with. The only way to do this is to try a variety of input values and see what kind of results you get. Then compare these results with the result you want, and then take a guess as to how much to change your input value. Repeat until you are satisfied.
It's kind of like target shooting. You know where the target is and you have a pretty good idea of where to aim in order to hit the target, but due to various factors, it may take several trial shots before you finally get your rifle dialed in and hit the bullseye.
Evidently Jack had run into this problem more than once, because he wrote a piece of code to perform this "guess and check" operation with the goal of minimizing the number of executions the formula code needed.
So I got the bright idea to try out his root finder on this Nicomedes problem, and after I got all my X's and Y's sorted out, it works like a champ. The source code for my demonstration program, including the root finder, is here.
Update May 2015: Replaced the link to the source code file and the link to Stu's article.
* Update July 2025. Link to Jack Crenshaw's stories is dead. I found three of them. Here's the links:
- A root-finding algorithm April 2004
- The root finder verified September 2003
- A root finder’s roots May 2003
3 comments:
Wouldn't it be easier in polar coordinates? r+a*sec(theta) ?
Polar coordinates? You would need a protractor. Or am I missing something?
Took me a while to realize what you were getting at. Yes, using trigonometry makes the problem trivial, but it requires using trigonometry. I was trying to emulate your straight-edge-and-compass method of finding a solution, and that meant using only algebra. Also, in some embedded applications (computer programs that run on resource poor microprocessors), there isn't room in memory for the code library that implements the trig functions. My friend Jack (not Mr. Crenshaw) is working on just such a project. So I had a two-fold interest in seeing if I could do it this way.
Post a Comment