#6766: [with patch, positive review] faster powers of factorizations
-------------------------+--------------------------------------------------
Reporter: fwclarke | Owner: tbd
Type: enhancement | Status: new
Priority: minor | Milestone: sage-4.1.2
Component: algebra | Keywords:
Reviewer: | Author: Francis Clarke
Merged: |
-------------------------+--------------------------------------------------
Comment(by 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
}}}
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6766#comment:5>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
