I see that the ticket http://trac.sagemath.org/sage_trac/ticket/4533
has been closed. Thank you for the effort, now divisors in SAGE is much faster!! However, the one that packed in SAGE 3.2 is still about 3 times slower than that in PARI. I wonder if all the improvements have been implemented in 3.2. or we need to wait for 3.2.1? PARI/GP (on a really old machine) for(i=1,1000, divisors(3293479734242732472)) time = 1,433 ms. SAGE (on the same machine) sage: %timeit divisors(3293479734242732472) 100 loops, best of 3: 4.93 ms per loop Thanks! On Nov 16, 12:26 am, Robert Bradshaw <[EMAIL PROTECTED]> wrote: > On Nov 15, 2008, at 11:57 PM, pong wrote: > > > I was a bit reluctant to post this question here since "support" > > shouldn't mean teaching me how to write programs. But Jason Grout > > suggested me to post it here anyway. > > Short snippets of code (like the one below) are very useful. It's > hard to give a good answer without something concrete to go on. I am > also curious what kind of input you're giving it. (Highly composite I > suppose?) > > > Here is a very short script that I want to maximize the speed > > > def lspec(n): > > return sorted([k if k^2 < 2*n else 2*n/k for k indivisors > > (odd_part(n))]) > > > At first, I think I can make it faster by avoiding computing k^2 in > > the for loop by replacing k^2 > 2*n by > > k > r where r = sqrt(RDF(2*n)) is computed once outside the for loop. > > However, it looks like comparing two entities of different types is > > veryslowin SAGE so I ended up with a slower script if a do that. > > Try setting r = (2*n).isqrt(), which is an integer. You can also > write 2*n//k which will do exact division (since you know the result > is an integer). After making these two changes it seems to run in > exactly the time it takes to computedivisors(odd_part(n)). The > divisorsfunction looks horribly inefficient, it's probably only ever > been used for small inputs. I've made a ticket > > http://trac.sagemath.org/sage_trac/ticket/4533 > > > Also I tried to replace k by 2*n/k only for those k indivisors > > (odd_part(n)) whose squares are > 2*n (instead of doing a list > > comprehension) but the resulting script is not any faster. > > > Thanks in advance > > > P.S. I implemented the algorithm using PARI/GP, the result is almost > > 200 times faster. > > That is quite the difference. Hopefully this gives us a good goal as > to how fast we can list thedivisorsof a number. > > - Robert --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
