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: | sage-9.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 follow-ups: ↓ 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 pari-dev.
comment:6 Changed 2 years ago by
From Karim Belabas's answer on pari-dev:
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 sage-8.4 to sage-9.2
comment:8 Changed 2 years ago by
- Milestone changed from sage-9.2 to sage-9.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't-fix 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 sage-9.3 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
comment:16 follow-up: ↓ 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 sage-duplicate/invalid/wontfix to sage-9.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.