Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

Prime generation using a sieve. Currently, an enhanced sieve of Eratosthenes is used, switching to an Atkin sieve is planned (if I get around to implementing it and it's not slower).

The sieve used is segmented, with a chunk size chosen to give good (enough)
cache locality while still getting something substantial done per chunk.
However, that means we must store data for primes up to the square root of
where sieving is done, thus sieving primes up to `n`

requires

space.*O*(sqrt n/log n)

- primes :: [Integer]
- sieveFrom :: Integer -> [Integer]
- data PrimeSieve
- primeSieve :: Integer -> PrimeSieve
- psieveList :: [PrimeSieve]
- psieveFrom :: Integer -> [PrimeSieve]
- primeList :: PrimeSieve -> [Integer]

# Limitations

There are three factors limiting the range of these sieves.

- Memory
- Overflow
- The internal representation of the state

An Eratosthenes type sieve needs to store the primes up to the square root of
the currently sieved region, thus requires

space.We store *O*(sqrt n/log n)`16`

bytes
of information per prime, thus a Gigabyte of memory takes you to about `1.6*10^18`

.
The `log`

doesn't change much in that range, so as a first approximation, doubling
the storage increases the sieve range by a factor of four.

On a 64-bit system, this is (currently) the only limitation to be concerned with, but
with more than four Terabyte of memory, the fact that the internal representation
currently limits the sieve range to about `6.8*10^25`

could become relevant.
Overflow in array indexing doesn't become a concern before memory and internal
representation would allow to sieve past `10^37`

.

On a 32-bit system, the internal representation imposes no additional limits,
but overflow has to be reckoned with. On the one hand, the fact that arrays are
`Int`

-indexed restricts the size of the prime store, on the other hand, overflow
in calculating the indices to cross off multiples is possible before running out
of memory. The former limits the upper bound of the monolithic `primeSieve`

to
shortly above `8*10^9`

, the latter limits the range of the segmented sieves to
about `1.7*10^18`

.

# Sieves and lists

List of primes.
Since the sieve uses unboxed arrays, overflow occurs at some point.
On 64-bit systems, that point is beyond the memory limits, on
32-bit systems, it is at about `1.7*10^18`

.

data PrimeSieve Source

Compact store of primality flags.

primeSieve :: Integer -> PrimeSieve Source

Sieve primes up to (and including) a bound. For small enough bounds, this is more efficient than using the segmented sieve.

Since arrays are `Int`

-indexed, overflow occurs when the sieve
size comes near

, that corresponds to an
upper bound near `maxBound`

:: `Int`

`15/8*`

. On `maxBound`

`32`

-bit systems, that
is often within memory limits, so don't give bounds larger than
`8*10^9`

there.

psieveList :: [PrimeSieve] Source

List of primes in the form of a list of `PrimeSieve`

s, more compact than
`primes`

, thus it may be better to use

than keeping the list of primes alive during the entire run.`psieveList`

>>= `primeList`

psieveFrom :: Integer -> [PrimeSieve] Source

creates the list of `psieveFrom`

n`PrimeSieve`

s starting roughly
at `n`

. Due to the organisation of the sieve, the list may contain
a few primes less than `n`

.
This form uses less memory than `[`

, hence it may be preferable
to use this if it is to be reused.`Integer`

]

primeList :: PrimeSieve -> [Integer] Source

Generate a list of primes for consumption from a
`PrimeSieve`

.