Inspired by the ask.sagemath question
https://ask.sagemath.org/question/35587/why-sigman-seems-not-so-performant-for-small-n/,
I started looking at timings for the sigma function (sigma(n) = sum of the
divisors of n, sigma(n, k) = sum of the kth powers of the divisors of n).
On my computer, a naive implementation of sigma is faster than what we have
in Sage for small values of n. When n is between 10^13 and 10^14, Sage's
implementation of sigma speeds up: it is much faster to compute
sigma(10**14) than sigma(10**13):
$ sage -c "timeit('L = [sigma(n) for n in range(10**13, 10**13 + 5)]',
number=1, repeat=1)"
1 loops, best of 1: 2.4 ms per loop
$ sage -c "timeit('L = [sigma(n) for n in range(10**14, 10**14 + 5)]',
number=1, repeat=1)"
1 loops, best of 1: 607 µs per loop
(I used "sage -c ..." and timeit with a single loop in case results were
being cached.)
Any ideas why? Can we speed it up for smaller values?
Also, should we switch to a naive implementation of sigma: essentially just
return sum(divisors(n))? I think the main difference between the current
version and the naive one is that the current version uses "factor(n)"
instead of "divisors(n)", and I think both of those functors just call
Pari. Has Pari's implementation of "divisors" improved lately, especially
as compared to "factor"? (By "lately" I may mean since 2007, which may have
been when sigma was last changed.)
--
John
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
