Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell98 |

`AUTHOR`

- Dr. Alistair Ward
`DESCRIPTION`

- Defines a
*prime-wheel*, for use in prime-number generation; http://en.wikipedia.org/wiki/Wheel_factorization.

- type Distance i = (i, [i])
- type NPrimes = Int
- type PrimeMultiples i = [i]
- data PrimeWheel i
- estimateOptimalSize :: Integral i => i -> NPrimes
- generateMultiples :: Integral i => i -> [i] -> [i]
- roll :: Integral i => PrimeWheel i -> [Distance i]
- rotate :: Integral i => Distance i -> Distance i
- mkPrimeWheel :: Integral i => NPrimes -> PrimeWheel i
- getCircumference :: Integral i => PrimeWheel i -> i
- getSpokeCount :: Integral i => PrimeWheel i -> i

# Types

## Type-synonyms

type Distance i = (i, [i]) Source

Couples a candidate prime with a *rolling wheel*, to define the distance rolled.

The size of the *wheel*, measured by the number of primes from which it is composed.

type PrimeMultiples i = [i] Source

An infinite increasing sequence, of the multiples of a specific prime.

## Data-types

data PrimeWheel i Source

- A conceptual
*wheel*, with irregularly spaced spokes; http://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#Prime_Wheels. - On being rolled, the trace of the spokes, identifies candidates which are
*coprime*to those primes from which the*wheel*was composed. - One can alternatively view this as a set of vertical nested rings, each with a
*prime circumference*, and touching at its lowest point. Each has a single mark on its*circumference*, which when rolled identifies multiples of that*circumference*. When the complete set is rolled, from the state where all marks are coincident, all multiples of the set of primes, are traced. - CAVEAT: The distance required to return to this state (the wheel's
*circumference*), grows rapidly with the number of primes:

zip [0 ..] . scanl (*) 1 $ [2,3,5,7,11,13,17,19,23,29,31] [(0,1),(1,2),(2,6),(3,30),(4,210),(5,2310),(6,30030),(7,510510),(8,9699690),(9,223092870),(10,6469693230),(11,200560490130)]

- The number of spokes also grows rapidly with the number of primes:

zip [0 ..] . scanl (*) 1 . map pred $ [2,3,5,7,11,13,17,19,23,29,31] [(0,1),(1,1),(2,2),(3,8),(4,48),(5,480),(6,5760),(7,92160),(8,1658880),(9,36495360),(10,1021870080),(11,30656102400)]

Show i => Show (PrimeWheel i) |

# Functions

estimateOptimalSize :: Integral i => i -> NPrimes Source

- The optimal number of low primes from which to build the
*wheel*, grows with the number of primes required; the*circumference*should be approximately the*square-root*of the number of integers it will be required to sieve. - CAVEAT: one greater than this is returned, which empirically seems better.

:: Integral i | |

=> i | The number to square and multiply |

-> [i] | A |

-> [i] |

- Generates multiples of the specified prime, starting from its
*square*, skipping those multiples of the low primes from which the specified`PrimeWheel`

was composed, and which therefore, the*wheel*won't generate as candidates. Eg:

Prime Rotating PrimeWheel 3 Output ===== ===================== ====== 7 [4,2,4,2,4,6,2,6] [49,77,91,119,133,161,203,217,259 ..] 11 [2,4,2,4,6,2,6,4] [121,143,187,209,253,319,341,407 ..] 13 [4,2,4,6,2,6,4,2] [169,221,247,299,377,403,481,533,559 ..]

roll :: Integral i => PrimeWheel i -> [Distance i] Source

Generate an infinite, increasing sequence of candidate primes, from the specified *wheel*.

rotate :: Integral i => Distance i -> Distance i Source

Generates a new candidate prime, from a *rolling wheel*, and the current candidate.

## Constructors

mkPrimeWheel :: Integral i => NPrimes -> PrimeWheel i Source

Smart constructor for a *wheel* from the specified number of low primes.

- The optimal number of low primes from which to build the
*wheel*, grows with the number of primes required; the*circumference*should be approximately the*square-root*of the number of integers it will be required to sieve. - The sequence of gaps between spokes on the
*wheel*is*symmetrical under reflection*; though two values lie*on*the axis, that aren't part of this symmetry. Eg:

nPrimes Gaps ====== ==== 0 [1] 1 [2] -- The terminal gap for all subsequent wheels is '2'; [(succ circumference `mod` circumference) - (pred circumference `mod` circumference)]. 2 [4,2] -- Both points are on the axis, so the symmetry isn't yet clear. 3 [6,4,2,4,2,4,6,2] 4 [10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2]

Exploitation of this property has proved counter-productive, probably because it requires *strict evaluation*,
exposing the user to the full cost of inadvertently choosing a *wheel*, which in practice, is rotated less than once.

## Query

getCircumference :: Integral i => PrimeWheel i -> i Source

The *circumference* of the specified `PrimeWheel`

.

getSpokeCount :: Integral i => PrimeWheel i -> i Source

The number of spokes in the specified `PrimeWheel`

.