From kde-core-devel  Wed Nov 17 13:32:57 1999
From: "Dirk A. Mueller" <mueller () kde ! org>
Date: Wed, 17 Nov 1999 13:32:57 +0000
To: kde-core-devel
Subject: Re: Need help for KSpread Maths
X-MARC-Message: https://marc.info/?l=kde-core-devel&m=94284570109924

On Mit, 17 Nov 1999, weis wrote:

> There are many algorithms which help you here, but they want
> a) a range [a,b] to search in which can be very big with double values.
> b) two points a and b, so that f(a)*f(b) < 0.

good old Newton ;-)

> Can anyone tell me what to do here. Excel is getting quick and good
> results, so there must be a way.

I guess they're "scanning" for two points, where one has a positive result
and one has a negative. 

if a is the step intervall (a doesn't need to be small, it's no problem if
you don't find a small intervall, newton will optimize it very fast) you can 
start testing with f(0), f(+a), f(-a), f(2*a), f(-2*a) and so on. you need
to remember the smallest k*a where f(+/-k*a) was positive or negative.
that's your interval. 

the exception is when f'(x) = 0. 

the problem is that newton needs a steady function. I don't think that
all possible formulars are steady?


Maybe it's a good idea to look at povray's source. they have also
implemented this algorithm and probably found some cool optimizations. 


Dirk