If I have an unknown function...

F(X)

...and I only know the following...

F(0) = 0

F(1) = 1

F(X) increases when X increases

...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) ?

I have tried a method that keeps guessing in the middle of a range, and each
guess divides the range in two until the guess comes close enough. However,
I'd like to learn about methods that parses faster.

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

Rune wrote:
> 
> If I have an unknown function...
> 
> F(X)
> 
> ...and I only know the following...
> 
> F(0) = 0
> 
> F(1) = 1
> 
> F(X) increases when X increases
> 
> ...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) ?
> 
> I have tried a method that keeps guessing in the middle of a range,
> and each guess divides the range in two until the guess comes close
> enough. However, I'd like to learn about methods that parses faster.

If you don't know the function, how do you evaluate it at X?

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message

Rune -

I hope this response is neither too simplistic or too basic for you, but
this is my best attempt at helping you out. :)

That method (the bisection method) is the fastest general purpose method
for searching a sorted array, which is very similar to what you're
trying to do.  And I think that if you really know nothing about your
function this might still be the fastest method.

However, if you know that the function is continuous and fairly
ordinary, there are a lot of methods that work really well.  According
to "Applied Numerical Methods for Digital Computation" (Harper and Row,
1985) one of the fastest is called the Secant Method.

I'll try to describe it here, but describing algorithms in plain words
is pretty difficult.  Anyway, If you know that the value you are
searching for is within some interval (i.e. between 0 and 1), you
construct a straight line that goes through the points <0,F(0)> and
<1,F(1)>

y = (F(1)-F(0)) x + F(0)

then you solve the equation y = VALUE for x.  This is then called x0. 
The trick is to figure out whether the real solution is between 0 and x0
OR between x0 and 1, very similar to what you had to do with the
bisection method.  Then you keep doing this methhod on the correct
interval (recursively) until you get a solution that is "close enough".

Depending on the result from your calculation for x0, you will choose to
subdivide the interval (0,x0) or the interval (x0,1).  If it is between
between 0 and x0,

	solve the equation
		VALUE = (F(x0)-F(0))/x0 x + F(0)
	and call the solution x1

OR if the real solution is between x0 and 1,

	solve the equation
		VALUE = (F(1)-F(x0))/(1-x0) x + F(x0)
	and call this solution x1.

Anyway, every time you find a new estimation of the position of VALUE
(x0, x1, x2, x3,...) you need to choose the best interval to continue
your search.  That part is very similar to the bisection method that you
were using.

- Ben

Post a reply to this message

You can also go to your local university library, get the book
"Numerical Recipes" (by Press, Teukolsky, Vetterling and Flannery) and
apply the methods and algorithms given in section 9.2 -- "Root finding
in one dimension" -- to the function G defined by

G(x) = F(x) - VALUE.

By the way, it's never bad to go and see what "Numerical Recipes" has to
say about any question related to numerical analysis : their comments
are often both insightfull and enlightening.

Stephane.

Post a reply to this message

"Ben Birdsey" wrote:
> I hope this response is neither too simplistic or
> too basic for you, but this is my best attempt at
> helping you out. :)

Thanks, the answer is just fine - I'll try it out now! :)

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

"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.

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

I used this in my lspline3 macro.

Find segment where the desired location (input parameter) is, then:

#local slen=; // segment length
#local l=; // from start of segment to location
#local e=0.01;
#local t1=l/slen; // relative location in segment
#local err=0.001*slen; //tolerance
#local dif=err+1;
#while (abs(dif)>err)
  lensp(t1,...,len) // returns length from start of segment to parameter
  #local dif=l-len;
  #local t2=t1+e;
  lensp(t2,...,len2)
  #local t1=e/(len2-len)*dif+t1;
#end

t1 is the parameter pointing to location.

_____________
Kari Kivisalo

Post a reply to this message

"Rune" wrote:
> Thanks, the answer is just fine - I'll try it out now! :)

For the record it made the parsing more than twice as fast! :)

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

Stephane -

You're totally right about looking at "Numerical Recipies"(NR).  I have
a copy and I have found it to be invaluable!

I knew that some kind of bisection search was going to be the fastest
method that didn't depend on the derivative (of the unknown function)
and I did consider looking at NR, but I was worried that there might be
too much info there to convey in an e-mail!


- Ben

Post a reply to this message

What do you want to use this algorithm for?  It sounds like you want to
place something on a fractal terrain or something.

- Ben

Post a reply to this message

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