Embedded Systems October 2000 Vol13_11

Issue link:

Contents of this Issue


Page 31 of 181

PROGRAMMER'S TOOLBOX • Now tha t' mo re like itl True, we FIGURE 3 Rarabolic bisectio'n 1 ~ II " 0.1 0.01 0.001 co x 0.0001 0.0001 0.000001 0.0000001 2 3 4 5 6 7 Iteration LISTING 5 doubLe para_search(doubLe (*f) (doubLe), doubLe &x0, doubLe &x2, doubLe Eps){ #define MAX_ITER 30 doubLe eps = Eps * (abs(x2-xO»; II initiaL Last vaLues make sure we try at Least twice doubLe Last1 = 1e20; doubLe Last2 = -1e20; doubLe x1 = goLd(xO, x2); doubLe yO = f(xO); doubLe y1 = f( x1); doubLe y2 = f(x2); for(i=O; i< MAX_ITER; i++){ if(!para_shrink(xO, x1, x2, yO, y1, y2» goLd_shrink(xO, x1, x2, yO, y1, y2); if«x2-xO) < eps) break; if(max(abs(x1-Last1), abs(x1-Last2» < eps) break; Last2 = Last1; Last1 = x1; } if(i = MAX_ITER) cout « "Para_search: No convergence after" « MAX_ITER « " triaLs." « endL; return x1; } } I'd also like to change the crite ri- o n for fo rcin g a bisec ti o n ste p. Curre n tly, we just cou n t off pa rabo l ic steps, and the n fo rce a bisectio n whe the r th e me th od needs it o r no t. 30 OCTOBER 2000 Embedded Systems Programming One thing we still must check o n is the suita bility of th e estim a tes com- ing o ut of th e pa rabo li c fit. If, fo r example, it gave a valu e for Xl tha t 's, say, almos t equa l to xo, we can expect th a t the next pa raboli c fit will be poor. I've flagged thi s as a po te ntial pro blem in the past , and Bre nt worri ed abo ut it too. Howeve r, bo th Bre nt's o rigina l Algol code and Press e t al. 's C tra nsla tio n o nly rej ect th e estima te if it's ve ry close (within a n e p ilo n va lue o n th e o rde r o f th e precisio n in th e so lution ) of o ne of th e bracke tin g po ints. I'm goin g to be much mo re aggressive o n thi s o ne, and rej ect it if it's within 5% o f the total CUITe n t inte rval be tween Xo a nd X2' T he stru cture o [ para_shrinkO all ows us to rej ect, simply by re turning a false value fo r th e re turn Boolean. T he cod e frag- me nt is : if(max(x-xO, x2-x) < too_cLose){ count = MAX_PARA; return FALSE; 8 9 10 11 12 13 ' :;, : .,~ ,: .. " .. ; . .. .' -0- xO - - -c - - - x1 - -A- - x2 1 still have va ri a bles tha t seem to stick a t o ne valu e. But look how drama ti- cally th e o the rs a re cha nging as we go. Afte r o nly eight passes, all three e rro rs a re less th an 0.001. Compa re th at to Figure 1, whe re it takes 12 passes to accomplish th e same res ult, o r Figure 2, whi ch ta kes 10. Admittedly, we' re now evalua ting the fun c tio n twi ce [o r each bisecti o n pass, but eve n so, the diffe re nce is impressive . I d o n 't mind a value get- ting stuck a t, say, 1.0, i[ th e other two a re ra pidly squeezing up next to it. Tha t's the best we can really ho pe [or in such a me thod. Preventing bad estimates

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems October 2000 Vol13_11