Opened 9 years ago
Closed 22 months ago
#10184 closed enhancement (fixed)
class group iterator is too slow
Reported by: | thome | Owned by: | davidloeffler |
---|---|---|---|
Priority: | minor | Milestone: | sage-8.1 |
Component: | number fields | Keywords: | sd51 |
Cc: | Merged in: | ||
Authors: | Emmanuel Thome | Reviewers: | Shahed Sharif, Travis Scrimshaw, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | 9fe600e (Commits) | Commit: | 9fe600ed3691d52d3e3f981e09283e1bf863ead7 |
Dependencies: | Stopgaps: |
Description (last modified by )
the class group iterator takes evey element in turn, and computes the product of the g^i
's. Sure powers are computed by repeated squaring, but for iterators this is suboptimal.
On my laptop, from this situation...
sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321) sage: OK=K.maximal_order() sage: G=K.class_group() sage: time _=G.list() CPU times: user 2.48 s, sys: 0.05 s, total: 2.53 s Wall time: 2.53 s
the attached patch improves to...
sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321) sage: OK=K.maximal_order() sage: G=K.class_group() sage: time _=G.list() CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s Wall time: 0.44 s
which is a tad better.
doctest included (actually the previous doctest wasn't doing much, this one is slightly more thorough).
Note: while the code would work for any abelian group, I believe it makes sense only when the group operation is sufficiently non-trivial.
Attachments (3)
Change History (23)
Changed 9 years ago by
comment:1 follow-up: ↓ 2 Changed 7 years ago by
comment:2 in reply to: ↑ 1 Changed 7 years ago by
Hi David,
Replying to roed:
Is this waiting on something, or does it just need review?
I think it just hasn't been reviewed by anyone.
Cheers,
E.
comment:3 Changed 7 years ago by
- Status changed from new to needs_review
I'll mark it as needs review then. I don't have time to review it at the moment, though I may be able to eventually.
comment:4 Changed 7 years ago by
- Status changed from needs_review to needs_work
There are some formatting problems. The "sage:" indentation should be left as it was:
TESTS:: sage: ...
And you really should put a blank line between 2 functions, lines 213--214.
Also: please put your real name in the Author field on the ticket.
comment:5 Changed 6 years ago by
- Description modified (diff)
Changed 6 years ago by
comment:6 Changed 6 years ago by
- Keywords sd51 added
- Milestone set to sage-5.12
- Reviewers set to Shahed Sharif
Rebased to 5.11b3. This included adjusting line numbers. Also, last example had to be changed---the order of the class group elements is different.
Lastly, the new iterator __iter_inner__
needs a documentation string and a doc test
comment:7 Changed 6 years ago by
Shahed: I am puzzled by the constructs such as
[l for l in reflist[k]]
in the doctests in your patch. This is completely equivalent to reflist[k]
. Why the list comprehension?
comment:8 follow-up: ↓ 9 Changed 6 years ago by
Hi David,
This is unchanged from Emmanuel's patch, but I can simplify it in a new version. Also, it has been brought to my attention (by you and J. Cremona) that Pari produces the generators for the class group in a different order depending on the implementation. The given doctests were tested on my 32-bit system running sage 5.11b3; someone (probably me given time) will need to test this on a 64-bit system and put in the relevant doc test.
Shahed
comment:9 in reply to: ↑ 8 Changed 6 years ago by
Replying to ssharif:
This is unchanged from Emmanuel's patch, but I can simplify it in a new version. Also, it has been brought to my attention (by you and J. Cremona) that Pari produces the generators for the class group in a different order depending on the implementation. The given doctests were tested on my 32-bit system running sage 5.11b3; someone (probably me given time) will need to test this on a 64-bit system and put in the relevant doc test.
Is it only the order that is different between 32- and 64-bit? In other words, if the output of the function is sorted, would 32- and 64-bit machines produce the same list of generators?
Changed 6 years ago by
comment:10 Changed 6 years ago by
Hi.
Thanks for your feedback. I just posted another version of the patch which fixes indentation, and adds documentation and doctests to _iter_inner_.
Looking back at this, and considering your warning on the generators returned by pari, I think that the doctest for the iterator is probably too fragile. What do you think ?
E.
comment:11 Changed 6 years ago by
Alex and Emmanuel:
Yes, the order is exactly the problem---the output of G.list() is permuted between the 2 cases. Also (though I haven't tested this on 64-bit), I believe the representative ideal in each class is also different; but this should not pose a problem, since G(I) for example returns the class of I. I tried using set() to fix the issue, but that didn't work; not sure why.
comment:12 Changed 5 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:13 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:14 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:15 Changed 2 years ago by
- Branch set to public/10184
- Commit set to 568cc957900189761105c28e702f65d16fb805b0
- Status changed from needs_work to needs_review
comment:16 Changed 2 years ago by
- Milestone changed from sage-6.4 to sage-8.1
comment:17 Changed 2 years ago by
- Commit changed from 568cc957900189761105c28e702f65d16fb805b0 to 9fe600ed3691d52d3e3f981e09283e1bf863ead7
comment:18 Changed 2 years ago by
- Reviewers changed from Shahed Sharif to Shahed Sharif, Travis Scrimshaw
I made some small additional changes for speed and safety (in case inplace multiplication actually becomes inplace, really this does what the previous code was doing). This is really the same algorithm but using less multiplication. So if my changes look good, then positive review.
comment:19 Changed 23 months ago by
- Reviewers changed from Shahed Sharif, Travis Scrimshaw to Shahed Sharif, Travis Scrimshaw, Frédéric Chapoton
- Status changed from needs_review to positive_review
Looks good to me. Let it be.
comment:20 Changed 22 months ago by
- Branch changed from public/10184 to 9fe600ed3691d52d3e3f981e09283e1bf863ead7
- Resolution set to fixed
- Status changed from positive_review to closed
Is this waiting on something, or does it just need review?