#11475: improve prime_pi (speedup + small fixes)
-----------------------------+----------------------------------------------
Reporter: rohana | Owner: was
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.7.1
Component: number theory | Keywords: primes, prime counting, prime_pi
Work_issues: | Upstream: N/A
Reviewer: | Author: R. Andrew Ohana
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by leif):
* status: needs_review => needs_work
Comment:
Ok, here are my first 32-bit tests (with patch v5):
{{{
sage -t "devel/sage-11475v5/sage/functions/prime_pi.pyx"
**********************************************************************
File "/home/leif/Sage/sage-4.7/devel/sage-
11475v5/sage/functions/prime_pi.pyx", line 126:
sage: prime_pi(10**10)
Expected:
455052511
Got:
498132213
**********************************************************************
1 items had failures:
1 of 14 in __main__.example_1
***Test Failed*** 1 failures.
For whitespace errors, see the file
/home/leif/.sage//tmp/.doctest_prime_pi.py
[6.1 s]
----------------------------------------------------------------------
The following tests failed:
sage -t "devel/sage-11475v5/sage/functions/prime_pi.pyx"
Total time for all tests: 6.1 seconds
real 0m6.293s
user 0m5.328s
sys 0m0.760s
}}}
With long tests included, some unhandled overflows occur:
{{{
sage -t -long "devel/sage-11475v5/sage/functions/prime_pi.pyx"
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
Exception OverflowError: 'long int too large to convert to int' in
'sage.functions.prime_pi.PrimePi.__sieve' ignored
**********************************************************************
File "/home/leif/Sage/sage-4.7/devel/sage-
11475v5/sage/functions/prime_pi.pyx", line 126:
sage: prime_pi(10**10)
Expected:
455052511
Got:
498132213
**********************************************************************
File "/home/leif/Sage/sage-4.7/devel/sage-
11475v5/sage/functions/prime_pi.pyx", line 231:
sage: for n in (42,41..32): prime_pi(2**n) # long time (21s on
mod.math, 2011)
Expected:
156661034233
80316571436
41203088796
21151907950
10866266172
5586502348
2874398515
1480206279
762939111
393615806
203280221
Got:
2072485352
555689055
4249350341
1916569322
829105263
2484680881
3345496393
1649125207
813719441
403824770
203621732
**********************************************************************
2 items had failures:
1 of 14 in __main__.example_1
1 of 14 in __main__.example_4
***Test Failed*** 2 failures.
For whitespace errors, see the file
/home/leif/.sage//tmp/.doctest_prime_pi.py
[52.1 s]
----------------------------------------------------------------------
The following tests failed:
sage -t -long "devel/sage-11475v5/sage/functions/prime_pi.pyx"
Total time for all tests: 52.2 seconds
real 0m52.318s
user 0m49.923s
sys 0m0.956s
}}}
This is on Ubuntu 7.10 :) (P4 Northwood, gcc 4.2.1) with Sage 4.7.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11475#comment:26>
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.
