#8309: speedup prime range
-----------------------------+----------------------------------------------
Reporter: robertwb | Owner: was
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.3.4
Component: number theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by robertwb):
* status: needs_info => needs_review
Comment:
BEFORE
{{{
sage: timeit("prime_range(10)", number=10000)
10000 loops, best of 3: 57.8 µs per loop
sage: timeit("prime_range(100)", number=10000)
10000 loops, best of 3: 61.2 µs per loop
sage: timeit("prime_range(1000)", number=10000)
10000 loops, best of 3: 102 µs per loop
sage: timeit("prime_range(1000,2000)", number=10000)
10000 loops, best of 3: 123 µs per loop
sage: timeit("prime_range(1e6)")
5 loops, best of 3: 36.9 ms per loop
sage: timeit("prime_range(2e6)")
5 loops, best of 3: 69.7 ms per loop
sage: timeit("prime_range(2e6)")
5 loops, best of 3: 69.7 ms per loop
sage: timeit("prime_range(1e6,2e6)")
5 loops, best of 3: 40.6 ms per loop
sage: timeit("prime_range(1e6,1e6+100)")
25 loops, best of 3: 8.21 ms per loop
}}}
AFTER
{{{
sage: timeit("prime_range(10)", number=10000)
10000 loops, best of 3: 969 ns per loop
sage: timeit("prime_range(100)", number=10000)
10000 loops, best of 3: 3.24 µs per loop
sage: timeit("prime_range(1000)", number=10000)
10000 loops, best of 3: 30.3 µs per loop
sage: timeit("prime_range(1000,2000)", number=10000)
10000 loops, best of 3: 22.2 µs per loop
sage: timeit("prime_range(1e6)")
25 loops, best of 3: 28.5 ms per loop
sage: timeit("prime_range(2e6)")
5 loops, best of 3: 53.8 ms per loop
sage: timeit("prime_range(2e6)")
5 loops, best of 3: 55 ms per loop
sage: timeit("prime_range(1e6,2e6)")
25 loops, best of 3: 25.6 ms per loop
sage: timeit("prime_range(1e6,1e6+100)")
625 loops, best of 3: 259 µs per loop
}}}
AFTER INTS
{{{
sage: timeit("prime_range(10, py_ints=True)", number=10000)
10000 loops, best of 3: 1.27 µs per loop
sage: timeit("prime_range(100, py_ints=True)", number=10000)
10000 loops, best of 3: 3.11 µs per loop
sage: timeit("prime_range(1000, py_ints=True)", number=10000)
10000 loops, best of 3: 11.5 µs per loop
sage: timeit("prime_range(1000, 2000, py_ints=True)", number=10000)
10000 loops, best of 3: 11.7 µs per loop
sage: timeit("prime_range(1e6, py_ints=True)")
125 loops, best of 3: 4.1 ms per loop
sage: timeit("prime_range(2e6, py_ints=True)")
125 loops, best of 3: 7.9 ms per loop
sage: timeit("prime_range(2e6, py_ints=True)")
125 loops, best of 3: 7.83 ms per loop
sage: timeit("prime_range(1e6,2e6, py_ints=True)")
125 loops, best of 3: 3.88 ms per loop
sage: timeit("prime_range(1e6,1e6+100, py_ints=True)")
625 loops, best of 3: 260 µs per loop
}}}
I also cleaned up the patch a bit (e.g. using pari.init_primes rather than
resetting diffptr manually).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8309#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
