Opened 12 years ago

Closed 12 years ago

#3857 closed defect (fixed)

[with patches, positive review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

Reported by: choldsworth Owned by: choldsworth
Priority: major Milestone: sage-3.1.2
Component: number theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

For example

sage: BinaryQF_reduced_representatives(-63)

[2*x^2 - x*y + 8*y^2,
 4*x^2 - x*y + 4*y^2,
 x^2 + x*y + 16*y^2,
 2*x^2 + x*y + 8*y^2,
 4*x^2 + x*y + 4*y^2,
 3*x^2 + 3*x*y + 6*y^2]

However, clearly:

4*x^2 - x*y + 4*y^2

isn't a reduced form. BinaryQF_reduced_representatives is incorrectly classifying some forms.

Attachments (4)

new_patch.patch (1.5 KB) - added by choldsworth 12 years ago.
3857.patch (2.5 KB) - added by choldsworth 12 years ago.
Patch implementing a superior BinaryQF_reduced_representatives method.
sage-trac3857.patch (2.0 KB) - added by cremona 12 years ago.
Apply after the previous patch (ignore the first one)
3857-nils-1.patch (2.2 KB) - added by NilsSkoruppa 12 years ago.
Apply after the previous two patches (ignore the first one)

Download all attachments as: .zip

Change History (15)

Changed 12 years ago by choldsworth

comment:1 Changed 12 years ago by choldsworth

  • Summary changed from BinaryQF_reduced_representatives in binry_qf.py produces extra unreduced forms to BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

comment:2 Changed 12 years ago by choldsworth

  • Summary changed from BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms to [with patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

comment:3 Changed 12 years ago by cremona

  • Summary changed from [with patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms to [with patch; with positive review but serious reservations] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

The patch applies cleanly to 3.1.1 and doctests pass.

However, there are some things I really do not like about this implementation:

  1. self.reduce() computes (if necessary) caches and returns the reduced form equivalent to self. I would expect it to change self into the reduced form, and have a different function self.reduced_form() to do what this function does.
  1. The function is_reduced() actually reduces self and tests if the result is the same as self. This is potentially very expensive! To test is_reduced() you should just test that the usual inequalities are satisfied.
  1. The function BinaryQF_reduced_representatives(D) -- where the bug was -- proceeds in a way very different to what I have always done, with the outer loop being over b. For a start you should only loop over b's of the same parity as D, not over all b's and then compute and test if b^2-D is a multiple of 4. Then, this method requires factoring all those values of (b^2-D)/4 to get possible a's -- another expensive and quite unnecessary set of computations. Finally, the list is not sorted as I think it should be.

I would like to rewrite this function, but the current patch can be applied and a new ticket opened if anyone agrees with me.

Changed 12 years ago by choldsworth

Patch implementing a superior BinaryQF_reduced_representatives method.

comment:4 Changed 12 years ago by choldsworth

I have submitted a new patch (superseding my first patch), re-implementing the BinaryQF_reduced_representatives method, and addressing your point 3.

I agree the other points need fixing but feel they should have their own ticket, or at least separate patches.

Here are some timings from the new method.

Old code:

sage: timeit("BinaryQF_reduced_representatives(-4004)")
5 loops, best of 3: 29.6 s per loop

New code:

sage: timeit("BinaryQF_reduced_representatives(-4004)")
5 loops, best of 3: 38.9 ms per loop

comment:5 Changed 12 years ago by choldsworth

  • Summary changed from [with patch; with positive review but serious reservations] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms to [with patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

Changed 12 years ago by cremona

Apply after the previous patch (ignore the first one)

comment:6 Changed 12 years ago by cremona

  • Summary changed from [with patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms to [with new patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

That is some speedup! When I tested the same myself I noticed that during the (long) test of the old code the machine was running lisp, meaning that something was happening using maxima, which it should not. But that is now in the past.

I have simplified the code a bit more, using xsrange() for the a and b loops, and letting b only loop from 0 (or 1) to a, adding in the form with -b if needed. This gives another speedup factor of about 2.

This should now have a new independent review -- as far as I am concerned it is ok!

I'll now review the other patches you made in response to my first two points.

Changed 12 years ago by NilsSkoruppa

Apply after the previous two patches (ignore the first one)

comment:7 Changed 12 years ago by NilsSkoruppa

  • Owner changed from was to NilsSkoruppa
  • Summary changed from [with new patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms to [with another new patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

The last patch seemed to be OK. However, I noticed that the bounds for the search region for reduced forms was not optimal. I inserted the optimal bounds and modified the loop logic accordingly, and I gained a speedup of a factor around 10.

Before:

sage: timeit( 'BinaryQF_reduced_representatives(-998995)')
5 loops, best of 3: 5.52 s per loop

After:

sage: timeit( 'BinaryQF_reduced_representatives(-998995)')
5 loops, best of 3: 547 ms per loop

Doctest runs successfully and I tested 1000 discriminants with 6 digits each, compared to the corresponding results produced by the last patch and compared number of produced forms with Hurwitz class numbers in gp. I think its OK now. Ready for being reviewed.

comment:8 Changed 12 years ago by cremona

Thanks for the review and great improvement (improved lower bound for b).

I applied all three patches (that is, all but the first attached to this ticket) to 3.1.2.alpha4 successfully, and all doctests in sage.quadraticforms pass. Nils's testing vs. gp was a very good idea, so I think we can be confident of this.

I vote for this to be adopted, and hope the editor will not feel the need to get in a new reviewer (so far, each reviewer has vastly improved the previous code, but I don't think we can hope for that to happen again!)

comment:9 Changed 12 years ago by mabshoff

  • Owner changed from NilsSkoruppa to choldsworth

comment:10 Changed 12 years ago by AlexGhitza

  • Summary changed from [with another new patch; needs review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms to [with patches, positive review] BinaryQF_reduced_representatives in binary_qf.py produces extra unreduced forms

comment:11 Changed 12 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged 3857.patch, sage-trac3857.patch and 3857-nils-1.patch in Sage 3.1.2.rc0

Note: See TracTickets for help on using tickets.