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