[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-core-devel
Subject:    Re: Need help for KSpread Maths
From:       "Dirk A. Mueller" <mueller () kde ! org>
Date:       1999-11-17 13:32:57
[Download RAW message or body]

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

[prev in list] [next in list] [prev in thread] [next in thread]