Opened 4 years ago
Closed 18 months ago
#25934 closed defect (fixed)
Problem displaying a number field (fractional) ideal
Reported by:  cremona  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  number fields  Keywords:  NumberField, ideal 
Cc:  jdemeyer, slelievre  Merged in:  
Authors:  John Cremona  Reviewers:  Frédéric Chapoton, Samuel Lelièvre 
Report Upstream:  N/A  Work issues:  
Branch:  1e45e42 (Commits, GitHub, GitLab)  Commit:  1e45e421fe879eb9e306fde3745ef3cbc36bf43c 
Dependencies:  Stopgaps: 
Description (last modified by )
With 8.3.rc1:
sage: K.<a> = NumberField(x^6  x^5  5*x^4 + 4*x^3 + 6*x^2  3*x  1) sage: K.ideal(1,1)
takes a long time to return  why? Using %time it immediately shows 1ms for the second line but the prompt does not appear until *minutes* later. So it is the display of the ideal which is triggering something long. In a new session:
sage: K.<a> = NumberField(x^6  x^5  5*x^4 + 4*x^3 + 6*x^2  3*x  1) sage: %time I=K.ideal([1,1]) CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 1.08 ms sage: %time I CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 10 µs <long wait>
Change History (23)
comment:1 Changed 4 years ago by
 Description modified (diff)
 Summary changed from Problem creating a number field (fractional) ideal to Problem displaying a number field (fractional) ideal
comment:2 followups: ↓ 3 ↓ 4 Changed 4 years ago by
comment:3 in reply to: ↑ 2 Changed 4 years ago by
Replying to cremona:
but also it might be a good idea to include special case code for the unit ideal  this ideal has norm 1 which is trivial to compute so returning the string '(1)' could be done as a short cut.
That's such a special case, I'm not convinced that it's worth it.
comment:4 in reply to: ↑ 2 Changed 4 years ago by
Replying to cremona:
Since the field discriminant is less than
10^6
the string function calls gens_reduced, and that is taking the time.
Indeed. So I would say that this heuristic bound of the discriminant is not sufficient to predict that the class group is easy to compute.
comment:5 Changed 4 years ago by
I asked paridev.
comment:6 Changed 2 years ago by
From Karim Belabas's answer on paridev:
In any case, you should never compute a bnfinit when it's not absolutely necessary. [ I.e. you should do it on the fly when the extra structure is a prerequisite for a specific function call. ]
comment:7 Changed 2 years ago by
 Cc slelievre added
 Component changed from PLEASE CHANGE to number fields
 Milestone changed from sage8.4 to sage9.2
comment:8 Changed 2 years ago by
 Milestone changed from sage9.2 to sage9.3
comment:9 Changed 18 months ago by
There is something strange here. Nothing to do with the representation if ideals really. For this field, if you construct its pari_bnf, it takes ages to return even with no output:
sage: K.<a> = NumberField(x^6  x^5  5*x^4 + 4*x^3 + 6*x^2  3*x  1) sage: %time pK = K.pari_bnf(proof=False, units=False) CPU times: user 1min 11s, sys: 128 ms, total: 1min 11s Wall time: 1min 11s
but in a fresh Sage session, if I interrupt the second line immediately and then rerun it:
sage: K.<a> = NumberField(x^6  x^5  5*x^4 + 4*x^3 + 6*x^2  3*x  1) sage: %time pK = K.pari_bnf(proof=False, units=False) <interrupt after <1s> sage: %time pK = K.pari_bnf(proof=False, units=False) CPU times: user 36 ms, sys: 0 ns, total: 36 ms Wall time: 37.2 ms
Also, after this, displaying K.ideal(1,1) is instantaneous. So I think that there *is* a bug in here, though I cannot tell what is happening.
Simplifying further:
sage: y = polygen(QQ, 'y') sage: f = pari(y^6  y^5  5*y^4 + 4*y^3 + 6*y^2  3*y  1) sage: %time f.bnfinit() CPU times: user 1min 9s, sys: 144 ms, total: 1min 9s Wall time: 1min 9s
while again, interrupting immediately and reissuing the last line gives the output immediately.
Lastly,
sage: %gp > Switching to PARI/GP interpreter < pari: K = bnfinit(y^6  y^5  5*y^4 + 4*y^3 + 6*y^2  3*y  1); pari: ## *** last result computed in 24 ms.
comment:10 Changed 18 months ago by
What about 9.3.beta6? Sage 8.3.rc1 is not very relevant unless you precisely bisect where the problem is.
comment:11 Changed 18 months ago by
(implicit note: I can not reproduce on 9.3.beta6)
comment:12 Changed 18 months ago by
The original posting was for an old version, but everything I wrote in the last 24 hours has been for 9.2, running on ubuntu, built from source.
comment:13 Changed 18 months ago by
Ah, and when I try on 9.3.beta6 is is fine. That's good! I'll mark this as invalid / won'tfix as something has fixed it between 9.2 and now.
comment:14 Changed 18 months ago by
Maybe cypari2 upgrade #31029?
comment:15 Changed 18 months ago by
 Milestone changed from sage9.3 to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
comment:16 followup: ↓ 17 Changed 18 months ago by
Any way to add a doctest for this?
comment:17 in reply to: ↑ 16 Changed 18 months ago by
Replying to slelievre:
Any way to add a doctetcst for this?
Sure: the 2 lines of the original post should do.
comment:18 Changed 18 months ago by
 Status changed from needs_review to needs_work
comment:19 Changed 18 months ago by
 Branch set to u/cremona/25934
 Commit set to 1e45e421fe879eb9e306fde3745ef3cbc36bf43c
 Status changed from needs_work to needs_review
I added a doctest as suggested. No code changes.
New commits:
1e45e42  #25934: add doctest to show the problem has gone away

comment:20 Changed 18 months ago by
Review please? The patch just adds one tiny doctest.
comment:21 Changed 18 months ago by
 Keywords NumberField ideal added
 Milestone changed from sageduplicate/invalid/wontfix to sage9.3
comment:22 Changed 18 months ago by
 Reviewers set to Frédéric Chapoton, Samuel Lelièvre
 Status changed from needs_review to positive_review
comment:23 Changed 18 months ago by
 Branch changed from u/cremona/25934 to 1e45e421fe879eb9e306fde3745ef3cbc36bf43c
 Resolution set to fixed
 Status changed from positive_review to closed
Since the field discriminant is less than
10^6
the string function calls gens_reduced, and that is taking the time. Specifially the call to self_cache_bnfisprincipal() is. This suggests that something needs fixing; but also it might be a good idea to include special case code for the unit ideal  this ideal has norm 1 which is trivial to compute so returning the string '(1)' could be done as a short cut.