primes 0.1 → 0.1.1
raw patch · 3 files changed
+39/−43 lines, 3 files
Files
- Data/Numbers/Primes.hs +30/−34
- README +3/−3
- primes.cabal +6/−6
Data/Numbers/Primes.hs view
@@ -8,17 +8,15 @@ -- 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>+-- prime generation inspired by /Lazy wheel sieves and spirals of/+-- /primes/ by Colin Runciman+-- (<http://www.cs.york.ac.uk/ftpdir/pub/colin/jfp97lw.ps.gz>) and+-- /The Genuine Sieve of Eratosthenes/ by Melissa O'Neil+-- (<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@@ -37,7 +35,7 @@ -- wheelSieve :: Int -- ^ number of primes canceled by the wheel -> [Integer] -- ^ infinite list of primes-wheelSieve k = reverse ps ++ sieve (spin p (cycle ns)) Empty +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 @@ -47,13 +45,13 @@ -- 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 +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.@@ -65,9 +63,9 @@ -- -- For example: ----- wheel 0 = ([2],[1]) --- wheel 1 = ([3,2],[2]) --- wheel 2 = ([5,3,2],[2,4]) +-- 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@@ -75,9 +73,8 @@ next :: Wheel -> Wheel next (ps@(p:_),xs) = (py:ps,cancel (product ps) p py ys)- where- (y:ys) = cycle xs- py = p + y+ where (y:ys) = cycle xs+ py = p + y cancel :: Integer -> Integer -> Integer -> [Integer] -> [Integer] cancel 0 _ _ _ = []@@ -87,28 +84,27 @@ where nx = n + x --- We use a special version of priority queues implemented as "pairing--- heaps" ((see "Purely functional datastructures by Chris Okasaki).+-- We use a special version of priority queues implemented as /pairing/+-- /heaps/ (see /Purely Functional Data Structures/ by Chris Okasaki). -- -- The queue stores non-empty lists of multiples; the first element is -- used as priority. ---data Queue = Empty | Fork [Integer] [Queue] +data Queue = Empty | Fork [Integer] [Queue] enqueue :: [Integer] -> Queue -> Queue-enqueue ns = merge (Fork ns []) +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) +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) +dequeue (Fork ns qs) = (ns,mergeAll qs) mergeAll :: [Queue] -> Queue-mergeAll [] = Empty; mergeAll [x] = x +mergeAll [] = Empty; mergeAll [x] = x mergeAll (x:y:qs) = merge (merge x y) (mergeAll qs)-
README view
@@ -1,7 +1,7 @@ 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.+generation inspired 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>
primes.cabal view
@@ -1,20 +1,20 @@ Name: primes-Version: 0.1+Version: 0.1.1 Cabal-Version: >= 1.6 Synopsis: Efficient, purely functional generation of prime numbers-Description: +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.+ prime generation inspired 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+Bug-Reports: http://github.com/sebfisch/primes/issues Homepage: http://github.com/sebfisch/primes Build-Type: Simple Stability: experimental