[sage-support] Re: need helps in optimizing speed
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 -~--~~~~--~~--~--~---
[sage-support] Re: need helps in optimizing speed
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 -~--~~~~--~~--~--~---
[sage-support] Re: need helps in optimizing speed
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 -~--~~~~--~~--~--~---
[sage-support] Re: need helps in optimizing speed
On Nov 15, 2008, at 23:57 , 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. It seems reasonable to post this here, since it involves performance, which can be tricky in a complicated system like Sage. I don't think this qualifies as teaching you to program :-} 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 in divisors (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 very slow in SAGE so I ended up with a slower script if a do that. I assume you mean instead of (or vice versa in your script). Try using isqrt() to compute the integer part of the square root. It speeds up the loop, but only slightly: sage: timeit( lspec(2799734567890)) 625 loops, best of 3: 1.24 ms per loop sage: timeit( sspec(2799734567890)) 625 loops, best of 3: 1.13 ms per loop (This is on a 3GHz Dual Quad Xeon, so YMMV). sspec() is the version with the square root computed outside the loop. HTH Justin -- Justin C. Walker, Curmudgeon-At-Large Institute for the Enhancement of the Director's Income Experience is what you get when you don't get what you want. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[sage-support] Re: need helps in optimizing speed
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 in divisors (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 very slow in 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 compute divisors(odd_part(n)). The divisors function 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 in divisors (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 the divisors of 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 -~--~~~~--~~--~--~---
