Rune wrote:
> 
> "John VanSickle" wrote:
> > If you don't know the function, how do you evaluate it at X?
> 
> I ask somebody to do it, then he tells me the result. Or rather, my
> code asks another part of my code to evaluate it at X the other part
> returns the result.
> 
> As you probably have guessed, the function is too complex to find the
> inverse of mathematically, so I have to use approximation. And I
> simply asked for a fast way to do that.

The only way that will be much faster is Newton's method, which
involves taking the first-order derivative of the function.  If that
is too complicated, then the divide-and-conquer approach is as fast as
you are going to get.

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message

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

"John VanSickle" wrote:
> The only way that will be much faster is Newton's method, which
> involves taking the first-order derivative of the function.
> If that is too complicated, then the divide-and-conquer approach
> is as fast as you are going to get.

As it's apparent from the messages posted in this thread there's not one but
several "divide-and-conquer" approaches. (Unless "divide-and-conquer" is a
standardized term I'm not aware of.)

I only tried to divide in halves as I described, but have now learned that
there's much faster methods.

Rune
--
3D images and anims, include files, tutorials and more:
Rune's World:    http://rsj.mobilixnet.dk (updated June 26)
POV-Ray Users:   http://rsj.mobilixnet.dk/povrayusers/
POV-Ray Webring: http://webring.povray.co.uk

Post a reply to this message

"Peter Popov" wrote:
> Binary search is fast, but golden ratio searching is faster
> because it evaluates three intervals at once and discards
> two of them.

I've read your explanation but I'm afraid I don't get how it works.

It evaluates 3 intervals at once but that also take at least 3 times as many
calculations I would think?

And how does the fact that the sizes of the intervals are controlled by the
golden ratio make it any more effecient?

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

How can I be sure the minimum isn't in between two of the samples?

As you can see from my questions I haven't got a clue...

Rune
--
3D images and anims, include files, tutorials and more:
Rune's World:    http://rsj.mobilixnet.dk (updated June 26)
POV-Ray Users:   http://rsj.mobilixnet.dk/povrayusers/
POV-Ray Webring: http://webring.povray.co.uk

Post a reply to this message