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