Oxford interview problem #2

-- Searching for the maximum (http://www.cs.ox.ac.uk/admissions/ugrad/Sample_interview_problems)

findMax' _ a b xa xb 0
    | a < b = (xb, b)
    | otherwise = (xa, a)
findMax' f a b xa xb i
    | a < b = let xc = xb + d
              in  findMax' f b (f xc) xb xc (i - 1)
    | otherwise = let xc = xa - d
                  in  findMax' f (f xc) a xc xa (i - 1)
    where d = (xb - xa) * ((sqrt 5) - 1) / 2

findMax f = let xa = (3 - sqrt 5) / 2
                xb = 1 - xa
            in  findMax' f (f xa) (f xb) xa xb

{- Explanation
Two values are read at each step.
If the left value is smaller, everything to its left is discarded.
Otherwise, everything to the right of the right value is discarded.
The larger value is passed on to the next step, meaning only 1 new value is taken.

 |    |  |
b|    |  +
a|    +  |
 |    |  |
 |____|__|____|
 0   xa  xb   1
b > a, so move right:
 |####   | |
a|####   + |
b|####   | +
 |####   | |
 |_##_|__|_|__|
 0      xa xb 1
Note that old xb and new xa are the same, so no remeasuring takes place.

The value xa = (3 - sqrt 5) / 2 comes about through solving:
-----|---|-----
(  x + y + x  ) / x
      ==
---|-|---
( x  + y) / y
where x + y + x = 1. The value of d comes about in a similar way, but is based on a given y,
rather than a given 2*x + y.
Both numbers are heavily related to the golden ratio:
(3 - sqrt 5) / 2 == 2 - phi
((sqrt 5) - 1) / 2 == phi - 1
                   == 1 / phi
-}