Embedded Systems December 2000 Vol13_13

Issue link:

Contents of this Issue


Page 17 of 197

PROGRAMMER'S TOOLBOX • Before each of the last few columns, I had hoped to wrap up the study in a blaze of glory, and present you with a totally finished, canned algorithm, a la Br.ent, that could solve any minimization problem we throw at it. Another point occurred to me as I programming world as the algoriulm of cho ice. Yet no one seems to be quite sure how it does what it does. The gen- eral notion of mixing golden sectio n and quadratic fit is straightforward enough, but ule details of such fea- lUres as the hal t criteria, or tlle logic to decide when to iruect a golden section step, arc retained as just so much witchcraft. I suppose it goes without saying that I do n't consider uch a sit- uation acceptable . Back to the grindstone This problem seems to have no end to it. The deeper 1 get into it, the deeper I get in to it, so to speak. J feel a litue bit like Brer Fox, in the Uncle Remus story, fighting the Tarbaby. (If you have never heard of Brer Fox, the Tarbaby, or Uncle Remus, don' t worry about it. The story comes from anoth- er generation, and it's no lo nger po lit- ically correct. It's still a great story, and th ose who missed it have bee n de prived of some precio us and insightful lessons.) Befo re each of th e las t few columns, I had hoped to wrap up the slUdy in a blaze of glory, and present you WiUl a to tally finished, canned algorithm, it la Brent, that could olve any minimization problem we throw at it. This se ri es must surely already be tlle longest running in a magazine like ESP. It's become more of a daytimc soap Ulan a collection of articl es; it may never end. Each time I've thought myself close to an end, I've had to fa ll back and regroup as I learned mo re about the problem, and/ o r had new thoughts that caused me to reulink things I had previously thought werc indisputable givens. So this monul I have some good ncws and some bad news. The bad news is that, no, you won 't find the final solu tion in this mo nth 's column, either. In fact, that elusive, ambitio us goal seems to be receding from me; I am not gaining on it-yet. The good news is that, a you might have imag- ined, ] have been thinking about this problem quite a lot, and the more I think about it, tlle more good ideas I have. Each of them seems to take us further afield from Bre lll's method, though the general approach of mix- ing golden sections and parabolic fi ts remains. But I believe ulat this depal-- tlll-e mus t be a good th i n g because th e reason I began su-aying from Brent is that 1 had concerns about it. By not trying to emulate Brent, I've come up witll a lot of new stuff I think you will find interesting and useful , and ule end product should be some thing worth waiting for. Speaking fo r myself, I'm excited and ready to attack tlle problem wi th renewed vigor (vaca- tions have a way of in spiring such feel- ings) . For now, at least, I am not going to try to hurry the proces , but rather concenU-ate on getting all of my ideas in to some semblance of o rder. Regarding efficiency In my last column, Moving Right Along (October 2000, p. 17), I mentioned Ulat software like Brent's is so difficult to fol- low because it's written witll efficiency, rather Ulan readabili ty, uppcrmost in mind. These algorithms tend to gct used in other algorithms, such as multivariate minimization problems, so they must be very, very fast. But at this poin t we don't want fast so much as understandable. So in that column and ulis one, I'm con- centrating on writing an algorithm ulat's easily understandable. We can always optimize tlle implementation later, but tlle algoritllm will not change. 16 DECEMBER 2000 Embedded Systems Programming was preparing fo r this article . 1 can hardly claim it is profound, but it's def- initely worth mentioning: the art of software engineering has not stood still since Brent's day. Think about it. All the programs I've been able to find on minimizatio n, or almost any other canned mctllod [o r that matter, are written in the style of '70s Foru-an pro- grams. Some of them actuaUy are old Fortran programs, translated into C or C++. One popular tex t, whose title I'll leave out this month (but you all know who I mean ), eve n goes so far as to override the C indexing convention, so the autllors can write their software witll indices starting at 1 instead of O. That approach must surely be close to the ultimate in lazy translation. When 1 was writing the oftware for the last column, I collected the various parts of the algorithm into subrou- tines, with arguments passed in and out to control modulari ty. I also decid- ed to let each subroutine inform me how successful it was, by returning a flag indicating success or fa ilure. If, for example, a quadratic fit fails to give a reliable valu e, tlle fun ction that per- forms the fit is in the best position to tell us whe th er it succeeded, and thereby trigger a golden ratio bisec- tion. I ended up witll fun ctions that returned a Boolean variable to indi- cate success or failure. In the midst of this process, howev- er, I found myself constrained a bit by having the functio n return only a Boolean. It would be a lot beller if it could suggest the next step, so Lhe dl-i- ver program doesn't have to guess. In preparaLion for this column, I asked myself, can one get a called function to suggest which way to go next? The answe r is yes, using a state machine. This happens to be one of my favo ri te approaches fo r embedded software involving complex logic. The implemen u'1tion of a state machine is the kind of thing thaL rar ely gets done in Fortran, because the language- at least, early versions of it-didn't sup- port the enumerated type that makes

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems December 2000 Vol13_13