Hi Denis,
On 12/14/2010 5:11 PM, Denis Lila wrote:
I have one question though: how fast does this have to be? I can come
up with fairly reasonable examples for which both CubicCurve2D.solveCubic
and the implementation I found give very inaccurate results
The existing method was not very accurate as you discovered so we don't
necessarily need to go too far in terms of accuracy if it means changing
its performance radically.
(i.e. evaluating the cubic on the computed "roots" gives numbers as
high as 1e-4). I read on the bug reports that what we should do is
treat the closed form as a crude approximation and then use the Newton
method to really find the roots. I like this idea (with perhaps the
exception of the Newton method - I think we might be better off
using something like false position, or even simply a binary search).
The binary search gives results that when evaluated are as small as
1e-17 which is as close to correct as possible in double precision
(because my termination condition was while(middle != start&& middle != end)).
That didn't even take an outrageous number of iterations - 77 was the
highest I observed.
How big are these errors expressed as multiples of the ULP of the
coefficients? Obviously 1e-17 is a lot smaller than 1e-4, but was 1e-17
representing "just a couple of bits of error" or was it still way off
with respect to the numbers being used? And were these fairly obscure
equations that were off?
Not knowing these answers, it is hard to prioritize the added accuracy
against the performance hit.
If the hit is very small for the vast majority of equations, and/or if
we had a test for "already close enough" that eliminated the need for
refining most roots then it might be worth it - otherwise we could
consider adding a second version that called the first and then refined
the results so the developer could choose the accuracy they needed.
Feel like running some timings?
4724552
4493128
4074742
4724556
(etc. Those were just the bugs I found on the first 2 pages of a bug
database search)
Double (triple, etc.) credit - woohoo! ;-)
Isn't there some sort of diminishing returns after the first duplicate ;-)
Not really, but if the number of dups is higher than some unknown value
then people start looking at you with raised eyebrows...
http://i18.tinypic.com/34461wi.jpg
...jim
