Intel's Ronler Acres Plant

Silicon Forest
If the type is too small, Ctrl+ is your friend

Tuesday, October 20, 2009

Conchoid of Nicomedes & Rootfinder

Not too long ago Stu posted a little blurb about how to trisect an angle using nothing but a compass and a straight edge. Okay, he cheated a little, but he didn't use any trigonometry and he didn't use a protractor. I looked at it a bit and satisfied myself that it worked. But I could not translate it into a simple formula that you could just plug the numbers in and it would crank out the answer. After stewing on it for a while I realized that this was one of those problems that would be a good application for a computer. In particular, it would be a chance to test out a root finder I knew about.

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.

3 comments:

Stu said...

Wouldn't it be easier in polar coordinates? r+a*sec(theta) ?

Chuck Pergiel said...

Polar coordinates? You would need a protractor. Or am I missing something?

Chuck Pergiel said...

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.