#8309: speedup prime range
-------------------------------+--------------------------------------------
Reporter: robertwb | Owner: was
Type: defect | Status: positive_review
Priority: major | Milestone: sage-4.3.4
Component: number theory | Keywords:
Author: Robert Bradshaw | Upstream: N/A
Reviewer: Paul Zimmermann | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_review => positive_review
* reviewer: => Paul Zimmermann
* author: => Robert Bradshaw
Comment:
Robert, I got one doctest failure in `graphs/generic_graph.py`. However
after cloning again 4.3.3, and testing again with your patch, it worked.
Thus it might be to an interference with the other patches I've tried.
On my side (Core 2 Duo) I get:
{{{
BEFORE:
----------------------------------------------------------------------
| Sage Version 4.3.3, Release Date: 2010-02-21 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: timeit("prime_range(10)", number=10000)
10000 loops, best of 3: 26.5 µs per loop
sage: timeit("prime_range(100)", number=10000)
10000 loops, best of 3: 31 µs per loop
sage: timeit("prime_range(1000)", number=10000)
10000 loops, best of 3: 65 µs per loop
sage: timeit("prime_range(1000,2000)", number=10000)
10000 loops, best of 3: 81.1 µs per loop
sage: timeit("prime_range(1e6)")
25 loops, best of 3: 24.9 ms per loop
sage: timeit("prime_range(2e6)")
5 loops, best of 3: 45.9 ms per loop
sage: timeit("prime_range(2e6)")
5 loops, best of 3: 45.8 ms per loop
sage: timeit("prime_range(1e6,2e6)")
25 loops, best of 3: 28.3 ms per loop
sage: timeit("prime_range(1e6,1e6+100)")
125 loops, best of 3: 5.47 ms per loop
AFTER:
Loading Sage library. Current Mercurial branch is: 8309
sage: timeit("prime_range(10)", number=10000)
10000 loops, best of 3: 649 ns per loop
sage: timeit("prime_range(100)", number=10000)
10000 loops, best of 3: 1.79 µs per loop
sage: timeit("prime_range(1000)", number=10000)
10000 loops, best of 3: 14.6 µs per loop
sage: timeit("prime_range(1000,2000)", number=10000)
10000 loops, best of 3: 10.8 µs per loop
sage: timeit("prime_range(1e6)")
25 loops, best of 3: 14.6 ms per loop
sage: timeit("prime_range(2e6)")
25 loops, best of 3: 30.2 ms per loop
sage: timeit("prime_range(2e6)")
25 loops, best of 3: 30.4 ms per loop
sage: timeit("prime_range(1e6,2e6)")
25 loops, best of 3: 12.7 ms per loop
sage: timeit("prime_range(1e6,1e6+100)")
625 loops, best of 3: 148 µs per loop
AFTER INTS:
sage: sage: timeit("prime_range(10, py_ints=True)", number=10000)
10000 loops, best of 3: 852 ns per loop
sage: sage: timeit("prime_range(100, py_ints=True)", number=10000)
10000 loops, best of 3: 1.73 µs per loop
sage: sage: timeit("prime_range(1000, py_ints=True)", number=10000)
10000 loops, best of 3: 6.95 µs per loop
sage: sage: timeit("prime_range(1000, 2000, py_ints=True)", number=10000)
10000 loops, best of 3: 6.44 µs per loop
sage: sage: timeit("prime_range(1e6, py_ints=True)")
125 loops, best of 3: 2.79 ms per loop
sage: sage: timeit("prime_range(2e6, py_ints=True)")
125 loops, best of 3: 7.15 ms per loop
sage: sage: timeit("prime_range(2e6, py_ints=True)")
125 loops, best of 3: 7.16 ms per loop
sage: sage: timeit("prime_range(1e6,2e6, py_ints=True)")
125 loops, best of 3: 2.34 ms per loop
sage: sage: timeit("prime_range(1e6,1e6+100, py_ints=True)")
625 loops, best of 3: 149 µs per loop
}}}
Given that py_ints is faster for ranges larger than 100, I wonder why you
didn't make it the default. Anyway a positive review. Great work!
Paul
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8309#comment:4>
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.
