Opened 7 years ago

Closed 5 years ago

#13101 closed defect (fixed)

enumerate_totallyreal_fields bug fix

Reported by: jvoight Owned by: davidloeffler
Priority: major Milestone: sage-6.1
Component: number fields Keywords: sd51
Cc: Merged in:
Authors: Robert Harron, John Voight, Frédéric Chapoton Reviewers: Alex Ghitza, Peter Bruin
Report Upstream: N/A Work issues:
Branch: u/vbraun/enumerate_totallyreal (Commits) Commit: 3923f3ad585170c563a4ba7f4d3edbe1c6356f96
Dependencies: Stopgaps:

Description (last modified by pbruin)

sage: enumerate_totallyreal_fields_all(8, 10^8)
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)

/home/jvoight/sage-4.2/devel/sage-main/sage/rings/number_field/<ipython console> in <module>()

/usr/local/share/sage-5.0/local/lib/python2.7/site-packages/sage/rings/number_field/totallyreal_rel.pyc in enumerate_totallyreal_fields_all(n, B, verbose, return_seqs)
    887                     print "Taking F =", Sds[i][1]
    888                 F = NumberField(ZZx(Sds[i][1]), 't')
--> 889                 T = enumerate_totallyreal_fields_rel(F, n/d, B, verbose=verbose, return_seqs=return_seqs)
    890                 if return_seqs:
    891                     for i in range(3):

/usr/local/share/sage-5.0/local/lib/python2.7/site-packages/sage/rings/number_field/totallyreal_rel.pyc in enumerate_totallyreal_fields_rel(F, m, B, a, verbose, return_seqs)
    726         T.incr(f_out,verbose)
    727     else:
--> 728         T.incr(f_out)
    729 
    730     Fx = PolynomialRing(F, 'xF')

/usr/local/share/sage-5.0/local/lib/python2.7/site-packages/sage/rings/number_field/totallyreal_rel.pyc in incr(self, f_out, verbose, haltk)
    542                         # New bounds from Lagrange multiplier in degree 3.

    543                         bminmax = [lagrange_degree_3(m,v(self.a[m-1]),v(self.a[m-2]),v(self.a[m-3])) for v in self.Foo]
--> 544                         self.b_lower = [bminmax[i][0] for i in range(len(bminmax))]
    545                         self.b_upper = [bminmax[i][1] for i in range(len(bminmax))]
    546 

IndexError: list index out of range

The fix is easy: we just need to add the lines

    if len(z4minmax) < 1: 
        z4minmax = [0.0, -1.0]
    return z4minmax

before line 295 of sage/rings/number_field/totallyreal_data.pyx. (Yes, I'm still intimidated by creating a patch.)

The issue was that when the lagrange multipliers gives contradictory bounds (a good thing, since it says the enumeration can stop in that branch), it was not sending a pair of bounds, just a single element, causing a type error.

JV

Apply: trac_13101_bug_in_enumerate_totallyreal_fields_all.patch, trac_13101_review.patch, trac_13101_long_time.patch,

Attachments (3)

trac_13101_bug_in_enumerate_totallyreal_fields_all.patch (1.5 KB) - added by robharron 6 years ago.
trac_13101_review.patch (5.3 KB) - added by chapoton 6 years ago.
trac_13101_long_time.patch (660 bytes) - added by pbruin 5 years ago.
mark doctest as "long time"

Download all attachments as: .zip

Change History (17)

comment:1 Changed 6 years ago by robharron

  • Reviewers citro deleted
  • Status changed from new to needs_review

Okay, I made a patch with the change you mentioned (I think I figured out what indentation you meant, but double-check to make sure). The output of this command should be the empty array, right? That's what I gather from the data on your website/your paper.

(Also, I fixed a typo).

comment:2 Changed 6 years ago by robharron

  • Authors set to Robert Harron, John Voight

comment:3 Changed 6 years ago by jvoight

Thanks for doing this and for fixing the typo! Yes, the tabbing/formatting is correct. Am I allowed to review this? JV

comment:4 Changed 6 years ago by robharron

Hmm, I don't really know how that works. I mean, if you did, you'd probably want to remove your name from the authors... You could try, what's the worse that could happen?!

comment:5 Changed 6 years ago by AlexGhitza

  • Description modified (diff)

comment:6 Changed 6 years ago by AlexGhitza

  • Keywords sd51 added
  • Reviewers set to Alex Ghitza
  • Status changed from needs_review to positive_review

comment:7 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12
  • Status changed from positive_review to needs_work

The added doctest really takes too long. Can the bug be tested with a shorted test? Otherwise, simply mark the test something like

# not tested (too long time)

comment:8 follow-up: Changed 6 years ago by jvoight

Did someone add

sage: enumerate_totallyreal_fields_all(8, 10^8)

to the doctest? This was just an example that caused the stupid bug and I don't think it was ever intended for a doctest. But then we also probably want to keep it for future testing purposes, right?

There is an easy doctest in there already

enumerate_totallyreal_fields_rel(F, 2, 2000)

and for general purposes of testing, this should be enough, IMHO. JV

Last edited 6 years ago by jvoight (previous) (diff)

comment:9 in reply to: ↑ 8 Changed 6 years ago by robharron

Yeah, I added that doctest: every time there is a bug fix, there has to be a corresponding doctest added to show that the bug has been fixed. Since I'm not really familiar with the workings of this part of sage, I simply took the snippet of code from the bug report and added it as a doctest. What Jeroen is asking is whether there is a shorter test that would fail before this bug fix but pass afterwards, thus showing things were fixed. Can you cook one of those up?

Replying to jvoight:

Did someone add

sage: enumerate_totallyreal_fields_all(8, 10^8)

to the doctest? This was just an example that caused the stupid bug and I don't think it was ever intended for a doctest. But then we also probably want to keep it for future testing purposes, right?

There is an easy doctest in there already

enumerate_totallyreal_fields_rel(F, 2, 2000)

and for general purposes of testing, this should be enough, IMHO. JV

comment:10 Changed 6 years ago by jvoight

OK, got it. Then yes, just use

sage: enumerate_totallyreal_fields_all(8, 10^6)

which should return

[]

as the smallest totally real octic field has discriminant 282300416 > 106. This triggers the error on my unpatched version. Is this quick enough for the doctest?

JV

Changed 6 years ago by chapoton

comment:11 Changed 6 years ago by chapoton

  • Status changed from needs_work to needs_review

here is a review patch, with more reasonable tests.

comment:12 Changed 5 years ago by pbruin

  • Authors changed from Robert Harron, John Voight to Robert Harron, John Voight, Frédéric Chapoton
  • Description modified (diff)
  • Reviewers changed from Alex Ghitza to Alex Ghitza, Peter Bruin
  • Status changed from needs_review to positive_review

Looks good. The new doctest takes around 2 seconds on the AMD64 2.2 GHz system that I tested it on. I think marking this as "long time" is still justified; I'm adding this as a reviewer patch.

Changed 5 years ago by pbruin

mark doctest as "long time"

comment:13 Changed 5 years ago by vbraun

  • Branch set to u/vbraun/enumerate_totallyreal
  • Commit set to 3923f3ad585170c563a4ba7f4d3edbe1c6356f96

New commits:

3923f3aTrac 13101: mark doctest as "long time"
a807b94trac 13101 better doctest
cfd405bTrac 13101: Fix bug in enumerate_totallyreal_fields_all

comment:14 Changed 5 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.