Why sigma(n) seems not so performant for small n?

asked 2016-11-15 12:18:12 +0200

logomath gravatar image

updated 2016-11-15 13:10:17 +0200

When I try to timeit sigma(n):

sage: %timeit

sage: for n in xsrange(1,10000): c=sigma(n)

5 loops, best of 3: 181 ms per loop

but it seems much quicker when you directly sum the divisors

sage: %timeit

sage: def s(n): return sum(divisors(n))

sage: for n in xsrange(1,10000): c=s(n)

5 loops, best of 3: 44.8 ms per loop

The same with sigma(n,k). Why that happens (for relatively small n)?

edit retag flag offensive close merge delete

Comments

Finding divisors uses pari, and maybe pari has gotten faster recently, making your version faster. Or more specifically, maybe pari has gotten faster at listing divisors than at factoring -- sigma uses the factor function. That's just a guess, though.

John Palmieri gravatar imageJohn Palmieri ( 2016-11-15 20:04:23 +0200 )edit

By the way, as far as I can tell, the code for sigma was last changed in 2007 or so. So it may be time to revisit it.

John Palmieri gravatar imageJohn Palmieri ( 2016-11-15 21:13:16 +0200 )edit

Thank you for your hint

logomath gravatar imagelogomath ( 2016-11-17 18:45:04 +0200 )edit
add a comment