For me, implementing code really helps me to understand the algorithms (i need to know) better. It might sound a bit odd in that you might need to understand the algorithm before you can implement it. And that’s partially true. An understanding is definitely required. But, with TDD and iterative processes ingrained, discovery of what makes the algorithm tick is made possible through doing it (by repetition and/or implementation).
Repetition helps you to understand it and use it. Implementing it in code is like rediscovering the algorithm from the beginning. It’s a small taste of that journey- and it’s addictive 🙂 Anyhooo, the Golden Section Search is not an exception- but surprisingly trivial. Maybe it was just all the fluff around the topic that got me distracted….
class Golden ... def search(tolerance) return if(@b - @a) <= tolerance dif =R*(@b-@a) x1 = @b - dif x2 = @a + dif vx1 = i_eval(x1) vx2 = i_eval(x2) if(vx1 > vx2) @b = x2 else @a = x1 end search(tolerance) end ... end
“i_eval” just evaluates the formula you supply (and uses the built-in Ruby expression evaluation) but the part that makes the grok for me is the if(vx1 > vx2) bit.
The way the text books explain it is pretty long-winded. The interval of uncertainty changes, but you’ve got the unknowns a,b,x1 and x2 floating around and changing positions all the time during the explanation. Plus you’ve got to now try remember case 1, case 2 and case 3. Eish. And all that inter-mixed with function and set notation. But that can be maths for you: pick any number between 0 and 10 => pick any integer from the domain of real numbers over the interval from, and including 0 to, and including 10.
The short of it lies in… :
‘b’ changes to x2 if vx2 [or f(x2)] is smaller (or equal) and
‘a’ changes to x1 if vx1 [or f(x1)] is smaller ..
… for the next iteration, everything else keeps the same value. That’s it.
And graphically, it also makes more sense to simplify that for one second and draw the lines in and see how ‘a’ and ‘b’ move along the axis iteration after iteration. Once that’s settled, going back to the ever pedantic yet accurate language of maths is then a whole bunch easier.