use PARI's qfbredsl2() for binary quadratic forms

[yyyyx4]

Currently, Sage cannot compute the transformation matrix when reducing definite binary quadratic forms:

sage: BinaryQF([1,2,3]).reduced_form(transformation=True)
# ...
NotImplementedError: reduction of definite binary quadratic forms with transformation=True is not implemented

We can use PARI's qfbredsl2() to make this work.

Component: quadratic forms

Author: Lorenz Panny

Branch/Commit: c2c91db

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/34229

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1bc1c1e	use PARI's qfbredsl2()
e540a90	add test for trac #34229

[sagetrac-git]

Changed commit from e2e2d4b to e540a90

[sagetrac-git]

Changed commit from e540a90 to 7a058f3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0eb89f0	PARI doesn't support negative definite forms; emulate using positive definite forms
e1e17f3	code style tweaks
271746f	doc tweaks
7a058f3	slightly more effective caching

[sagetrac-git]

Changed commit from 7a058f3 to cc19834

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cc19834

some more minor doc tweaks

[yyyyx4]

comment:5

The patchbot failure seems unrelated.

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:6

I don't understand why content becomes a cached method here. If discriminant is already one, dividing it by 4 should be costless. Could you provide timing to justify this change?

Instead of self.content() == 1 I would rather use self.content().is_one().

To my mind, all changes similar to

-        Return if ``self`` is identically zero.
+        Determine if ``self`` is identically zero.

makes the specification less precise. The word "determines" does not describe the output of the function.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0eea79e

use is_...() methods for comparing to 0 or 1

[sagetrac-git]

Changed commit from cc19834 to 0eea79e

[yyyyx4]

comment:8

Replying to @videlec:

I don't understand why content becomes a cached method here. If discriminant is already one, dividing it by 4 should be costless. Could you provide timing to justify this change?

I think the diff you're looking at is cut in an unfortunate place — the content isn't the discriminant divided by four! The reasoning behind the changes to caching (commit 7a058f3026c) is:

• Replace gcd([a,b,c]) by .content() in .is_primitive() because that's what it is.
• Move the @cached_method up from .is_primitive() to .content() because it's more general and .is_one() is cheap.
• Remove @cached_method from .is_zero() because .content() is now cached and .is_zero() is cheap.

To my mind, all changes similar to

-        Return if ``self`` is identically zero.
+        Determine if ``self`` is identically zero.

makes the specification less precise. The word "determines" does not describe the output of the function.

My problem with "return if X" was that it can be read as if X then return [a thing?] else [catch fire?]. But I don't really care; surely noone will be confused by either phrasing.

[videlec]

comment:9

Replying to @yyyyx4:

Replying to @videlec:

I don't understand why content becomes a cached method here. If discriminant is already one, dividing it by 4 should be costless. Could you provide timing to justify this change?

I think the diff you're looking at is cut in an unfortunate place — the content isn't the discriminant divided by four! The reasoning behind the changes to caching (commit 7a058f3026c) is:

• Replace gcd([a,b,c]) by .content() in .is_primitive() because that's what it is.
• Move the @cached_method up from .is_primitive() to .content() because it's more general and .is_one() is cheap.
• Remove @cached_method from .is_zero() because .content() is now cached and .is_zero() is cheap.

Oh I see. Thanks for the explanation. I should have looked more carefully at the final code rather than the diff.

To my mind, all changes similar to

-        Return if ``self`` is identically zero.
+        Determine if ``self`` is identically zero.

makes the specification less precise. The word "determines" does not describe the output of the function.

My problem with "return if X" was that it can be read as if X then return [a thing?] else [catch fire?]. But I don't really care; surely noone will be confused by either phrasing.

I agree that the initial sentence was not perfect either. In most places we can read Return whether ``self`` is identically zero. which I like better.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c2c91db

rephrase per reviewer's request

[sagetrac-git]

Changed commit from 0eea79e to c2c91db

[vbraun]

Changed branch from public/use_pari_qfbredsl2 to c2c91db