primes (empty) → 0.1

raw patch · 5 files changed

+172/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

• Data/Numbers/Primes.hs +114/−0
• LICENSE +15/−0
• README +8/−0
• Setup.hs +4/−0
• primes.cabal +31/−0

@@ -0,0 +1,114 @@+-- |+-- Module      : Data.Numbers.Primes+-- Copyright   : Sebastian Fischer+-- License     : PublicDomain+-- +-- Maintainer  : Sebastian Fischer (sebf@informatik.uni-kiel.de)+-- Stability   : experimental+-- Portability : portable+-- +-- This Haskell library provides an efficient lazy wheel sieve for+-- prime generation ispired by "Lazy wheel sieves and spirals of+-- primes" [1] by Colin Runciman and "The Genuine Sieve of+-- Eratosthenes" [2] by Melissa O'Neil.+-- +-- [1]: <http://www.cs.york.ac.uk/ftpdir/pub/colin/jfp97lw.ps.gz>+-- +-- [2]: <http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf>+-- +module Data.Numbers.Primes ( primes, wheelSieve ) where++-- | +-- This global constant is an infinite list of prime numbers. It is+-- generated by a lazy wheel sieve and shared among different+-- applications. If you are concerned about the memory requirements of+-- sharing many primes you can call the function @wheelSieve@+-- directly.+-- +primes :: [Integer]+primes = wheelSieve 6++-- |+-- This function returns an infinite list of prime numbers by sieving+-- with a wheel that cancels the multiples of the first @n@ primes+-- where @n@ is the argument given to @wheelSieve@. Don't use too+-- large wheels because computing them is more expensive than+-- sieving. The number @6@ is a good value to pass to this function.+-- +wheelSieve :: Int        -- ^ number of primes canceled by the wheel+           -> [Integer]  -- ^ infinite list of primes+wheelSieve k = reverse ps ++ sieve (spin p (cycle ns)) Empty + where (p:ps,ns)     = wheel k+       spin n (x:xs) = n : spin (n+x) xs+++-- Auxiliary Definitions+------------------------------------------------------------------------------++-- Sieves a list of prime candidates using a lazy priority queue.+--+sieve :: [Integer] -> Queue -> [Integer] +sieve (n:ns) Empty = n : sieve ns (enqueue (map (n*) (n:ns)) Empty) +sieve (n:ns) queue +  | m == n         = sieve ns (enqueue ms q) +  | m < n          = sieve (n:ns) (enqueue ms q) +  | otherwise      = n : sieve ns (enqueue (map (n*) (n:ns)) queue) + where (m:ms,q) = dequeue queue ++-- A wheel consists of a list of primes whose multiples are canceled+-- and the actual wheel that is rolled for canceling.+--+type Wheel = ([Integer],[Integer])++-- Computes a wheel that cancels the multiples of the given number+-- (plus 1) of primes.+--+-- For example:+--+-- wheel 0 = ([2],[1]) +-- wheel 1 = ([3,2],[2]) +-- wheel 2 = ([5,3,2],[2,4]) +-- wheel 3 = ([7,5,3,2],[4,2,4,2,4,6,2,6])+--+wheel :: Int -> Wheel+wheel n = iterate next ([2],[1]) !! n++next :: Wheel -> Wheel+next (ps@(p:_),xs) = (py:ps,cancel (product ps) p py ys)+ where+  (y:ys) = cycle xs+  py = p + y++cancel :: Integer -> Integer -> Integer -> [Integer] -> [Integer]+cancel 0 _ _ _ = []+cancel m p n (x:ys@(y:zs))+  | nx `mod` p > 0 = x : cancel (m-x) p nx ys+  | otherwise      = cancel m p n (x+y:zs)+ where nx = n + x+++-- We use a special version of priority queues implemented as "pairing+-- heaps" ((see "Purely functional datastructures by Chris Okasaki).+--+-- The queue stores non-empty lists of multiples; the first element is+-- used as priority.+--+data Queue = Empty | Fork [Integer] [Queue] ++enqueue :: [Integer] -> Queue -> Queue+enqueue ns = merge (Fork ns []) ++merge :: Queue -> Queue -> Queue+merge Empty y = y; merge x Empty = x +merge x y | prio x <= prio y = join x y +          | otherwise        = join y x + where prio (Fork (n:_) _)   = n +       join (Fork ns qs) q   = Fork ns (q:qs) ++dequeue :: Queue -> ([Integer], Queue)+dequeue (Fork ns qs) = (ns,mergeAll qs) ++mergeAll :: [Queue] -> Queue+mergeAll [] = Empty; mergeAll [x] = x +mergeAll (x:y:qs) = merge (merge x y) (mergeAll qs)+

@@ -0,0 +1,15 @@+ALL PUBLIC DOMAIN MATERIAL IS OFFERED AS-IS. NO REPRESENTATIONS OR+WARRANTIES OF ANY KIND ARE MADE CONCERNING THE MATERIALS, EXPRESS,+IMPLIED, STATUTORY OR OTHERWISE, INCLUDING, WITHOUT LIMITATION,+WARRANTIES OF TITLE, MERCHANTIBILITY, FITNESS FOR A PARTICULAR+PURPOSE, NONINFRINGEMENT, OR THE ABSENCE OF LATENT OR OTHER DEFECTS,+ACCURACY, OR THE PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT+DISCOVERABLE.++IN NO EVENT WILL THE AUTHOR(S), PUBLISHER(S), OR PRESENTER(S) OF ANY+PUBLIC DOMAIN MATERIAL BE LIABLE TO YOU ON ANY LEGAL THEORY FOR ANY+SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE OR EXEMPLARY DAMAGES+ARISING OUT OF THIS LICENSE OR THE USE OF THE WORK, EVEN IF THE+AUTHOR(S), PUBLISHER(S), OR PRESENTER(S) HAVE BEEN ADVISED OF THE+POSSIBILITY OF SUCH DAMAGES.+

@@ -0,0 +1,8 @@+This Haskell library provides an efficient lazy wheel sieve for prime+generation ispired by "Lazy wheel sieves and spirals of primes" [1] by+Colin Runciman and "The Genuine Sieve of Eratosthenes" [2] by Melissa+O'Neil.++[1]: <http://www.cs.york.ac.uk/ftpdir/pub/colin/jfp97lw.ps.gz>+[2]: <http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf>+

@@ -0,0 +1,4 @@+import Distribution.Simple++main = defaultMain+

@@ -0,0 +1,31 @@+Name:          primes+Version:       0.1+Cabal-Version: >= 1.6+Synopsis:      Efficient, purely functional generation of prime numbers+Description:   ++  This Haskell library provides an efficient lazy wheel sieve for+  prime generation ispired by "Lazy wheel sieves and spirals of+  primes" by Colin Runciman and "The Genuine Sieve of Eratosthenes" by+  Melissa O'Neil.++Category:      Algorithms, Numerical+License:       PublicDomain+License-File:  LICENSE+Author:        Sebastian Fischer+Maintainer:    Sebastian Fischer+Bug-Reports:   mailto:sebf@informatik.uni-kiel.de+Homepage:      http://github.com/sebfisch/primes+Build-Type:    Simple+Stability:     experimental++Extra-Source-Files: README++Library+  Build-Depends:    base+  Exposed-Modules:  Data.Numbers.Primes+  Ghc-Options:      -Wall -fno-warn-incomplete-patterns++Source-Repository head+  type:     git+  location: git://github.com/sebfisch/primes.git