-
-
Notifications
You must be signed in to change notification settings - Fork 405
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
binary_qf tests fail for a particular random seed #35292
Comments
@yyyyx4 - the errors are in a function you've written, according to |
@JohnCremona - maybe you know what's going on here? |
here is what's going on: (complete error dump in the issue description):
|
The form has zero discriminant -- it is a multiple of (16x - 83y)^2. In the code for solve_integer() it explicitly states that reducible forms are not supported. Looking at the code, it makes a change of variables so that the form becomes ax^2+bx*y, but then assumes that b is nonzero which it is not. So the method solve_integer() needs to catch this case. Instead of dividing y_num by Q._b when Q._b is 0, it should test whether y_num is 0 (and skip this x if not). Otherwise there are infinitely many solutions (e.g. think of solving x^2=1 for (x,y)) and it seems to meet the documentation to return just one. I volunteer to make a patch for this. |
@JohnCremona Sorry, I already fixed this in #35262! (GitHub shows a cross-reference above your comment for this reason, but indeed it's not easy to spot...) |
That's great, and your solution looks better than what I was thinking of doing anyway |
Recent versions of PARI have a `qfbcornacchia()` function which can replace special cases of `qfbsolve()` while being much faster. In this patch we add a path to `qfbcornacchia()` in the `BinaryQF.solve_integer()` method; it can be selected using an optional `algorithm=` argument. See the added doctest for an example of the speedup. Also fixes #35292. URL: #35262 Reported by: Lorenz Panny Reviewer(s): Lorenz Panny, Travis Scrimshaw
This is on SageMath 10.0.beta8.
|
Thanks for the report. This appears to be a PARI bug:
|
Thanks.
|
I just submitted it to the PARI bug tracker. (It's #2471.) |
Thanks, Lorenz.
|
https://en.m.wikipedia.org/wiki/Cornacchia's_algorithm does not seem to require the condition Bill mentions, so all this is very misleading. |
Either it is a bug in Wikipedia article, or in Pari... |
It's a documentation bug in Pari. I have fixed the doc in 'master'. The only point of allowing 4*p is to handle x^2 + xy + (1 + D)/4 y^2 = p when D = 3 (mod 4) by a change of variable. For the general case, one should use qfbsolve (a bit slower because the general case is more complicated), or make a change of variable to try both n = 1223277844 and n / 4 (non primitive solution). The special case handled in PARI only looks for a primitive solution (but may find a non-primitive one). |
…rnacchia algorithm This patch should fix the random doctest failure pointed out in sagemath#35292 (comment), following an upstream documentation update that was applied to resolve [PARI bug sagemath#2471](https://pari.math.u-bordeaux.fr/cgi- bin/bugreport.cgi?bug=2471). URL: sagemath#35486 Reported by: Lorenz Panny Reviewer(s): Frédéric Chapoton, Lorenz Panny, Rémy Oudompheng
…rnacchia algorithm This patch should fix the random doctest failure pointed out in sagemath#35292 (comment), following an upstream documentation update that was applied to resolve [PARI bug sagemath#2471](https://pari.math.u-bordeaux.fr/cgi- bin/bugreport.cgi?bug=2471). URL: sagemath#35486 Reported by: Lorenz Panny Reviewer(s): Frédéric Chapoton, Lorenz Panny, Rémy Oudompheng
Is there an existing issue for this?
Did you read the documentation and troubleshoot guide?
Environment
Steps To Reproduce
See below (Additional info) for an easy reproducer at Sage prompt:
build 10.0.beta4 and run
on #35290 (where I was lucky to get this random seed), and also reproducible on Fedora box, an error as below.
OK with several other seeds.
Expected Behavior
no error
Actual Behavior
Additional Information
here is the reproducer without random stuff - obtained by printing values in the test for the
random seed in question:
The text was updated successfully, but these errors were encountered: