factory-0.2.1.0: Rational arithmetic in an irrational world.

Safe HaskellSafe-Inferred

Factory.Data.PrimeWheel

Contents

Description

AUTHOR
Dr. Alistair Ward
DESCRIPTION
Defines a prime-wheel, for use in prime-number generation; http://en.wikipedia.org/wiki/Wheel_factorization.

Synopsis

Types

Type-synonyms

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

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

type NPrimes = IntSource

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)]

Instances

Show i => Show (PrimeWheel i) 

Functions

estimateOptimalSize :: Integral i => i -> NPrimesSource

  • 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.

generateMultiplesSource

Arguments

:: Integral i 
=> i

The number to square and multiply

-> [i]

A rolling wheel, the track of which, delimits the gaps between coprime candidates.

-> [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 iSource

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

Constructors

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

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 -> iSource

The circumference of the specified PrimeWheel.

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

The number of spokes in the specified PrimeWheel.