[OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces

[Denis Lila]

Hi Jim.

> The test as it is has a test case (I just chose random numbers to
> check
> and got lucky - d'oh!) that generates 1 solution from the new code
> even
> though the equation had 2 distinct solutions that weren't even near
> each
> other...

I figured out why this happens. It's because of cancellation in the
computation of D (two large numbers are subtracted and the result is
supposed to be 0 or close to 0, but it's about 1e-7, which wasn't
enough to pass the iszero test). I've been working on this and I
came up with a couple of different ways. They are in the attached
file (it's a modified version of the file your CubicSolve.java).

The first thing I did was to modify solveCubicOld. I tried to get
a bit fancy and although I think I fixed the problems it had, the
end result is ugly, complicated and it has small problems, like
returning 3 very close roots when there should only be one.

The other solution is to just check if the roots of the derivative
are also roots of the cubic polynomial if only 1 root was computed
by the closed form algorithm. This doesn't have the numerical
accuracy of the first way (which used bisectRoots when things went wrong)
but it's much faster, doesn't have the multiple roots problem, and it's
much simpler. I called your trySolve function on a few hundred
polynomials with random roots in [-10, 10] and it never finds fewer
roots than there actually are. Sometimes it finds 3 roots when there are
only 2, but I don't think this is a huge problem.

I've attached what I have so far.

Regards,
Denis.

----- Original Message -----
> Hi Denis,
> 
> I'm attaching a test program I wrote that compares the old and new
> algorithms.
> 
> Obviously the old one missed a bunch of solutions because it
> classified
> all solutions as 1 or 3, but the new one also sometimes misses a
> solution. You might want to turn this into an automated test for the
> bug (and maybe use it as a stress test with a random number
> generator).
> 
> I think one problem might be that you use "is close to zero" to check
> if
> you should use special processing. I think any tests which say "do it
> this way and get fewer roots" should be conservative and if we are on
> the borderline and we can do the code that generates more solutions
> then
> we should generate more and them maybe refine the roots and eliminate
> duplicates. That way we can be (more) sure not to leave any roots
> unsolved.
> 

> 
> ...jim
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CubicSolver.java
Type: text/x-java
Size: 16972 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20110104/3be69ce9/CubicSolver.java>