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 -~----------~----~----~----~------~----~------~--~---
