I guess that it would be much better to also propose access to
1) the flint function
void fmpz_divisor_sigma ( fmpz_t res , const fmpz_t n , ulong k )
2) the pari function sigma
For example, pari timing is competitive in this range
$ sage -c "timeit('L = [sigma(n) for n in range(10**13, 10**13 + 5)]',
number=1, repeat=1)"
1 loops, best of 1: 3.47 ms per loop
$ sage -c "timeit('L = [pari(n).sigma() for n in range(10**13, 10**13
+ 5)]', number=1, repeat=1)"
1 loops, best of 1: 688 µs per loop
Vincent
On 15 November 2016 at 21:01, William Stein <[email protected]> wrote:
> On Tue, Nov 15, 2016 at 11:47 AM, John H Palmieri
> <[email protected]> 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 [email protected].
>> To post to this group, send email to [email protected].
>> 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 [email protected].
> To post to this group, send email to [email protected].
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
