On Tue, Nov 15, 2016 at 11:47 AM, John H Palmieri <jhpalmier...@gmail.com> wrote: > 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?
Idea -- try proof.all(False) That may be relevant to whether factoring is also proving correctness or not. -- William > > 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. -- William (http://wstein.org) -- 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.
