On Fri, 24 Aug 2001 18:36:35 +0200, "Rune"
<run### [at] mobilixnetdk> wrote:

>...what is the most efficient (fast) method to find out which X value
>(between 0 and 1) returns a given value F(X) (also between 0 and 1) ?

Binary search is fast, but golden ratio searching is faster because it
evaluates three intervals at once and discards two of them.

First of all, I should mention that the golden ratio (let's call it R)
is the only number between 0 and 1 which satisfies the equation 1+R =
1/R. It is approximately equal to 0.618 or more precisely
0.5*(sqrt(5)-1).

The golden ratio (or golden mean) search utilizes this property. It is
the fastest way to find the minimum of a function. Since you're
looking for x : F(x) = X (given), you will have to analyze the
function G(x) = abs(F(x) - X)) which will give 0 at x = X.
See how it works.

1. Take your interval [x1, x2] and evaluate the function at x1,
(1-R)*(x1+x2), R*(x1+x2) and x2 (let's call these A, B, C and D for
ease.)

2. If F(A) > F(B) > F(C) then the minimum can not be in the interval
[A; C]. If F(B) > F(C) > F(D) then the minimum can not be in the
interval [B; D]. 

3. Since we assume there is exactly one minimum in [A; D], only one of
these conditions will be satisfied. We take that interval ( [B; D] or
[A; C] respectively ) and pass it on to step 1. The good thing about
it, and that's why we used the golden mean, is that in that interval
we not only know the values of F at the endpoints, but we also know it
in one of F(B) or F(C), so we only need to calculate one additional
sample. Why this is so is LAEFTR :)

HTH and let us know the results :) I am esp. interested since my math
books claim it is faster than regular binary search.


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message