Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 39 of 229

PROGRAMMER'S TOOLBOX e At first glance, fmin.f appears to be the worst kind of spaghetti code Fortran IV. However, take another look. It's really a straightforward translation of Brent's original code, which was written in Algol. (No wonder we don't find many copies of it!) I I swap two double-precision floats void swap(double &x1, double &x2){ double temp = x1; x1 = x2; x2 = temp; } II divide an interval according to the golden section double gold(double xO, double x2){ static const double g = 2-golden; return xO + g *(x2 - xO); } II shrink an interval by dividing one side of it void gold_shrink(double &xO, double &x1, double &x2, double &yO, double &y1, double &y2){ double x = gold(xO, x1); double y = f(x); if(y > y1 ){ xO = x; yO = y; } else{ x2 = x1; y2 = y1; x1 = x· , y1 = y; } swap(xO, x2); swap( yO, y2); } II Find the minimum of a function using golden section search double gold_search(double &xO, double &x2, double Eps){ double eps = Eps * (abs(x2-x0)); double x1 = gold(xO, x2); swap(xO, x2>; double yO = f(xQ); double y1 = f(x1); double y2 = f(x2>; while(abs(x2-x0) > eps) gold_shrink(xO, x1 , x2, yO, y1, y2); return (x0+x2)12.0; } single a rea of nume ri cal algorithms, Ala n 's your man . I've never see n so ma ny impleme ntatio ns (mos tly Fo rtra n and th e new la nguage, F- mo re on this next mo nth ) . Sadly, his Web site doesn ' t list an impleme nta- tio n of Bre nt's method . However, if you fo llow the trail thro ugh "No n- lin . programming," you ' ll arrive at plato. la.asu .edu/guide. html, a site ma in ta in ed by Hans D. Mittlemann and P. Spellucci of Ari zona State Unive rsity. Take an o th e r step through th eir "decision tree fo r o ptim izat io n softwa re," thro ugh pa ths fo r unco nstra in ed linear and nonlinear o ptimizati on, and lo and be h old , th e re's bin/nellibfiles. fJl ?f ilename=/ go/fmin.f, which is the ir impleme nta tio n of Bre nt's me thod . (Yo u can also find fmin . f by following a trail thro ugh the van Snyde r We b site.) At first glance, fmi n. f appears to be th e worst kind of spaghe tti code Fortran IV. Howeve r, take anoth e r look. It's really a straightforward tra nslation of Bre nt's origin al code, which was wt·itte n in Algol. (No wonder we do n 't find many copies of it!) The many GOTOs in th e Fo rtra n ve rsio n me re ly re present the limita tions of Fo rtra n IV, n o t Mittlemann and Spe lluci. Fo rtun ate ly, we a re not limited to Fo rtra n IV. I took a look at fmin . f myself, to see what it might have looked like had it auth o rs had access to th e structured constru cts of Fo rtran 77 o r 90. Not surprising- ly, since it was de rived from th e structured language Algol, the code unravels ni cely. Fo r th ose of you who like Fortra n, a copy of the mod- ifi ed code is shown in Listing 1. If I've do ne no thing e lse in thi s seri es, a t least I've give n th e world a version of Bre n t's algorithm th at o ne can actually read. Comparing th e Fortran code from fmin. f with the C code from Recipes, I was struck by two things. First, they are almost identical; even the same vari- able names are used in most places, 38 SEPTEMBER 2000 Embedded Systems Programming netlib. org/cgi-

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10