#4533: [with patch; needs work] divisors function slow for integers
----------------------+-----------------------------------------------------
Reporter: robertwb | Owner: tbd
Type: defect | Status: new
Priority: major | Milestone: sage-3.2.1
Component: algebra | Resolution:
Keywords: |
----------------------+-----------------------------------------------------
Changes (by was):
* summary: [with patch; needs review] divisors function slow for
integers => [with patch; needs work] divisors
function slow for integers
Comment:
1. The new code isn't much faster, but it is certainly better. Here are
some before and after speed comparisons (core2 2.6Ghz 32-bit osx)
Before:
{{{
sage: n = odd_part(factorial(31))
sage: time _ = divisors(n)
CPU times: user 1.66 s, sys: 0.03 s, total: 1.70 s
Wall time: 1.73 s
sage: n = 928304029834092384082304982093480293849028349823948
sage: time _ = divisors(n)
CPU times: user 0.30 s, sys: 0.06 s, total: 0.35 s
Wall time: 0.46 s
sage: n = 9283040298340
sage: timeit('divisors(n)')
125 loops, best of 3: 1.75 ms per loop
}}}
After:
{{{
sage: n = odd_part(factorial(31))
sage: time _ = divisors(n)
CPU times: user 0.90 s, sys: 0.06 s, total: 0.96 s
Wall time: 0.98 s
sage: time a = gp(n).divisors()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.21 s
sage: n = 928304029834092384082304982093480293849028349823948
sage: time _ = divisors(n)
CPU times: user 0.31 s, sys: 0.06 s, total: 0.37 s
Wall time: 0.40 s
sage: n = 9283040298340
sage: timeit('divisors(n)')
625 loops, best of 3: 341 µs per loop
}}}
2. It no longer works on int's, which is a serious problem (this used to
work fine):
{{{
sage: divisors(int(5))
Traceback (most recent call last):
...
AttributeError: 'int' object has no attribute 'parent'
}}}
There should be a doctest about that.
For a positive review fix the code to work on int/long as input, and add a
doctest about that. Regarding speeding it up to be on par with pari,
that should be another ticket that *must* be opened before closing this
one. Ideas regarding speed:
* you can easily precompute the length of the output list as
{{{
prod(e+1 for _,e in f)
}}}
* If the input is an int < long long (or long), could do all arithmetic
with
machine says data types, since you know a priori the biggest number that
will appear. This should be special cased.
* Interestingly, I changed two lines of the function so it uses Python
int's instead of Sage MPFR ints everywhere and the function speeds up
dramatically so it is almost as fast as pari:
{{{
one = int(1)
all = [one]
for p, e in f:
p = int(p)
...
sage: time d = divisors(n)
CPU times: user 0.23 s, sys: 0.02 s, total: 0.24 s
Wall time: 0.25 s
sage: time w = [ZZ(a) for a in d]
CPU times: user 0.24 s, sys: 0.01 s, total: 0.25 s
Wall time: 0.26 s
sage: time w = gp(n).divisors()
CPU times: user 0.00 s, sys: 0.01 s, total: 0.01 s
Wall time: 0.18 s
}}}
Interestingly, as you can see above, doing everything with python ints,
then converting all the python ints back to sage ints, results in
something that is *twice* as fast as your code on the same input.
3. Other remarks:
* pari(n).divisors() gives an AttributeError, so I guess we never wrapped
that.
* Why is odd_part(factorial(31)) a RATIONAL? This seems really weird.
{{{
sage: n = odd_part(factorial(31))
sage: type(n)
<type 'sage.rings.rational.Rational'>
sage: type(factorial(31))
<type 'sage.rings.integer.Integer'>
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4533#comment:6>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
