Oh really. Now I realized why I had in my mind that SAGE was much slower---the test what based on a more complicated function instead of just divisors.
Looking forward to SAGE 3.2.1 then. On Nov 24, 11:05 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > 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 Washingtonhttp://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 -~----------~----~----~----~------~----~------~--~---
