Embedded Systems October 2000 Vol13_11

Issue link:

Contents of this Issue


Page 33 of 181

PROGRAMMER'S TOOLBOX • At this point, we almost have a serviceable function, in that it takes a mix- ture of parabolic and golden section steps, and it chooses between the two based on reasonably intelligent, rather than pre-programmed, rules. I have what I t11ink are some super LISTING 6 #incLude #incLude #incLude #incLude #incLude * and aLso define abs as a macro rather than a function. If you 1* NOTE: Files constant.* * don't do this, better change caLLs to abs to fabs. */ doubLe f(doubLe xH return cos(2*pi*x*x*x); } void main(void){ doubLe eps = 1.0e-7; doubLe xO = 0; doubLe x2 = 1; doubLe x = para_search(f, xO, x2, eps); cout « x « endL; } and jmath.* define pi, the GoLden ratio, ideas fo r a robust halting criterion , but they would req uire too many changes to our code to include them thi s month. Brent used the change, not in two successive pal-abolic esti- mates, but in th e estimates two cycles apart. Press et al. suggest o nly that "th e reason ... seems esse n tially heuristic." I'll go Brent one step bet- ter, and require that we have three parabolic estimates within an epsilo n error. The code is collected into a ge neral-purpose function in Listing 5. A sample driver pl-ogram, com- plete with test function, is shown in Listing 6. For your interest, the method converges to 1-7 accuracy in 17 itel-a- tions: five bisectio ns and 12 parabol- ic fits . It uses a total of 25 function evaluatio ns. I know, I know, that's more than Brent's method. That is no doubt because each golde n sec- tion ma kes two evaluatio ns, not just one. At this point, it's a price I'm prepared to pay to get rock-solid robustness. I still believe we can improve on the algorithm som more. For exam- ple, I want to try my ideas for a better halting criterion. However, I won't be doing that next month. I want to For the test case, it has always been needed in th e sense that one of the boundary poin ts seems stuck. Bu t this may not a lways be true. When the boundary points are not stuck, it's foolish to abandon a method that's working. A be tte r method would be to kee p a separate count for each boundary point, and kick out when one appears to be stuck. Listing 4 shows function para_ shri nkO after this change. Knowing when to quit I think this header is particul arly apt, both for this month's session, and also for the study of minimizing a functi on. 1'm ready to quit, aren 't yo u? At this point, we almost have a ser- viceable function, in that it takes a mixture of parabolic and golden sec- tion steps, and it chooses between the two based on reasonably intell i- gen t, rather than pre-programmed, rules. The one thing still lacking to ma ke th e [unction p.-oduction-quali- ty is a good stopping criterion. Recall that, for bisection-only case, the cri- terion is simple: we stop whe n the in terval between Xo and X<.! i reduced sufficiently far. Thanks to the forced changes in both boundaries, we could still use this criterio n, but in fact, the paraboli c fits seem to be homing in considel-ably faster than that last boundary point gets pulled in . So we'd be taking a few too many steps. 32 OCTOBER 2000 Embedded Systems Programming give both you and I some time to wring out the algorithm. Have at it, try it on as many functions as you can, and see if you can break it. Meantime, I th ink we could all use a rest from Brent's method andi ts cousins, so next mo nth I'll be start- ing a new topic. See you then. esp Jack W Crenshaw a senioT princijJal design engineer at Atliant Tech Systems Inc. in Clearwater, FL. He did much early work in the sjJace program {md has deuel- o/Jed numerous analysis and real-time pro- grams. He is the author of Math Toolkit for Real-time Programming (CMP Boo/IS, 2000). He holds a PhD in jJhysics from A ubum University. Orenshaw enjoys contact and can be )'eached via e-r/wil at jcrens@earthlinli. net.

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems October 2000 Vol13_11