Opened 13 years ago
Closed 13 years ago
#6766 closed enhancement (fixed)
[with patch, positive review] faster powers of factorizations
Reported by: | fwclarke | Owned by: | tbd |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.1.2 |
Component: | algebra | Keywords: | |
Cc: | cremona | Merged in: | Sage 4.1.2.alpha0 |
Authors: | Francis Clarke | Reviewers: | John Cremona |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The patch provides a much faster method for computing powers of commutative factorizations. This implements a suggestion made by John Cremona in #5188. The speed-up is most marked for factorizations of ideals in number fields. Before:
sage: f = NumberField(x^2 + 23, 'a').factor(47) sage: timeit('f^10') 5 loops, best of 3: 134 ms per loop
After:
sage: f = NumberField(x^2 + 23, 'a').factor(47) sage: timeit('f^10') 625 loops, best of 3: 571 µs per loop
In addition, five redundant lines have been removed from the __init__
function of the Factorization
class.
Attachments (1)
Change History (8)
Changed 13 years ago by
comment:1 Changed 13 years ago by
- Summary changed from faster powers of factorizations to [with patch, needs review] faster powers of factorizations
comment:2 Changed 13 years ago by
- Summary changed from [with patch, needs review] faster powers of factorizations to [with patch, positive review] faster powers of factorizations
This looks good to me; it applies fine to 4.1.1. I only tested the file which was changed.
comment:3 follow-up: ↓ 4 Changed 13 years ago by
It would be nice if there are more code to illustrate timings before and after applying the patch. As I see it, the patch claims to optimize an operation and Francis has provided one example. Is it possible to provide some more examples of before and after timing statistics? Such examples goes very well with release tours, in which features are being showcased.
comment:4 in reply to: ↑ 3 Changed 13 years ago by
Replying to mvngu:
It would be nice if there are more code to illustrate timings before and after applying the patch. As I see it, the patch claims to optimize an operation and Francis has provided one example. Is it possible to provide some more examples of before and after timing statistics? Such examples goes very well with release tours, in which features are being showcased.
I'm not sure this is really worth it in this case. Before a stupid method was used (by default) while now a sensible one is. But on the other hand there are not that many situations where one needs to raise a factoization to a power anyway, so I would not want to make a big issue of this in release notes! [This is not to diminish the credit to Francis for bothering to do the job, of course!]
comment:5 follow-up: ↓ 6 Changed 13 years ago by
I agree with John's comments, but for the record: before (4.1.1)
sage: f = factor(120) sage: for i in range(10): timeit('f^(2^%s)' % i) ....: 625 loops, best of 3: 80.1 µs per loop 625 loops, best of 3: 538 µs per loop 625 loops, best of 3: 1.03 ms per loop 125 loops, best of 3: 1.5 ms per loop 125 loops, best of 3: 1.93 ms per loop 125 loops, best of 3: 2.39 ms per loop 125 loops, best of 3: 2.81 ms per loop 125 loops, best of 3: 3.23 ms per loop 125 loops, best of 3: 3.7 ms per loop 125 loops, best of 3: 4.12 ms per loop
and after (4.1.1 + patch)
sage: f = factor(120) sage: for i in range(10): timeit('f^(2^%s)' % i) ....: 625 loops, best of 3: 4.49 µs per loop 625 loops, best of 3: 95.1 µs per loop 625 loops, best of 3: 95 µs per loop 625 loops, best of 3: 95 µs per loop 625 loops, best of 3: 95.1 µs per loop 625 loops, best of 3: 95 µs per loop 625 loops, best of 3: 95.2 µs per loop 625 loops, best of 3: 95.2 µs per loop 625 loops, best of 3: 95.3 µs per loop 625 loops, best of 3: 95.3 µs per loop
It might be possible to make this faster still. But as John points out, it's a fairly obscure function. I only wrote the patch because I found in the course of doing some calculations that the existing code can't cope at all with factorizations of ideals in moderately sized number fields; what takes all the time is the completely unnecessary check for idempotence in the generic power code.
comment:6 in reply to: ↑ 5 Changed 13 years ago by
Replying to fwclarke:
I agree with John's comments, but for the record: before (4.1.1)
sage: f = factor(120) sage: for i in range(10): timeit('f^(2^%s)' % i) ....: 625 loops, best of 3: 80.1 µs per loop 625 loops, best of 3: 538 µs per loop 625 loops, best of 3: 1.03 ms per loop 125 loops, best of 3: 1.5 ms per loop 125 loops, best of 3: 1.93 ms per loop 125 loops, best of 3: 2.39 ms per loop 125 loops, best of 3: 2.81 ms per loop 125 loops, best of 3: 3.23 ms per loop 125 loops, best of 3: 3.7 ms per loop 125 loops, best of 3: 4.12 ms per loop
and after (4.1.1 + patch)
sage: f = factor(120) sage: for i in range(10): timeit('f^(2^%s)' % i) ....: 625 loops, best of 3: 4.49 µs per loop 625 loops, best of 3: 95.1 µs per loop 625 loops, best of 3: 95 µs per loop 625 loops, best of 3: 95 µs per loop 625 loops, best of 3: 95.1 µs per loop 625 loops, best of 3: 95 µs per loop 625 loops, best of 3: 95.2 µs per loop 625 loops, best of 3: 95.2 µs per loop 625 loops, best of 3: 95.3 µs per loop 625 loops, best of 3: 95.3 µs per loop
These are what I was looking for. Thank you for providing more examples. And my apologies since my above request was ambiguous.
comment:7 Changed 13 years ago by
- Merged in set to Sage 4.1.2.alpha0
- Resolution set to fixed
- Reviewers set to John Cremona
- Status changed from new to closed
Hi Francis. After uploading a patch for a ticket, you should change the subject to "[with patch, needs review]". That way, the ticket can be picked up by the relevant trac report as needing review.