Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

diagrams-solve-0.1.1 test suite failure #4

Open
peti opened this Issue Jul 19, 2017 · 6 comments

Comments

Projects
None yet
4 participants
@peti
Copy link

peti commented Jul 19, 2017

Citing from https://nix-cache.s3.amazonaws.com/log/n980597fmjsmaxqfi9q9ziqsmd5c8q9l-diagrams-solve-0.1.1.drv:

running tests
Running 1 test suites...
Test suite tests: RUNNING...
Solve
  solutions found satisfy quadratic equation: OK
    +++ OK, passed 100 tests.
  solutions found satisfy cubic equation:     FAIL
    *** Failed! Falsifiable (after 62 tests and 27 shrinks): 
    89.0
    0.0
    1.0
    -2286.0
    Use --quickcheck-replay '61 TFGenR 000018C68371466B000000001DCD6500000000000000E26100000018AE17A400 0 9223372036854775806 63 0' to reproduce.

1 out of 2 tests failed (0.00s)
Test suite tests: FAIL
@byorgey

This comment has been minimized.

Copy link
Member

byorgey commented Jul 22, 2017

Thanks for the report. This is actually a known issue; in particular, the issue is that the solver is perhaps not as numerically stable as it could be, and occasionally will fail to return a result within the expected tolerance. I tried to improve this situation with 44ff207 but I don't really know what I'm doing and as you can see that experiment has never actually been merged. Ultimately it's a bit silly for us to be using our own homegrown solver methods; I would love to farm this work out to an optimized, dedicated root-finding package instead.

@robinp

This comment has been minimized.

Copy link

robinp commented Dec 5, 2017

Hit this with (-54, 0, 1, -3155). Please either improve or make the test more tolerant?

@byorgey

This comment has been minimized.

Copy link
Member

byorgey commented Dec 8, 2017

The test is already quite tolerant; no matter how tolerant we make it there always seem to exist some combination of coefficients that make it numerically unstable enough to fail. As explained above we don't have the expertise to improve things. Though it does remind me I should perhaps try using https://herbie.uwplse.org/ and see if it helps.

@blackgnezdo

This comment has been minimized.

Copy link

blackgnezdo commented Feb 6, 2019

And one more:

Solve
solutions found satisfy quadratic equation: OK
+++ OK, passed 100 tests.
solutions found satisfy cubic equation: FAIL
*** Failed! Falsifiable (after 67 tests and 14 shrinks):
33.76506136107823
55.0
28.0
-21603.0
Use --quickcheck-replay '66 TFGenR 3158287060CBD4EEF0BE48C7B4E5845AC63027C001E9BE5BD18903178C6E947E 0 15 4 0' to reproduce.

1 out of 2 tests failed (0.03s)

@byorgey

This comment has been minimized.

Copy link
Member

byorgey commented Feb 10, 2019

So I've started looking into better root-finding methods, here are my initial notes.

  • The math-functions package has root finding code (using Ridder's algorithm and/or Newton-Raphson) we could depend on, but it only finds a single root and you have to give it a starting bracket, which is not super useful in our context.
  • The dsp package has a module Polynomial.Roots containing an implementation of Laguerre's method, which finds all the (complex) roots, but it's GPL and I don't want to depend on the entire dsp package.
  • The hmatrix-gsl package has Numeric.GSL.Polynomials which has an interface to a root finder from GSL, but that is an even heavier-weight dependency.
  • I had looked before into implementing the Durand-Kerner method which can also find all roots (see misc/DKSolve.hs in the diagrams-lib repo, but I don't think I ever got it to work.
  • Apparently the Jenkins-Traub algorithm is widely used for root finding, but the only implementation I could find in Haskell is at https://github.com/frankwang95/jenkins_traub which doesn't seem like it comes with any particular guarantees.
@byorgey

This comment has been minimized.

Copy link
Member

byorgey commented Feb 14, 2019

I wrote a blog post about this: https://byorgey.wordpress.com/2019/02/13/finding-roots-of-polynomials-in-haskell/ Still don't know a good solution to do better than what we have currently.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.