On Mon, Nov 24, 2008 at 10:43 PM, pong <[EMAIL PROTECTED]> wrote: > > 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 >
Quick remarks -- In pari, the runtime here is dominated by the call to factor. E.g., in pari you'll get the same time if you replace divisors by factor. Second: #4533 is *not* merged into sage-3.2. It's only going to appear in 3.2.1 -- that's why Michael wrote "Merged the edited patch in Sage 3.2.1.alpha0" at the bottom of the ticket. I think 3.2 just has the old code. In 3.2.1 pari is about 0.61s for me on that benchmark and sage is about 0.90s (for 1000 iterations). I think the actual divisor enumeration code is faster in Sage, but there is overhead doing the factorization, which is the reason Sage is a tiny bit slower. William > 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 > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
