#9451: [with patch, needs work] sieve of atkin
-----------------------------+----------------------------------------------
Reporter: rohana | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: number theory | Keywords: prime, sieve, range
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Description changed by rohana:
Old description:
> The goal of this ticket is to efficiently implement the sieve of atkin.
> This first version is a step in that direction.
>
> Paper on the sieve can be found at http://bit.ly/sieveatkin
>
> Due to the length of the implementation, I moved `prime_range` from
> `fast_arith` into a new module.
>
> The current implementation uses 64-bit ints and hits that barrier at
> input around `2**56`, so I've capped it at `2**52` (in the future I plan
> to remove this limitation).
>
> I've changed the default algorithm to atkins, since it is nearly as fast
> as the pari table, but doesn't use as much storage so it is more viable
> for large input.
>
> Docstrings are incomplete.
New description:
The goal of this ticket is to efficiently implement the sieve of atkin.
This first version is a step in that direction.
Paper on the sieve can be found at http://bit.ly/sieveatkin
The implementation is written to be run in parallel, however I am unaware
of any good method of making it parallel within cython (it would be nice
to get openmp in there sometime).
Due to the length of the implementation, I moved `prime_range` from
`fast_arith` into a new module.
The current implementation uses 64-bit ints and hits that barrier at input
around `2**56`, so I've capped it at `2**52` (in the future I plan to
remove this limitation).
I've changed the default algorithm to atkins, since it is nearly as fast
as the pari table, but doesn't use as much storage so it is more viable
for large input.
Docstrings are incomplete.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9451#comment:1>
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.
