Opened 12 years ago

Closed 12 years ago

Last modified 5 years ago

#7947 closed defect (fixed)

iteration error in QuadraticForm.vectors_by_length()

Reported by: tornaria Owned by: tornaria
Priority: major Milestone: sage-4.3.3
Component: quadratic forms Keywords:
Cc: jonhanke Merged in: sage-4.3.3.alpha0
Authors: Gonzalo Tornaría Reviewers: Jonathan Hanke
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

After the fix in #7100 (rounding issues), there's still a bug in the vectors_by_length() code:

----------------------------------------------------------------------
| Sage Version 4.3, Release Date: 2009-12-24                         |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: Q = QuadraticForm(ZZ, 4, [1,-1,-1,-1, 1,0,0, 4,-3, 4])
sage: Q.vectors_by_length(3)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/home/tornaria/.sage/temp/sage/9609/_home_tornaria__sage_init_sage_0.py in <module>()

/home/tornaria/sage/sage-4.3/local/lib/python2.6/site-packages/sage/quadratic_forms/quadratic_form__split_local_covering.pyc in vectors_by_length(self, bound)
    213             ## Now go back and compute the bounds...
    214             ## 2. Compute bounds
--> 215             Z = (T[i] / Q[i][i]).sqrt(extend=False)
    216             L[i] = ( Z - U[i]).floor()
    217             x[i] = (-Z - U[i]).ceil()

/home/tornaria/sage/sage-4.3/local/lib/python2.6/site-packages/sage/rings/real_double.so in sage.rings.real_double.RealDoubleElement.sqrt (sage/rings/real_double.c:10382)()

ValueError: negative number -0.888887555556 does not have a square root in the real field

You can tell this is not a rounding issue from the error message.

Attachments (1)

trac_7947.patch (1.7 KB) - added by tornaria 12 years ago.
fix iteration error in QuadraticForm?.vectors_by_length()

Download all attachments as: .zip

Change History (6)

Changed 12 years ago by tornaria

fix iteration error in QuadraticForm?.vectors_by_length()

comment:1 Changed 12 years ago by tornaria

  • Status changed from new to needs_review

comment:2 Changed 12 years ago by jonhanke

  • Status changed from needs_review to positive_review

This is a subtle bug which arises because negative numbers are created when the round and ceil functions cause upper and lower bounds to inadvertently move past each other. The patch discards partial vectors where this happens by incrementing (successively if necessary) to the next possible partial vector, which is the correct thing to do. Also the patch omits using a condition (i<n-1) as in Comment 3a slightly below the patch, which is ok because zero will always be an allowed value for the (n-1)st entry since that first allowed interval is not shifted at all.

The patch looks good. =)

comment:3 Changed 12 years ago by tornaria

  • Authors set to Gonzalo Tornaria
  • Reviewers set to Jonathan Hanke

comment:4 Changed 12 years ago by mpatel

  • Merged in set to sage-4.3.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:5 Changed 5 years ago by chapoton

  • Authors changed from Gonzalo Tornaria to Gonzalo Tornaría
Note: See TracTickets for help on using tickets.