#4443: [with patch, needs review] Massive prime_range speedup, arith* files
cleanup
------------------------------+---------------------------------------------
Reporter: craigcitro | Owner: craigcitro
Type: defect | Status: new
Priority: major | Milestone: sage-3.2
Component: basic arithmetic | Keywords:
------------------------------+---------------------------------------------
This bundle does several things:
1. Massively speed up `prime_range`. Before:
{{{
sage: time ls = prime_range(10^8)
CPU times: user 143.74 s, sys: 1.51 s, total: 145.26 s
Wall time: 145.93 s
}}}
After:
{{{
sage: %time ls = prime_range(10^8)
CPU times: user 1.76 s, sys: 1.08 s, total: 2.84 s
Wall time: 2.87 s
}}}
This was first mentioned during the `3.1.3.alpha0` testing cycle.
2. Speed up `gcd` and `lcm`. These were rewritten to be much more robust
as part of #3118. However, these were accidentally made much slower. This
patch fixes that.
Before #3118:
{{{
sage: n = 928374923
sage: m = 892734
sage: %timeit gcd(n,m)
100000 loops, best of 3: 6.13 µs per loop
}}}
After #3118:
{{{
sage: n = 928374923
sage: m = 892734
sage: %timeit gcd(n,m)
10000 loops, best of 3: 25.7 µs per loop
}}}
With this patch:
{{{
sage: n = 928374923
sage: m = 892734
sage: %timeit gcd(n,m)
100000 loops, best of 3: 3.97 µs per loop
}}}
I also tested on lots of other kinds of input (lists of `Integer`s, list
of `int`s, list of `long`s, etc), and the code '''seems''' to be always at
least as fast as both before and after the patch at #3118. If there are
cases I've missed, please let me know!
3. Tidy up `sage/rings/arith.py`. This was mostly small cosmetic changes;
it would be a good project to go through this file, remove more cruft, and
move some functions to Cython. If someone wants to make a ticket and
assign it to me, I'll try to get to it at some point.
4. Clean up and reorganize all of the files with `arith` in their name.
In particular, I moved `sage/ext/arith.pyx` to
`sage/rings/fast_arith.pyx`, and removed all of the legacy `arith_c`,
`arith_gmp`, etc. Most of these were empty files that dated back to the
days when Pyrex wouldn't let us keep `.pyx` files in multiple directories.
There were also two files which seemed to be a Pyrex implementation of
polynomials mod n, I believe by Didier Deshommes. These aren't used
anywhere in Sage, and we have new code that does that (based on David
Harvey's `znpoly`), so I've removed them.
I have tested all of `sage/rings/`, but one should really do a `sage -br`
and a `sage -testall` before giving this bundle a positive review. I'll
try to do this soon, but I wanted to get the patch posted while I was at
it.
Since several files were added and removed from the mercurial archive, I'm
attaching a bundle instead of a patch. I'm adding John Cremona and Paul
Zimmerman to the `cc`, because they're most qualified to look at the
changes I made after #3118 and see if I accidentally un-did any of their
work on some corner cases.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4443>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
