"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