Opened 12 years ago
Closed 11 years ago
#5136 closed defect (duplicate)
[fixed by #5842] constructing the ring of integers of a relative number field is SLOW
Reported by: | AlexGhitza | Owned by: | davidloeffler |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | number fields | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
David Loeffler reported this on sage-devel:
sage: K.<a> = QuadraticField(-23) sage: L.<b> = K.extension(x^3 - x - 1) sage: OL = L.ring_of_integers() # infinite loop?
Note also that CTRL-C seems to have no effect. I see the same problem on my 32-bit Archlinux machine.
Change History (9)
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
- Priority changed from blocker to major
- Summary changed from sage-3.3.alpha3 gets stuck computing the ring of integers of a relative number field to constructing the ring of integers of a relative number field is SLOW
It is, in fact, not an infinite loop. It's just really, really slow. It also seems to pre-date 3.3.alpha3:
---------------------------------------------------------------------- | Sage Version 3.2.3, Release Date: 2009-01-05 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- sage: K.<a> = QuadraticField(-23) sage: L.<b> = K.extension(x^3 - x - 1) sage: time OL = L.ring_of_integers() CPU times: user 263.94 s, sys: 12.98 s, total: 276.92 s Wall time: 280.13 s
comment:3 Changed 12 years ago by
I do not think this is a problem with the relative number field patch; it was an existing problem. I have code that I can submit if you want to compute the relative ring of integers; it uses pari's rnfbasis.
This issue has to with the fact that L.ring_of_integers().base_ring()
is ZZ and not K.ring_of_integers()
. There's already a ticket for that.
comment:4 follow-up: ↓ 6 Changed 12 years ago by
This works for me now (in sage 4.0.2):
---------------------------------------------------------------------- | Sage Version 4.0.2, Release Date: 2009-06-18 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- Loading Sage library. Current Mercurial branch is: unitary sage: K.<a> = QuadraticField(-23) sage: L.<b> = K.extension(x^3 - x - 1) sage: time OL = L.ring_of_integers() CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s Wall time: 0.02 s
I don't know what's changed -- presumably this is something to do with Francis Clarke's campaign to fix all the relative number field bugs over the last couple of months -- but presumably we can close this ticket now?
comment:5 Changed 12 years ago by
- Component changed from number theory to number fields
- Owner changed from was to davidloeffler
comment:6 in reply to: ↑ 4 Changed 12 years ago by
Replying to davidloeffler:
This works for me now (in sage 4.0.2): ... I don't know what's changed -- presumably this is something to do with Francis Clarke's campaign to fix all the relative number field bugs over the last couple of months -- but presumably we can close this ticket now?
Yes, this issue had already been raised in #4738, and I commented there that "The problem of the slowness of computing relative maximal orders is solved by the patch in #5842. A doctest is included at line 532 of the patched number_field_rel.py
" (It's become line 570 by 4.1)
What changed was a rewrite of maximal_order
for relative number fields. The previous version was repetitive and grossly wasteful of memory.
comment:7 Changed 11 years ago by
- Report Upstream set to N/A
- Status changed from new to needs_review
- Summary changed from constructing the ring of integers of a relative number field is SLOW to [fixed by #5842] constructing the ring of integers of a relative number field is SLOW
We should close this ticket -- two people agree that it's fixed and there are doctests to prove it.
comment:8 Changed 11 years ago by
- Status changed from needs_review to positive_review
I'm setting this to "positive review" so the release manager can close it when convenient.
comment:9 Changed 11 years ago by
- Milestone changed from sage-4.5.2 to sage-duplicate/invalid/wontfix
- Resolution set to duplicate
- Status changed from positive_review to closed
I'm closing this ticket as a "duplicate."
Actually, CTRL-C does eventually stop this, with the following result: