Prime numbers
From HaskellWiki
(→Tree merging with Wheel: add comment) |
|||
(107 intermediate revisions by one user not shown) | |||
Line 18: | Line 18: | ||
== Definition == | == Definition == | ||
− | In mathematics, ''amongst the natural numbers greater than 1'', a ''prime number'' (or a ''prime'') is such that has no divisors other than itself (and 1). The smallest prime is thus 2. Non-prime numbers are known as ''composite'', i.e. those representable as product of two natural numbers greater than 1. | + | In mathematics, ''amongst the natural numbers greater than 1'', a ''prime number'' (or a ''prime'') is such that has no divisors other than itself (and 1). The smallest prime is thus 2. Non-prime numbers are known as ''composite'', i.e. those representable as product of two natural numbers greater than 1. |
− | + | To find out a prime's multiples we can either '''a.''' test each new candidate number for divisibility by that prime, giving rise to a kind of ''trial division'' algorithm; or '''b.''' we can directly generate the multiples of a prime ''p'' by counting up from it in increments of ''p'', resulting in a variant of the ''sieve of Eratosthenes''. | |
− | + | The set of prime numbers is thus | |
− | : | + | : '''P''' = {''n'' ∈ '''N'''<sub>2</sub> ''':''' (∀ ''m'' ∈ '''N'''<sub>2</sub>) ((''m'' | ''n'') ⇒ m = n)} |
− | :: | + | :: = {''n'' ∈ '''N'''<sub>2</sub> ''':''' (∀ ''m'' ∈ '''N'''<sub>2</sub>) (''m''×''m'' ≤ ''n'' ⇒ ¬(''m'' | ''n''))} |
− | + | :: = '''N'''<sub>2</sub> \ {''n''×''m'' ''':''' ''n'',''m'' ∈ '''N'''<sub>2</sub>} | |
− | + | :: = '''N'''<sub>2</sub> \ '''⋃''' { {''n''×''m'' ''':''' ''m'' ∈ '''N'''<sub>n</sub>} ''':''' ''n'' ∈ '''N'''<sub>2</sub> } | |
+ | |||
+ | :: = '''N'''<sub>2</sub> \ '''⋃''' { {''n''×''n'', ''n''×''n''+''n'', ''n''×''n''+''n''+''n'', ...} ''':''' ''n'' ∈ '''N'''<sub>2</sub> } | ||
+ | |||
+ | :: = '''N'''<sub>2</sub> \ '''⋃''' { {''p''×''p'', ''p''×''p''+''p'', ''p''×''p''+''p''+''p'', ...} ''':''' ''p'' ∈ '''P''' } | ||
+ | :::: where '''N'''<sub>k</sub> = {''n'' ∈ '''N''' ''':''' ''n'' ≥ k} | ||
+ | |||
+ | Thus starting with 2, for each newly found prime we can ''eliminate'' from the rest of the numbers ''all the multiples'' of this prime, giving us the next available number as next prime. This is known as ''sieving'' the natural numbers, so that in the end all the composites are eliminated and what we are left with are just primes. <small>(This is what the last formula is describing, though seemingly [http://en.wikipedia.org/wiki/Impredicativity impredicative], because it is self-referential. But because '''N'''<sub>2</sub> is well-ordered (with the order being preserved under addition), the formula is well-defined.)</small> | ||
+ | |||
+ | In ''pseudocode'', this can be written as | ||
+ | |||
+ | <haskell> | ||
+ | primes = [2..] \ [[p*p, p*p+p..] | p <- primes] | ||
+ | </haskell> | ||
Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an [[#Tree merging with Wheel|efficient ''list''-based code]] we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results incrementally, one by one. | Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an [[#Tree merging with Wheel|efficient ''list''-based code]] we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results incrementally, one by one. | ||
== Sieve of Eratosthenes == | == Sieve of Eratosthenes == | ||
+ | Simplest, bounded, ''very'' inefficient formulation: | ||
+ | <haskell> | ||
+ | primesTo m = sieve [2..m] {- (\\) is set-difference for unordered lists -} | ||
+ | where | ||
+ | sieve (x:xs) = x : sieve (xs Data.List.\\ [x,x+x..m]) | ||
+ | sieve [] = [] | ||
+ | </haskell> | ||
− | The sieve of Eratosthenes calculates primes as | + | The (unbounded) sieve of Eratosthenes calculates primes as ''integers above 1 that are not multiples of primes'', i.e. ''not composite'' — whereas composites are found as enumeration of multiples of each prime, generated by counting up from prime's square in constant increments equal to that prime (or twice that much, for odd primes): |
<haskell> | <haskell> | ||
− | primes = 2 : 3 : ([5,7..] `minus` | + | primes = 2 : 3 : ([5,7..] `minus` _U [[p*p, p*p+2*p..] | p <- tail primes]) |
+ | |||
+ | {- Using `under n = takeWhile (<= n)`, with ordered increasing lists, | ||
+ | `minus`, `union` and `_U` satisfy, for any `n`: | ||
+ | under n (minus a b) == under n a \\ under n b | ||
+ | under n (union a b) == nub . sort $ under n a ++ under n b | ||
+ | under n . _U == nub . sort . concat | ||
+ | . takeWhile (not.null) . map (under n) -} | ||
</haskell> | </haskell> | ||
− | <code> | + | The definition is primed with 2 and 3 as initial primes, to avoid the vicious circle. |
+ | |||
+ | The ''"big union"'' <code>_U</code> function can be defined as the folding of <code>(\(x:xs) -> (x:) . union xs)</code>; or it could use a <code>Bool</code> array as a sorting and duplicates-removing device. The processing naturally divides up into the segments between successive squares of primes. | ||
Stepwise development follows (the fully developed version is [[#Tree merging with Wheel|here]]). | Stepwise development follows (the fully developed version is [[#Tree merging with Wheel|here]]). | ||
Line 48: | Line 77: | ||
=== Initial definition === | === Initial definition === | ||
− | + | First of all, working with ''ordered'' increasing lists, the sieve of Eratosthenes can be genuinely represented by | |
<haskell> | <haskell> | ||
− | -- genuine yet wasteful sieve of Eratosthenes | + | -- genuine yet wasteful sieve of Eratosthenes |
− | primesTo m = | + | -- primes = eratos [2.. ] -- unbounded |
− | + | primesTo m = eratos [2..m] -- bounded, up to m | |
− | + | where | |
− | -- eulers (p:xs) = p : eulers (xs `minus` map (p*)(p:xs)) | + | eratos [] = [] |
− | -- turner (p:xs) = p : turner [x | x <- xs, rem x p /= 0] | + | eratos (p:xs) = p : eratos (xs `minus` [p, p+p..]) |
+ | -- eratos (p:xs) = p : eratos (xs `minus` map (p*) [1..]) | ||
+ | -- eulers (p:xs) = p : eulers (xs `minus` map (p*) (p:xs)) | ||
+ | -- turner (p:xs) = p : turner [x | x <- xs, rem x p /= 0] | ||
</haskell> | </haskell> | ||
− | This should be regarded more like a ''specification'', not a code. It | + | This should be regarded more like a ''specification'', not a code. It runs at [https://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth empirical orders of growth] worse than quadratic in number of primes produced. But it has the core defining features of the classical formulation of S. of E. as '''''a.''''' being bounded, i.e. having a top limit value, and '''''b.''''' finding out the multiples of a prime directly, by counting up from it in constant increments, equal to that prime. |
− | The canonical list-difference <code>minus</code> and duplicates-removing | + | The canonical list-difference <code>minus</code> and duplicates-removing <code>union</code> functions (cf. [http://hackage.haskell.org/packages/archive/data-ordlist/latest/doc/html/Data-List-Ordered.html Data.List.Ordered package]) are: |
<haskell> | <haskell> | ||
− | -- ordered lists, difference and union | + | -- ordered lists, difference and union |
minus (x:xs) (y:ys) = case (compare x y) of | minus (x:xs) (y:ys) = case (compare x y) of | ||
LT -> x : minus xs (y:ys) | LT -> x : minus xs (y:ys) | ||
Line 76: | Line 108: | ||
</haskell> | </haskell> | ||
− | The name ''merge'' ought to be reserved for duplicates-preserving merging operation of | + | The name ''merge'' ought to be reserved for duplicates-preserving merging operation of the merge sort. |
=== Analysis === | === Analysis === | ||
− | So for each newly found prime | + | So for each newly found prime ''p'' the sieve discards its multiples, enumerating them by counting up in steps of ''p''. There are thus <math>O(m/p)</math> multiples generated and eliminated for each prime, and <math>O(m \log \log(m))</math> multiples in total, with duplicates, by virtues of [http://en.wikipedia.org/wiki/Prime_harmonic_series prime harmonic series]. |
If each multiple is dealt with in <math>O(1)</math> time, this will translate into <math>O(m \log \log(m))</math> RAM machine operations (since we consider addition as an atomic operation). Indeed mutable random-access arrays allow for that. But lists in Haskell are sequential-access, and complexity of <code>minus(a,b)</code> for lists is <math>\textstyle O(|a \cup b|)</math> instead of <math>\textstyle O(|b|)</math> of the direct access destructive array update. The lower the complexity of each ''minus'' step, the better the overall complexity. | If each multiple is dealt with in <math>O(1)</math> time, this will translate into <math>O(m \log \log(m))</math> RAM machine operations (since we consider addition as an atomic operation). Indeed mutable random-access arrays allow for that. But lists in Haskell are sequential-access, and complexity of <code>minus(a,b)</code> for lists is <math>\textstyle O(|a \cup b|)</math> instead of <math>\textstyle O(|b|)</math> of the direct access destructive array update. The lower the complexity of each ''minus'' step, the better the overall complexity. | ||
− | So on ''k''-th step the argument list <code>(p:xs)</code> that the <code>eratos</code> function gets starts with the ''(k+1)''-th prime, and consists of all the numbers ≤ ''m'' coprime with all the primes ≤ ''p''. According to the M. O'Neill's article (p.10) there are <math>\textstyle\Phi(m,p) \in \Theta(m/\log p)</math> such numbers. | + | So on ''k''-th step the argument list <code>(p:xs)</code> that the <code>eratos</code> function gets, starts with the ''(k+1)''-th prime, and consists of all the numbers ≤ ''m'' coprime with all the primes ≤ ''p''. According to the M. O'Neill's article (p.10) there are <math>\textstyle\Phi(m,p) \in \Theta(m/\log p)</math> such numbers. |
It looks like <math>\textstyle\sum_{i=1}^{n}{1/log(p_i)} = O(n/\log n)</math> for our intents and purposes. Since the number of primes below ''m'' is <math>n = \pi(m) = O(m/\log(m))</math> by the prime number theorem (where <math>\pi(m)</math> is a prime counting function), there will be ''n'' multiples-removing steps in the algorithm; it means total complexity of at least <math>O(m n/\log(n)) = O(m^2/(\log(m))^2)</math>, or <math>O(n^2)</math> in ''n'' primes produced - much much worse than the optimal <math>O(n \log(n) \log\log(n))</math>. | It looks like <math>\textstyle\sum_{i=1}^{n}{1/log(p_i)} = O(n/\log n)</math> for our intents and purposes. Since the number of primes below ''m'' is <math>n = \pi(m) = O(m/\log(m))</math> by the prime number theorem (where <math>\pi(m)</math> is a prime counting function), there will be ''n'' multiples-removing steps in the algorithm; it means total complexity of at least <math>O(m n/\log(n)) = O(m^2/(\log(m))^2)</math>, or <math>O(n^2)</math> in ''n'' primes produced - much much worse than the optimal <math>O(n \log(n) \log\log(n))</math>. | ||
Line 90: | Line 122: | ||
=== From Squares === | === From Squares === | ||
− | But we can start each step at a prime's square, as its smaller multiples will have been already produced on previous steps. This means we can stop early, when the prime's square reaches the top value ''m'', and thus | + | But we can start each elimination step at a prime's square, as its smaller multiples will have been already produced and discarded on previous steps, as multiples of smaller primes. This means we can stop early now, when the prime's square reaches the top value ''m'', and thus cut the total number of steps to around <math>\textstyle n = \pi(m^{0.5}) = \Theta(2m^{0.5}/\log m)</math>. This does not in fact change the complexity of random-access code, but for lists it makes it <math>O(m^{1.5}/(\log m)^2)</math>, or <math>O(n^{1.5}/(\log n)^{0.5})</math> in ''n'' primes produced, a dramatic speedup: |
<haskell> | <haskell> | ||
− | primesToQ m = 2 | + | primesToQ m = eratos [2..m] |
− | + | where | |
− | + | eratos [] = [] | |
+ | eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m]) | ||
+ | -- eratos (p:xs) = p : eratos (xs `minus` map (p*) [p..div m p]) | ||
+ | -- eulers (p:xs) = p : eulers (xs `minus` map (p*) (under (div m p) (p:xs))) | ||
+ | -- turner (p:xs) = p : turner [x | x<-xs, x<p*p || rem x p /= 0] | ||
</haskell> | </haskell> | ||
− | Its empirical complexity is | + | Its empirical complexity is around <math>O(n^{1.45})</math>. This simple optimization works here because this formulation is bounded (by an upper limit). To start late on a bounded sequence is to stop early (starting past end makes an empty sequence – ''see warning below''<sup><sub> 1</sub></sup>), thus preventing the creation of all the superfluous multiples streams which start above the upper bound anyway <small>(note that Turner's sieve is unaffected by this)</small>. This is acceptably slow now, striking a good balance between clarity, succinctness and efficiency. |
− | <small>''Warning'': this is predicated on a subtle point of <code>minus xs [] = xs</code> definition being used, as it indeed should be. If the definition <code>minus (x:xs) [] = x:minus xs []</code> is used, the problem is back and the complexity is bad again.</small> | + | <sup><sub>1</sub></sup><small>''Warning'': this is predicated on a subtle point of <code>minus xs [] = xs</code> definition being used, as it indeed should be. If the definition <code>minus (x:xs) [] = x:minus xs []</code> is used, the problem is back and the complexity is bad again.</small> |
=== Guarded === | === Guarded === | ||
This ought to be ''explicated'' (improving on clarity, though not on time complexity) as in the following, for which it is indeed a minor optimization whether to start from ''p'' or ''p*p'' - because it explicitly ''stops as soon as possible'': | This ought to be ''explicated'' (improving on clarity, though not on time complexity) as in the following, for which it is indeed a minor optimization whether to start from ''p'' or ''p*p'' - because it explicitly ''stops as soon as possible'': | ||
<haskell> | <haskell> | ||
− | primesToG m = 2 : sieve [3,5..m] | + | primesToG m = 2 : sieve [3,5..m] |
+ | where | ||
sieve (p:xs) | sieve (p:xs) | ||
| p*p > m = p : xs | | p*p > m = p : xs | ||
| otherwise = p : sieve (xs `minus` [p*p, p*p+2*p..]) | | otherwise = p : sieve (xs `minus` [p*p, p*p+2*p..]) | ||
+ | -- p : sieve (xs `minus` map (p*) [p,p+2..]) | ||
+ | -- p : eulers (xs `minus` map (p*) (p:xs)) | ||
</haskell> | </haskell> | ||
− | It is now clear that it can't be made unbounded just by abolishing the upper bound ''m'', because the guard can not be simply omitted without changing the complexity back for the worst. | + | (here we also flatly ignore all evens above 2 a priori.) It is now clear that it ''can't'' be made unbounded just by abolishing the upper bound ''m'', because the guard can not be simply omitted without changing the complexity back for the worst. |
=== Accumulating Array === | === Accumulating Array === | ||
− | So while <code>minus(a,b)</code> takes <math>O(|b|)</math> operations for random-access imperative arrays and about <math>O(|a|)</math> operations for lists | + | So while <code>minus(a,b)</code> takes <math>O(|b|)</math> operations for random-access imperative arrays and about <math>O(|a|)</math> operations here for ordered increasing lists of numbers, using Haskell's immutable array for ''a'' one ''could'' expect the array update time to be nevertheless closer to <math>O(|b|)</math> if destructive update were used implicitly by compiler for an array being passed along as an accumulating parameter: |
<haskell> | <haskell> | ||
{-# OPTIONS_GHC -O2 #-} | {-# OPTIONS_GHC -O2 #-} | ||
Line 127: | Line 166: | ||
</haskell> | </haskell> | ||
− | + | Indeed for unboxed arrays, with the type signature added explicitly <small>(suggested by Daniel Fischer)</small>, the above code runs pretty fast, with empirical complexity of about ''<math>O(n^{1.15..1.45})</math>'' in ''n'' primes produced (for producing from few hundred thousands to few millions primes, memory usage also slowly growing). But it relies on specific compiler optimizations, and indeed if we remove the explicit type signature, the code above turns ''very'' slow. | |
How can we write code that we'd be certain about? One way is to use explicitly mutable monadic arrays ([[#Using Mutable Arrays|''see below'']]), but we can also think about it a little bit more on the functional side of things still. | How can we write code that we'd be certain about? One way is to use explicitly mutable monadic arrays ([[#Using Mutable Arrays|''see below'']]), but we can also think about it a little bit more on the functional side of things still. | ||
=== Postponed === | === Postponed === | ||
− | Going back to ''guarded'' Eratosthenes, first we notice that though it works with minimal number of prime multiples streams, it still starts working with each | + | Going back to ''guarded'' Eratosthenes, first we notice that though it works with minimal number of prime multiples streams, it still starts working with each prematurely. Fixing this with explicit synchronization won't change complexity but will speed it up some more: |
<haskell> | <haskell> | ||
− | + | primesPE1 = 2 : sieve [3..] primesPE1 | |
where | where | ||
− | + | sieve xs (p:ps) | q <- p*p , (h,t) <- span (< q) xs = | |
+ | h ++ sieve (t `minus` [q, q+p..]) ps | ||
+ | -- h ++ turner [x|x<-t, rem x p /= 0] ps | ||
+ | </haskell> | ||
+ | <!-- primesPE1 = 2 : sieve [3,5..] 9 (tail primesPE1) | ||
+ | where | ||
+ | sieve xs q ~(p:t) | (h,ys) <- span (< q) xs = | ||
+ | h ++ sieve (ys `minus` [q, q+2*p..]) (head t^2) t | ||
+ | -- h ++ turner [x | x <- ys, rem x p /= 0] ... | ||
+ | --> | ||
+ | Inlining and fusing <code>span</code> and <code>(++)</code> we get: | ||
+ | <haskell> | ||
+ | primesPE = 2 : oddprimes | ||
+ | where | ||
+ | oddprimes = sieve [3,5..] 9 oddprimes | ||
sieve (x:xs) q ps@ ~(p:t) | sieve (x:xs) q ps@ ~(p:t) | ||
| x < q = x : sieve xs q ps | | x < q = x : sieve xs q ps | ||
| otherwise = sieve (xs `minus` [q, q+2*p..]) (head t^2) t | | otherwise = sieve (xs `minus` [q, q+2*p..]) (head t^2) t | ||
</haskell> | </haskell> | ||
− | Since the removal of a prime's multiples here starts at the right moment, and not just from the right place, the code could | + | Since the removal of a prime's multiples here starts at the right moment, and not just from the right place, the code could now finally be made unbounded. Because no multiples-removal process is started ''prematurely'', there are no ''extraneous'' multiples streams, which were the reason for the original formulation's extreme inefficiency. |
=== Segmented === | === Segmented === | ||
Line 147: | Line 200: | ||
<haskell> | <haskell> | ||
− | primesSE = 2 : | + | primesSE = 2 : oddprimes |
where | where | ||
− | + | oddprimes = sieve 3 9 oddprimes [] | |
sieve x q ~(p:t) fs = | sieve x q ~(p:t) fs = | ||
− | foldr (flip minus) [x,x+2..q-2] | + | foldr (flip minus) [x,x+2..q-2] -- chain of subtractions |
− | [[y+s, y+2*s..q] | (s,y) <- fs] | + | [[y+s, y+2*s..q] | (s,y) <- fs] -- OR, |
+ | -- [x,x+2..q-2] `minus` foldl union [] -- subtraction of merged | ||
+ | -- [[y+s, y+2*s..q] | (s,y) <- fs] -- lists | ||
++ sieve (q+2) (head t^2) t | ++ sieve (q+2) (head t^2) t | ||
((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs]) | ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs]) | ||
Line 165: | Line 220: | ||
<haskell> | <haskell> | ||
− | primesSTE = 2 : | + | primesSTE = 2 : oddprimes |
where | where | ||
− | + | oddprimes = sieve 3 9 oddprimes [] | |
sieve x q ~(p:t) fs = | sieve x q ~(p:t) fs = | ||
([x,x+2..q-2] `minus` joinST [[y+s, y+2*s..q] | (s,y) <- fs]) | ([x,x+2..q-2] `minus` joinST [[y+s, y+2*s..q] | (s,y) <- fs]) | ||
Line 173: | Line 228: | ||
((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs]) | ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs]) | ||
− | joinST ( | + | joinST (xs:t) = (union xs . joinST . pairs) t |
− | pairs ( | + | where |
− | pairs | + | pairs (xs:ys:t) = union xs ys : pairs t |
+ | pairs t = t | ||
joinST [] = [] | joinST [] = [] | ||
</haskell> | </haskell> | ||
− | === | + | ====Segmented merging via an array==== |
− | + | ||
− | + | The removal of composites is easy with arrays. Starting points can be calculated directly: | |
− | + | <haskell> | |
+ | import Data.List (inits) | ||
+ | import Data.Array.Unboxed | ||
+ | |||
+ | primesSAE = 2 : sieve 3 4 (tail primesSAE) (inits primesSAE) | ||
+ | where | ||
+ | sieve x q ps (fs:ft) = [i | (i,True) <- assocs ( | ||
+ | accumArray (\ _ _ -> False) | ||
+ | True (x,q-1) | ||
+ | [(i,()) | p <- fs, let c = p * div (x+p-1) p, | ||
+ | i <- [c, c+p..q-1]] :: UArray Int Bool )] | ||
+ | ++ sieve q (head ps^2) (tail ps) ft | ||
+ | </haskell> | ||
+ | === Linear merging === | ||
+ | But segmentation doesn't add anything substantially, and each multiples stream starts at its prime's square anyway. What does the [[#Postponed|Postponed]] code do, operationally? With each prime's square passed by, there emerges a nested linear ''left-deepening'' structure, '''''(...((xs-a)-b)-...)''''', where '''''xs''''' is the original odds-producing ''[3,5..]'' list, so that each odd it produces must go through more and more <code>minus</code> nodes on its way up - and those odd numbers that eventually emerge on top are prime. Thinking a bit about it, wouldn't another, ''right-deepening'' structure, '''''(xs-(a+(b+...)))''''', be better? This idea is due to Richard Bird, seen in his code presented in M. O'Neill's article, equivalent to: | ||
<haskell> | <haskell> | ||
− | + | primesB = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) | |
+ | [] primesB) | ||
+ | </haskell> | ||
+ | or, | ||
+ | |||
+ | <haskell> | ||
+ | primesLME1 = 2 : prs | ||
where | where | ||
− | + | prs = 3 : minus [5,7..] (joinL [[p*p, p*p+2*p..] | p <- prs]) | |
joinL ((x:xs):t) = x : union xs (joinL t) | joinL ((x:xs):t) = x : union xs (joinL t) | ||
</haskell> | </haskell> | ||
− | + | Here, ''xs'' stays near the top, and ''more frequently'' odds-producing streams of multiples of smaller primes are ''above'' those of the bigger primes, that produce ''less frequently'' their multiples which have to pass through ''more'' <code>union</code> nodes on their way up. Plus, no explicit synchronization is necessary anymore because the produced multiples of a prime start at its square anyway - just some care has to be taken to avoid a runaway access to the indefinitely-defined structure, defining <code>joinL</code> (or <code>foldr</code>'s combining function) to produce part of its result ''before'' accessing the rest of its input (making it ''productive''). | |
− | + | Melissa O'Neill [http://hackage.haskell.org/packages/archive/NumberSieves/0.0/doc/html/src/NumberTheory-Sieve-ONeill.html introduced double primes feed] to prevent unneeded memoization (a memory leak). We can even do multistage. Here's the code, faster still and with radically reduced memory consumption, with empirical orders of growth of around ~ <math>n^{1.40}</math> (initially better, yet worsening for bigger ranges): | |
− | + | ||
<haskell> | <haskell> | ||
− | + | primesLME = 2 : _Y ((3:) . minus [5,7..] . joinL . map (\p-> [p*p, p*p+2*p..])) | |
− | + | ||
− | + | _Y :: (t -> t) -> t | |
− | + | _Y g = g (_Y g) -- multistage, non-sharing, recursive | |
− | + | -- g x where x = g x -- two stages, sharing, corecursive | |
− | + | ||
− | + | ||
− | + | ||
</haskell> | </haskell> | ||
− | + | <code>_Y</code> is a non-sharing fixpoint combinator, here arranging for a recursive ''"telescoping"'' multistage primes production (a ''tower'' of producers). | |
− | + | This allows the <code>primesLME</code> stream to be discarded immediately as it is being consumed by its consumer. With <code>primes'</code> from <code>primesLME1</code> definition above it is impossible, as each produced element of <code>primes'</code> is needed later as input to the same <code>primes'</code> corecursive stream definition. So the <code>primes'</code> stream feeds in a loop into itself, and thus is retained in memory. With multistage production, each stage feeds into its consumer above it at the square of its current element which can be immediately discarded after it's been consumed. <code>(3:)</code> jump-starts the whole thing. | |
− | + | === Tree merging === | |
+ | Moreover, it can be changed into a '''''tree''''' structure. This idea [http://www.haskell.org/pipermail/haskell-cafe/2007-July/029391.html is due to Dave Bayer] and [[Prime_numbers_miscellaneous#Implicit_Heap|Heinrich Apfelmus]]: | ||
− | <haskell> | + | <haskell> |
+ | primesTME = 2 : _Y ((3:) . gaps 5 . joinT . map (\p-> [p*p, p*p+2*p..])) | ||
− | + | -- joinL ((x:xs):t) = x : union xs (joinL t) | |
− | + | joinT ((x:xs):t) = x : union xs (joinT (pairs t)) -- set union, ~= | |
− | + | where pairs (xs:ys:t) = union xs ys : pairs t -- nub.sort.concat | |
− | -- | + | gaps k s@(x:xs) | k < x = k:gaps (k+2) s -- ~= [k,k+2..]\\s, |
+ | | True = gaps (k+2) xs -- when null(s\\[k,k+2..]) | ||
</haskell> | </haskell> | ||
+ | |||
+ | This code is [http://ideone.com/p0e81 pretty fast], running at speeds and empirical complexities comparable with the code from Melissa O'Neill's article (about <math>O(n^{1.2})</math> in number of primes ''n'' produced). | ||
+ | |||
+ | As an aside, <code>joinT</code> is equivalent to [[Fold#Tree-like_folds|infinite tree-like folding]] <code>foldi (\(x:xs) ys-> x:union xs ys) []</code>: | ||
+ | |||
+ | [[Image:Tree-like_folding.gif|frameless|center|458px|tree-like folding]] | ||
=== Tree merging with Wheel === | === Tree merging with Wheel === | ||
− | Wheel factorization optimization can be further applied, and another tree structure can be used which is better adjusted for the primes multiples production (effecting about 5%-10% at the top of a total ''2.5x speedup'' w.r.t. the above tree merging on odds only | + | Wheel factorization optimization can be further applied, and another tree structure can be used which is better adjusted for the primes multiples production (effecting about 5%-10% at the top of a total ''2.5x speedup'' w.r.t. the above tree merging on odds only, for first few million primes): |
<haskell> | <haskell> | ||
− | + | primesTMWE = [2,3,5,7] ++ _Y ((11:) . tail . gapsW 11 wheel | |
− | primesTMWE = 2 | + | . joinT . hitsW 11 wheel) |
− | + | ||
− | + | ||
− | gapsW k | + | gapsW k (d:w) s@(c:cs) | k < c = k : gapsW (k+d) w s -- set difference |
− | + | | otherwise = gapsW (k+d) w cs -- k==c | |
− | + | hitsW k (d:w) s@(p:ps) | k < p = hitsW (k+d) w s -- intersection | |
− | + | | otherwise = scanl (\c d->c+p*d) (p*p) (d:w) | |
− | + | : hitsW (k+d) w ps -- k==p | |
− | + | ||
− | + | ||
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2: | wheel = 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:10:wheel | 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel | ||
+ | -- cycle $ zipWith (-) =<< tail $ [i | i <- [11..221], gcd i 210 == 1] | ||
+ | </haskell> | ||
+ | |||
+ | The <code>hitsW</code> is there to find the start point for rolling the wheel for each prime, but it can be found directly: | ||
+ | |||
+ | <haskell> | ||
+ | primesW = [2,3,5,7] ++ _Y ( (11:) . tail . gapsW 11 wheel . joinT . | ||
+ | map (\p-> | ||
+ | map (p*) . dropWhile (< p) $ | ||
+ | scanl (+) (p - rem (p-11) 210) wheel) ) | ||
</haskell> | </haskell> | ||
− | + | Seems to run about 1.4x faster, too. | |
====Above Limit - Offset Sieve==== | ====Above Limit - Offset Sieve==== | ||
− | Another task is to produce primes above a given value | + | Another task is to produce primes above a given value: |
<haskell> | <haskell> | ||
{-# OPTIONS_GHC -O2 -fno-cse #-} | {-# OPTIONS_GHC -O2 -fno-cse #-} | ||
primesFromTMWE primes m = dropWhile (< m) [2,3,5,7,11] | primesFromTMWE primes m = dropWhile (< m) [2,3,5,7,11] | ||
− | ++ gapsW a | + | ++ gapsW a wh2 (compositesFrom a) |
where | where | ||
− | (a, | + | (a,wh2) = rollFrom (snapUp (max 3 m) 3 2) |
− | (h, | + | (h,p2:t) = span (< z) $ drop 4 primes -- p < z => p*p<=a |
− | z = ceiling $ sqrt $ fromIntegral a + 1 -- | + | z = ceiling $ sqrt $ fromIntegral a + 1 -- p2>=z => p2*p2>a |
− | compositesFrom a = joinT (joinST [multsOf p a | p <- h++[ | + | compositesFrom a = joinT (joinST [multsOf p a | p <- h ++ [p2]] |
− | + | : [multsOf p (p*p) | p <- t] ) | |
− | snapUp v o step = v + ((o-v) | + | snapUp v o step = v + (mod (o-v) step) -- full steps from o |
multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- map (p*) $ | multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- map (p*) $ | ||
where -- scanl (+) x wh | where -- scanl (+) x wh | ||
Line 267: | Line 354: | ||
rollFrom n = go wheelNums wheel | rollFrom n = go wheelNums wheel | ||
where m = (n-11) `mod` 210 | where m = (n-11) `mod` 210 | ||
− | go (x:xs) ws@(w: | + | go (x:xs) ws@(w:ws2) | x < m = go xs ws2 |
| True = (n+x-m, ws) -- (x >= m) | | True = (n+x-m, ws) -- (x >= m) | ||
</haskell> | </haskell> | ||
Line 275: | Line 362: | ||
<haskell> | <haskell> | ||
primesFrom m = filter isPrime [m..] | primesFrom m = filter isPrime [m..] | ||
+ | </haskell> | ||
+ | |||
+ | === Map-based === | ||
+ | Runs ~1.7x slower than [[#Tree_merging|TME version]], but with the same empirical time complexity, ~<math>n^{1.2}</math> (in ''n'' primes produced) and same very low (near constant) memory consumption: | ||
+ | |||
+ | <haskell> | ||
+ | import Data.List -- based on http://stackoverflow.com/a/1140100 | ||
+ | import qualified Data.Map as M | ||
+ | |||
+ | primesMPE :: [Integer] | ||
+ | primesMPE = 2:mkPrimes 3 M.empty prs 9 -- postponed addition of primes into map; | ||
+ | where -- decoupled primes loop feed | ||
+ | prs = 3:mkPrimes 5 M.empty prs 9 | ||
+ | mkPrimes n m ps@ ~(p:t) q = case (M.null m, M.findMin m) of | ||
+ | (False, (n2, skips)) | n == n2 -> | ||
+ | mkPrimes (n+2) (addSkips n (M.deleteMin m) skips) ps q | ||
+ | _ -> if n<q | ||
+ | then n : mkPrimes (n+2) m ps q | ||
+ | else mkPrimes (n+2) (addSkip n m (2*p)) t (head t^2) | ||
+ | |||
+ | addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m | ||
+ | addSkips = foldl' . addSkip | ||
</haskell> | </haskell> | ||
== Turner's sieve - Trial division == | == Turner's sieve - Trial division == | ||
− | David Turner's | + | David Turner's ''(SASL Language Manual, 1983)'' formulation replaces non-standard <code>minus</code> in the sieve of Eratosthenes by stock list comprehension with <code>rem</code> filtering, turning it into a trial division algorithm: |
<haskell> | <haskell> | ||
− | -- unbounded sieve, premature filters | + | -- unbounded sieve, premature filters |
− | primesT = | + | primesT = sieve [2..] |
− | sieve (p:xs) = p : sieve [x | x <- xs, rem x p | + | where |
− | + | sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0] | |
+ | -- map head | ||
+ | -- $ iterate (\(p:xs) -> [x | x <- xs, rem x p > 0]) [2..] | ||
</haskell> | </haskell> | ||
− | This creates | + | This creates many superfluous implicit filters, because they are created prematurely. To be admitted as prime, ''each number'' will be ''tested for divisibility'' here by all its preceding primes, while just those not greater than its square root would suffice. To find e.g. the '''1001'''st prime (<code>7927</code>), '''1000''' filters are used, when in fact just the first '''24''' are needed (up to <code>89</code>'s filter only). Operational overhead here is huge. |
=== Guarded Filters === | === Guarded Filters === | ||
− | But this really ought to be changed into bounded and guarded variant, again achieving the ''"miraculous"'' complexity improvement from above quadratic to about <math>O(n^{1.45})</math> empirically (in ''n'' primes produced): | + | But this really ought to be changed into bounded and guarded variant, [[#From Squares|again achieving]] the ''"miraculous"'' complexity improvement from above quadratic to about <math>O(n^{1.45})</math> empirically (in ''n'' primes produced): |
<haskell> | <haskell> | ||
− | primesToGT m = | + | primesToGT m = sieve [2..m] |
+ | where | ||
sieve (p:xs) | sieve (p:xs) | ||
− | + | | p*p > m = p : xs | |
− | + | | True = p : sieve [x | x <- xs, rem x p > 0] | |
+ | -- (\(a,b:_) -> map head a ++ b) . span ((< m).(^2).head) | ||
+ | -- $ iterate (\(p:xs) -> [x | x <- xs, rem x p > 0]) [2..m] | ||
</haskell> | </haskell> | ||
=== Postponed Filters === | === Postponed Filters === | ||
− | + | Or it can remain unbounded, just filters creation must be ''postponed'' until the right moment: | |
<haskell> | <haskell> | ||
− | + | primesPT1 = 2 : sieve primesPT1 [3..] | |
where | where | ||
− | + | sieve (p:ps) xs = let (h,t) = span (< p*p) xs | |
+ | in h ++ sieve ps [x | x <- t, rem x p > 0] | ||
+ | -- fix $ concatMap (fst . fst) | ||
+ | -- . iterate (\((_,xs), p:ps) -> let (h,t) = span (< p*p) xs in | ||
+ | -- ((h, [x | x <- t, rem x p > 0]), ps)) | ||
+ | -- . (,) ([2],[3..]) | ||
+ | </haskell> | ||
+ | This is better re-written with <code>span</code> and <code>(++)</code> inlined and fused into the <code>sieve</code>: | ||
+ | <haskell> | ||
+ | primesPT = 2 : oddprimes | ||
+ | where | ||
+ | oddprimes = sieve [3,5..] 9 oddprimes | ||
sieve (x:xs) q ps@ ~(p:t) | sieve (x:xs) q ps@ ~(p:t) | ||
− | + | | x < q = x : sieve xs q ps | |
− | + | | True = sieve [x | x <- xs, rem x p /= 0] (head t^2) t | |
</haskell> | </haskell> | ||
− | creating here [[#Linear merging |as well]] the linear nested structure at run-time, <code>(...(([3,5..] >>= filterBy [3]) >>= filterBy [5])...)</code>, where <code>filterBy ds n = [n | noDivs | + | creating here [[#Linear merging |as well]] the linear nested structure at run-time, <code>(...(([3,5..] >>= filterBy [3]) >>= filterBy [5])...)</code>, where <code>filterBy ds n = [n | noDivs n ds]</code> (see <code>noDivs</code> definition below)  –  but unlike the original code, each filter being created at its proper moment, not sooner than the prime's square is seen. |
=== Optimal trial division === | === Optimal trial division === | ||
Line 316: | Line 441: | ||
The above is equivalent to the traditional formulation of trial division, | The above is equivalent to the traditional formulation of trial division, | ||
<haskell> | <haskell> | ||
− | noDivs | + | ps = 2 : [i | i <- [3..], |
− | + | and [rem i p > 0 | p <- takeWhile (\p -> p^2 <= i) ps]] | |
− | -- primes = filter (noDivs [2..]) [2..] | + | </haskell> |
− | primesTD = 2 : 3 : filter (noDivs | + | or, |
− | isPrime n = n > 1 && noDivs | + | <haskell> |
+ | noDivs n fs = foldr (\f r -> f*f > n || (rem n f > 0 && r)) True fs | ||
+ | -- primes = filter (`noDivs`[2..]) [2..] | ||
+ | -- = 2 : filter (`noDivs`[3,5..]) [3,5..] | ||
+ | primesTD = 2 : 3 : filter (`noDivs` tail primesTD) [5,7..] | ||
+ | isPrime n = n > 1 && noDivs n primesTD | ||
</haskell> | </haskell> | ||
except that this code is rechecking for each candidate number which primes to use, whereas for every candidate number in each segment between the successive squares of primes these will just be the same prefix of the primes list being built. | except that this code is rechecking for each candidate number which primes to use, whereas for every candidate number in each segment between the successive squares of primes these will just be the same prefix of the primes list being built. | ||
+ | |||
+ | Trial division is used as a simple [[Testing primality#Primality Test and Integer Factorization|primality test and prime factorization algorithm]]. | ||
=== Segmented Generate and Test === | === Segmented Generate and Test === | ||
− | + | Next we turn [[#Postponed Filters |the list of filters]] into one filter by an ''explicit'' list, each one in a progression of prefixes of the primes list. This seems to eliminate most recalculations, explicitly filtering composites out from batches of odds between the consecutive squares of primes. | |
<haskell> | <haskell> | ||
− | primesST = 2 : | + | import Data.List |
+ | |||
+ | primesST = 2 : oddprimes | ||
where | where | ||
− | + | oddprimes = sieve 3 9 oddprimes (inits oddprimes) -- [],[3],[3,5],... | |
− | sieve x q ~(_:t) | + | sieve x q ~(_:t) (fs:ft) = |
filter ((`all` fs) . ((/=0).) . rem) [x,x+2..q-2] | filter ((`all` fs) . ((/=0).) . rem) [x,x+2..q-2] | ||
− | ++ sieve (q+2) (head t^2) t | + | ++ sieve (q+2) (head t^2) t ft |
</haskell> | </haskell> | ||
− | |||
==== Generate and Test Above Limit ==== | ==== Generate and Test Above Limit ==== | ||
− | The following will start the segmented Turner sieve at the right place, using any primes list it's supplied with (e.g. [[ | + | The following will start the segmented Turner sieve at the right place, using any primes list it's supplied with (e.g. [[#Tree_merging_with_Wheel | TMWE]] etc.) or itself, as shown, demand computing it just up to the square root of any prime it'll produce: |
<haskell> | <haskell> | ||
− | primesFromST | + | primesFromST m | m > 2 = |
− | + | sieve (m`div`2*2+1) (head ps^2) (tail ps) (inits ps) | |
where | where | ||
− | (h,ps) = span (<= (floor.sqrt $ fromIntegral m+1)) | + | (h,ps) = span (<= (floor.sqrt $ fromIntegral m+1)) oddprimes |
− | sieve x q ps | + | sieve x q ps (fs:ft) = |
− | filter ((`all` fs) . ((/=0).) . rem) [x,x+2..q-2] | + | filter ((`all` (h ++ fs)) . ((/=0).) . rem) [x,x+2..q-2] |
− | ++ sieve (q+2) (head ps^2) (tail ps) | + | ++ sieve (q+2) (head ps^2) (tail ps) ft |
+ | oddprimes = 3 : primesFromST 5 -- odd primes | ||
</haskell> | </haskell> | ||
− | This is usually faster than testing candidate numbers for divisibility [[#Optimal trial division|one by one]] which has to re-fetch anew the needed prime factors to test by, for each candidate. Faster is the [[99_questions/Solutions/39#Solution_4.|offset sieve of Eratosthenes on odds]], and yet faster the | + | This is usually faster than testing candidate numbers for divisibility [[#Optimal trial division|one by one]] which has to re-fetch anew the needed prime factors to test by, for each candidate. Faster is the [[99_questions/Solutions/39#Solution_4.|offset sieve of Eratosthenes on odds]], and yet faster the one [[#Above_Limit_-_Offset_Sieve|w/ wheel optimization]], on this page. |
=== Conclusions === | === Conclusions === | ||
− | All these variants | + | All these variants being variations of trial division, finding out primes by direct divisibility testing of every candidate number by sequential primes below its square root (instead of just by ''its factors'', which is what ''direct generation of multiples'' is doing, essentially), are thus principally of worse complexity than that of Sieve of Eratosthenes. |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | The initial code is just a one-liner that ought to have been regarded as ''executable specification'' in the first place. It can easily be improved quite significantly with a simple use of bounded, guarded formulation to limit the number of filters it creates, or by postponement of filter creation. | |
== Euler's Sieve == | == Euler's Sieve == | ||
Line 366: | Line 496: | ||
<haskell> | <haskell> | ||
− | primesEU = 2 : | + | primesEU = 2 : eulers [3,5..] |
− | + | where | |
+ | eulers (p:xs) = p : eulers (xs `minus` map (p*) (p:xs)) | ||
+ | -- eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+2*p..]) | ||
</haskell> | </haskell> | ||
− | This code is extremely inefficient, running above <math>O({n^{2}})</math> complexity (and worsening rapidly), and should be regarded a ''specification'' only. Its memory usage is very high, with space complexity just below <math>O({n^{2}})</math>, in ''n'' primes produced. | + | This code is extremely inefficient, running above <math>O({n^{2}})</math> empirical complexity (and worsening rapidly), and should be regarded a ''specification'' only. Its memory usage is very high, with empirical space complexity just below <math>O({n^{2}})</math>, in ''n'' primes produced. |
+ | |||
+ | In the stream-based sieve of Eratosthenes we are able to ''skip'' along the input stream <code>xs</code> directly to the prime's square, consuming the whole prefix at once, thus achieving the results equivalent to the postponement technique, because the generation of the prime's multiples is independent of the rest of the stream. | ||
+ | |||
+ | But here in the Euler's sieve it ''is'' dependent on all <code>xs</code> and we're unable ''in principle'' to skip along it to the prime's square - because all <code>xs</code> are needed for each prime's multiples generation. Thus efficient unbounded stream-based implementation seems to be impossible in principle, under the simple scheme of producing the multiples by multiplication. | ||
=== Wheeled list representation === | === Wheeled list representation === | ||
Line 422: | Line 558: | ||
=== Generating Segments of Primes === | === Generating Segments of Primes === | ||
− | The sieve of Eratosthenes' | + | The sieve of Eratosthenes' [[#Segmented|removal of multiples on each segment of odds]] can be done by actually marking them in an array, instead of manipulating ordered lists, and can be further sped up more than twice by working with odds only: |
<haskell> | <haskell> | ||
− | + | import Data.Array.Unboxed | |
− | + | ||
− | primesSA = 2 : | + | primesSA :: [Int] |
+ | primesSA = 2 : oddprimes () | ||
where | where | ||
− | + | oddprimes () = 3 : sieve (oddprimes ()) 3 [] | |
− | sieve (p:ps) x fs = [i*2 + x | (i, | + | sieve (p:ps) x fs = [i*2 + x | (i,True) <- assocs a] |
− | ++ sieve ps (p*p) fs | + | ++ sieve ps (p*p) ((p,0) : |
+ | [(s, rem (y-q) s) | (s,y) <- fs]) | ||
where | where | ||
− | q | + | q = (p*p-x)`div`2 |
− | + | a :: UArray Int Bool | |
− | + | a = accumArray (\ b c -> False) True (1,q-1) | |
− | a | + | [(i,()) | (s,y) <- fs, i <- [y+s, y+s+s..q]] |
− | + | ||
</haskell> | </haskell> | ||
− | + | Runs significantly faster than [[#Tree merging with Wheel|TMWE]] and with better empirical complexity, of about <math>O(n^{1.10..1.05})</math> in producing first few millions of primes, with constant memory footprint. | |
− | + | ||
− | + | ||
=== Calculating Primes Upto a Given Value === | === Calculating Primes Upto a Given Value === | ||
Line 458: | Line 592: | ||
[(i,()) | i <- [9,15..n]] | [(i,()) | i <- [9,15..n]] | ||
f p a | q > n = a | f p a | q > n = a | ||
− | | True = if null x then | + | | True = if null x then a2 else f (head x) a2 |
where q = p*p | where q = p*p | ||
− | + | a2 :: UArray Int Bool | |
− | + | a2 = a // [(i,False) | i <- [q, q+2*p..n]] | |
− | x = [i | i <- [p+2,p+4..n], | + | x = [i | i <- [p+2,p+4..n], a2 ! i] |
</haskell> | </haskell> | ||
Line 471: | Line 605: | ||
++ [i | i <- [o,o+2..b], ar ! i] | ++ [i | i <- [o,o+2..b], ar ! i] | ||
where | where | ||
− | o = max (if even a then a+1 else a) 3 | + | o = max (if even a then a+1 else a) 3 -- first odd in the segment |
r = floor . sqrt $ fromIntegral b + 1 | r = floor . sqrt $ fromIntegral b + 1 | ||
− | ar = accumArray (\ | + | ar = accumArray (\_ _ -> False) True (o,b) -- initially all True, |
[(i,()) | p <- [3,5..r] | [(i,()) | p <- [3,5..r] | ||
− | , let q = p*p | + | , let q = p*p -- flip every multiple of an odd |
− | s = 2*p | + | s = 2*p -- to False |
(n,x) = quotRem (o - q) s | (n,x) = quotRem (o - q) s | ||
− | + | q2 = if o <= q then q | |
else q + (n + signum x)*s | else q + (n + signum x)*s | ||
− | , i <- [ | + | , i <- [q2,q2+s..b] ] |
</haskell> | </haskell> | ||
− | Although | + | Although sieving by odds instead of by primes, the array generation is so fast that it is very much feasible and even preferable for quick generation of some short spans of relatively big primes. |
== Using Mutable Arrays == | == Using Mutable Arrays == | ||
Line 607: | Line 741: | ||
* Speed/memory [http://ideone.com/p0e81 comparison table] for sieve of Eratosthenes variants. | * Speed/memory [http://ideone.com/p0e81 comparison table] for sieve of Eratosthenes variants. | ||
+ | |||
+ | * [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth Empirical orders of growth] on Wikipedia. | ||
[[Category:Code]] | [[Category:Code]] | ||
[[Category:Mathematics]] | [[Category:Mathematics]] |
Latest revision as of 09:06, 19 October 2016
In mathematics, amongst the natural numbers greater than 1, a prime number (or a prime) is such that has no divisors other than itself (and 1).
[edit] 1 Prime Number Resources
- At Wikipedia:
- HackageDB packages:
- arithmoi: Various basic number theoretic functions; efficient array-based sieves, Montgomery curve factorization ...
- Numbers: An assortment of number theoretic functions.
- NumberSieves: Number Theoretic Sieves: primes, factorization, and Euler's Totient.
- primes: Efficient, purely functional generation of prime numbers.
- Papers:
- O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004.
[edit] 2 Definition
In mathematics, amongst the natural numbers greater than 1, a prime number (or a prime) is such that has no divisors other than itself (and 1). The smallest prime is thus 2. Non-prime numbers are known as composite, i.e. those representable as product of two natural numbers greater than 1.
To find out a prime's multiples we can either a. test each new candidate number for divisibility by that prime, giving rise to a kind of trial division algorithm; or b. we can directly generate the multiples of a prime p by counting up from it in increments of p, resulting in a variant of the sieve of Eratosthenes.
The set of prime numbers is thus
- P = {n ∈ N_{2} : (∀ m ∈ N_{2}) ((m | n) ⇒ m = n)}
- = {n ∈ N_{2} : (∀ m ∈ N_{2}) (m×m ≤ n ⇒ ¬(m | n))}
- = N_{2} \ {n×m : n,m ∈ N_{2}}
- = N_{2} \ ⋃ { {n×m : m ∈ N_{n}} : n ∈ N_{2} }
- = N_{2} \ ⋃ { {n×n, n×n+n, n×n+n+n, ...} : n ∈ N_{2} }
- = N_{2} \ ⋃ { {p×p, p×p+p, p×p+p+p, ...} : p ∈ P }
- where N_{k} = {n ∈ N : n ≥ k}
- = N_{2} \ ⋃ { {p×p, p×p+p, p×p+p+p, ...} : p ∈ P }
Thus starting with 2, for each newly found prime we can eliminate from the rest of the numbers all the multiples of this prime, giving us the next available number as next prime. This is known as sieving the natural numbers, so that in the end all the composites are eliminated and what we are left with are just primes. (This is what the last formula is describing, though seemingly impredicative, because it is self-referential. But because N_{2} is well-ordered (with the order being preserved under addition), the formula is well-defined.)
In pseudocode, this can be written as
primes = [2..] \ [[p*p, p*p+p..] | p <- primes]
Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an efficient list-based code we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results incrementally, one by one.
[edit] 3 Sieve of Eratosthenes
Simplest, bounded, very inefficient formulation:
primesTo m = sieve [2..m] {- (\\) is set-difference for unordered lists -} where sieve (x:xs) = x : sieve (xs Data.List.\\ [x,x+x..m]) sieve [] = []
The (unbounded) sieve of Eratosthenes calculates primes as integers above 1 that are not multiples of primes, i.e. not composite — whereas composites are found as enumeration of multiples of each prime, generated by counting up from prime's square in constant increments equal to that prime (or twice that much, for odd primes):
primes = 2 : 3 : ([5,7..] `minus` _U [[p*p, p*p+2*p..] | p <- tail primes]) {- Using `under n = takeWhile (<= n)`, with ordered increasing lists, `minus`, `union` and `_U` satisfy, for any `n`: under n (minus a b) == under n a \\ under n b under n (union a b) == nub . sort $ under n a ++ under n b under n . _U == nub . sort . concat . takeWhile (not.null) . map (under n) -}
The definition is primed with 2 and 3 as initial primes, to avoid the vicious circle.
The "big union" _U
function can be defined as the folding of (\(x:xs) -> (x:) . union xs)
; or it could use a Bool
array as a sorting and duplicates-removing device. The processing naturally divides up into the segments between successive squares of primes.
Stepwise development follows (the fully developed version is here).
[edit] 3.1 Initial definition
First of all, working with ordered increasing lists, the sieve of Eratosthenes can be genuinely represented by
-- genuine yet wasteful sieve of Eratosthenes -- primes = eratos [2.. ] -- unbounded primesTo m = eratos [2..m] -- bounded, up to m where eratos [] = [] eratos (p:xs) = p : eratos (xs `minus` [p, p+p..]) -- eratos (p:xs) = p : eratos (xs `minus` map (p*) [1..]) -- eulers (p:xs) = p : eulers (xs `minus` map (p*) (p:xs)) -- turner (p:xs) = p : turner [x | x <- xs, rem x p /= 0]
This should be regarded more like a specification, not a code. It runs at empirical orders of growth worse than quadratic in number of primes produced. But it has the core defining features of the classical formulation of S. of E. as a. being bounded, i.e. having a top limit value, and b. finding out the multiples of a prime directly, by counting up from it in constant increments, equal to that prime.
The canonical list-difference minus
and duplicates-removing union
functions (cf. Data.List.Ordered package) are:
-- ordered lists, difference and union minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs union (x:xs) (y:ys) = case (compare x y) of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys union xs [] = xs union [] ys = ys
The name merge ought to be reserved for duplicates-preserving merging operation of the merge sort.
[edit] 3.2 Analysis
So for each newly found prime p the sieve discards its multiples, enumerating them by counting up in steps of p. There are thus O(m / p) multiples generated and eliminated for each prime, and O(mloglog(m)) multiples in total, with duplicates, by virtues of prime harmonic series.
If each multiple is dealt with in O(1) time, this will translate into O(mloglog(m)) RAM machine operations (since we consider addition as an atomic operation). Indeed mutable random-access arrays allow for that. But lists in Haskell are sequential-access, and complexity of minus(a,b)
for lists is instead of of the direct access destructive array update. The lower the complexity of each minus step, the better the overall complexity.
So on k-th step the argument list (p:xs)
that the eratos
function gets, starts with the (k+1)-th prime, and consists of all the numbers ≤ m coprime with all the primes ≤ p. According to the M. O'Neill's article (p.10) there are such numbers.
It looks like for our intents and purposes. Since the number of primes below m is n = π(m) = O(m / log(m)) by the prime number theorem (where π(m) is a prime counting function), there will be n multiples-removing steps in the algorithm; it means total complexity of at least O(mn / log(n)) = O(m^{2} / (log(m))^{2}), or O(n^{2}) in n primes produced - much much worse than the optimal O(nlog(n)loglog(n)).
[edit] 3.3 From Squares
But we can start each elimination step at a prime's square, as its smaller multiples will have been already produced and discarded on previous steps, as multiples of smaller primes. This means we can stop early now, when the prime's square reaches the top value m, and thus cut the total number of steps to around . This does not in fact change the complexity of random-access code, but for lists it makes it O(m^{1.5} / (logm)^{2}), or O(n^{1.5} / (logn)^{0.5}) in n primes produced, a dramatic speedup:
primesToQ m = eratos [2..m] where eratos [] = [] eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m]) -- eratos (p:xs) = p : eratos (xs `minus` map (p*) [p..div m p]) -- eulers (p:xs) = p : eulers (xs `minus` map (p*) (under (div m p) (p:xs))) -- turner (p:xs) = p : turner [x | x<-xs, x<p*p || rem x p /= 0]
Its empirical complexity is around O(n^{1.45}). This simple optimization works here because this formulation is bounded (by an upper limit). To start late on a bounded sequence is to stop early (starting past end makes an empty sequence – see warning below^{ 1}), thus preventing the creation of all the superfluous multiples streams which start above the upper bound anyway (note that Turner's sieve is unaffected by this). This is acceptably slow now, striking a good balance between clarity, succinctness and efficiency.
^{1}Warning: this is predicated on a subtle point of minus xs [] = xs
definition being used, as it indeed should be. If the definition minus (x:xs) [] = x:minus xs []
is used, the problem is back and the complexity is bad again.
[edit] 3.4 Guarded
This ought to be explicated (improving on clarity, though not on time complexity) as in the following, for which it is indeed a minor optimization whether to start from p or p*p - because it explicitly stops as soon as possible:
primesToG m = 2 : sieve [3,5..m] where sieve (p:xs) | p*p > m = p : xs | otherwise = p : sieve (xs `minus` [p*p, p*p+2*p..]) -- p : sieve (xs `minus` map (p*) [p,p+2..]) -- p : eulers (xs `minus` map (p*) (p:xs))
(here we also flatly ignore all evens above 2 a priori.) It is now clear that it can't be made unbounded just by abolishing the upper bound m, because the guard can not be simply omitted without changing the complexity back for the worst.
[edit] 3.5 Accumulating Array
So while minus(a,b)
takes O( | b | ) operations for random-access imperative arrays and about O( | a | ) operations here for ordered increasing lists of numbers, using Haskell's immutable array for a one could expect the array update time to be nevertheless closer to O( | b | ) if destructive update were used implicitly by compiler for an array being passed along as an accumulating parameter:
{-# OPTIONS_GHC -O2 #-} import Data.Array.Unboxed primesToA m = sieve 3 (array (3,m) [(i,odd i) | i<-[3..m]] :: UArray Int Bool) where sieve p a | p*p > m = 2 : [i | (i,True) <- assocs a] | a!p = sieve (p+2) $ a//[(i,False) | i <- [p*p, p*p+2*p..m]] | otherwise = sieve (p+2) a
Indeed for unboxed arrays, with the type signature added explicitly (suggested by Daniel Fischer), the above code runs pretty fast, with empirical complexity of about O(n^{1.15..1.45}) in n primes produced (for producing from few hundred thousands to few millions primes, memory usage also slowly growing). But it relies on specific compiler optimizations, and indeed if we remove the explicit type signature, the code above turns very slow.
How can we write code that we'd be certain about? One way is to use explicitly mutable monadic arrays (see below), but we can also think about it a little bit more on the functional side of things still.
[edit] 3.6 Postponed
Going back to guarded Eratosthenes, first we notice that though it works with minimal number of prime multiples streams, it still starts working with each prematurely. Fixing this with explicit synchronization won't change complexity but will speed it up some more:
primesPE1 = 2 : sieve [3..] primesPE1 where sieve xs (p:ps) | q <- p*p , (h,t) <- span (< q) xs = h ++ sieve (t `minus` [q, q+p..]) ps -- h ++ turner [x|x<-t, rem x p /= 0] ps
Inlining and fusing span
and (++)
we get:
primesPE = 2 : oddprimes where oddprimes = sieve [3,5..] 9 oddprimes sieve (x:xs) q ps@ ~(p:t) | x < q = x : sieve xs q ps | otherwise = sieve (xs `minus` [q, q+2*p..]) (head t^2) t
Since the removal of a prime's multiples here starts at the right moment, and not just from the right place, the code could now finally be made unbounded. Because no multiples-removal process is started prematurely, there are no extraneous multiples streams, which were the reason for the original formulation's extreme inefficiency.
[edit] 3.7 Segmented
With work done segment-wise between the successive squares of primes it becomes
primesSE = 2 : oddprimes where oddprimes = sieve 3 9 oddprimes [] sieve x q ~(p:t) fs = foldr (flip minus) [x,x+2..q-2] -- chain of subtractions [[y+s, y+2*s..q] | (s,y) <- fs] -- OR, -- [x,x+2..q-2] `minus` foldl union [] -- subtraction of merged -- [[y+s, y+2*s..q] | (s,y) <- fs] -- lists ++ sieve (q+2) (head t^2) t ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])
This "marks" the odd composites in a given range by generating them - just as a person performing the original sieve of Eratosthenes would do, counting one by one the multiples of the relevant primes. These composites are independently generated so some will be generated multiple times.
The advantage to working in spans explicitly is that this code is easily amendable to using arrays for the composites marking and removal on each finite span; and memory usage can be kept in check by using fixed sized segments.
[edit] 3.7.1 Segmented Tree-merging
Rearranging the chain of subtractions into a subtraction of merged streams (see below) and using tree-like folding structure, further speeds up the code and significantly improves its asymptotic time behavior (down to about O(n^{1.28}empirically), space is leaking though):
primesSTE = 2 : oddprimes where oddprimes = sieve 3 9 oddprimes [] sieve x q ~(p:t) fs = ([x,x+2..q-2] `minus` joinST [[y+s, y+2*s..q] | (s,y) <- fs]) ++ sieve (q+2) (head t^2) t ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs]) joinST (xs:t) = (union xs . joinST . pairs) t where pairs (xs:ys:t) = union xs ys : pairs t pairs t = t joinST [] = []
[edit] 3.7.2 Segmented merging via an array
The removal of composites is easy with arrays. Starting points can be calculated directly:
import Data.List (inits) import Data.Array.Unboxed primesSAE = 2 : sieve 3 4 (tail primesSAE) (inits primesSAE) where sieve x q ps (fs:ft) = [i | (i,True) <- assocs ( accumArray (\ _ _ -> False) True (x,q-1) [(i,()) | p <- fs, let c = p * div (x+p-1) p, i <- [c, c+p..q-1]] :: UArray Int Bool )] ++ sieve q (head ps^2) (tail ps) ft
[edit] 3.8 Linear merging
But segmentation doesn't add anything substantially, and each multiples stream starts at its prime's square anyway. What does the Postponed code do, operationally? With each prime's square passed by, there emerges a nested linear left-deepening structure, (...((xs-a)-b)-...), where xs is the original odds-producing [3,5..] list, so that each odd it produces must go through more and more minus
nodes on its way up - and those odd numbers that eventually emerge on top are prime. Thinking a bit about it, wouldn't another, right-deepening structure, (xs-(a+(b+...))), be better? This idea is due to Richard Bird, seen in his code presented in M. O'Neill's article, equivalent to:
primesB = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] primesB)
or,
primesLME1 = 2 : prs where prs = 3 : minus [5,7..] (joinL [[p*p, p*p+2*p..] | p <- prs]) joinL ((x:xs):t) = x : union xs (joinL t)
Here, xs stays near the top, and more frequently odds-producing streams of multiples of smaller primes are above those of the bigger primes, that produce less frequently their multiples which have to pass through more union
nodes on their way up. Plus, no explicit synchronization is necessary anymore because the produced multiples of a prime start at its square anyway - just some care has to be taken to avoid a runaway access to the indefinitely-defined structure, defining joinL
(or foldr
's combining function) to produce part of its result before accessing the rest of its input (making it productive).
Melissa O'Neill introduced double primes feed to prevent unneeded memoization (a memory leak). We can even do multistage. Here's the code, faster still and with radically reduced memory consumption, with empirical orders of growth of around ~ n^{1.40} (initially better, yet worsening for bigger ranges):
primesLME = 2 : _Y ((3:) . minus [5,7..] . joinL . map (\p-> [p*p, p*p+2*p..])) _Y :: (t -> t) -> t _Y g = g (_Y g) -- multistage, non-sharing, recursive -- g x where x = g x -- two stages, sharing, corecursive
_Y
is a non-sharing fixpoint combinator, here arranging for a recursive "telescoping" multistage primes production (a tower of producers).
This allows the primesLME
stream to be discarded immediately as it is being consumed by its consumer. With primes'
from primesLME1
definition above it is impossible, as each produced element of primes'
is needed later as input to the same primes'
corecursive stream definition. So the primes'
stream feeds in a loop into itself, and thus is retained in memory. With multistage production, each stage feeds into its consumer above it at the square of its current element which can be immediately discarded after it's been consumed. (3:)
jump-starts the whole thing.
[edit] 3.9 Tree merging
Moreover, it can be changed into a tree structure. This idea is due to Dave Bayer and Heinrich Apfelmus:
primesTME = 2 : _Y ((3:) . gaps 5 . joinT . map (\p-> [p*p, p*p+2*p..])) -- joinL ((x:xs):t) = x : union xs (joinL t) joinT ((x:xs):t) = x : union xs (joinT (pairs t)) -- set union, ~= where pairs (xs:ys:t) = union xs ys : pairs t -- nub.sort.concat gaps k s@(x:xs) | k < x = k:gaps (k+2) s -- ~= [k,k+2..]\\s, | True = gaps (k+2) xs -- when null(s\\[k,k+2..])
This code is pretty fast, running at speeds and empirical complexities comparable with the code from Melissa O'Neill's article (about O(n^{1.2}) in number of primes n produced).
As an aside, joinT
is equivalent to infinite tree-like folding foldi (\(x:xs) ys-> x:union xs ys) []
:
[edit] 3.10 Tree merging with Wheel
Wheel factorization optimization can be further applied, and another tree structure can be used which is better adjusted for the primes multiples production (effecting about 5%-10% at the top of a total 2.5x speedup w.r.t. the above tree merging on odds only, for first few million primes):
primesTMWE = [2,3,5,7] ++ _Y ((11:) . tail . gapsW 11 wheel . joinT . hitsW 11 wheel) gapsW k (d:w) s@(c:cs) | k < c = k : gapsW (k+d) w s -- set difference | otherwise = gapsW (k+d) w cs -- k==c hitsW k (d:w) s@(p:ps) | k < p = hitsW (k+d) w s -- intersection | otherwise = scanl (\c d->c+p*d) (p*p) (d:w) : hitsW (k+d) w ps -- k==p wheel = 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:10:wheel -- cycle $ zipWith (-) =<< tail $ [i | i <- [11..221], gcd i 210 == 1]
The hitsW
is there to find the start point for rolling the wheel for each prime, but it can be found directly:
primesW = [2,3,5,7] ++ _Y ( (11:) . tail . gapsW 11 wheel . joinT . map (\p-> map (p*) . dropWhile (< p) $ scanl (+) (p - rem (p-11) 210) wheel) )
Seems to run about 1.4x faster, too.
[edit] 3.10.1 Above Limit - Offset Sieve
Another task is to produce primes above a given value:
{-# OPTIONS_GHC -O2 -fno-cse #-} primesFromTMWE primes m = dropWhile (< m) [2,3,5,7,11] ++ gapsW a wh2 (compositesFrom a) where (a,wh2) = rollFrom (snapUp (max 3 m) 3 2) (h,p2:t) = span (< z) $ drop 4 primes -- p < z => p*p<=a z = ceiling $ sqrt $ fromIntegral a + 1 -- p2>=z => p2*p2>a compositesFrom a = joinT (joinST [multsOf p a | p <- h ++ [p2]] : [multsOf p (p*p) | p <- t] ) snapUp v o step = v + (mod (o-v) step) -- full steps from o multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- map (p*) $ where -- scanl (+) x wh (x,wh) = rollFrom (snapUp from p (2*p) `div` p) -- , if p < from wheelNums = scanl (+) 0 wheel rollFrom n = go wheelNums wheel where m = (n-11) `mod` 210 go (x:xs) ws@(w:ws2) | x < m = go xs ws2 | True = (n+x-m, ws) -- (x >= m)
A certain preprocessing delay makes it worthwhile when producing more than just a few primes, otherwise it degenerates into simple trial division, which is then ought to be used directly:
primesFrom m = filter isPrime [m..]
[edit] 3.11 Map-based
Runs ~1.7x slower than TME version, but with the same empirical time complexity, ~n^{1.2} (in n primes produced) and same very low (near constant) memory consumption:
import Data.List -- based on http://stackoverflow.com/a/1140100 import qualified Data.Map as M primesMPE :: [Integer] primesMPE = 2:mkPrimes 3 M.empty prs 9 -- postponed addition of primes into map; where -- decoupled primes loop feed prs = 3:mkPrimes 5 M.empty prs 9 mkPrimes n m ps@ ~(p:t) q = case (M.null m, M.findMin m) of (False, (n2, skips)) | n == n2 -> mkPrimes (n+2) (addSkips n (M.deleteMin m) skips) ps q _ -> if n<q then n : mkPrimes (n+2) m ps q else mkPrimes (n+2) (addSkip n m (2*p)) t (head t^2) addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m addSkips = foldl' . addSkip
[edit] 4 Turner's sieve - Trial division
David Turner's (SASL Language Manual, 1983) formulation replaces non-standard minus
in the sieve of Eratosthenes by stock list comprehension with rem
filtering, turning it into a trial division algorithm:
-- unbounded sieve, premature filters primesT = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0] -- map head -- $ iterate (\(p:xs) -> [x | x <- xs, rem x p > 0]) [2..]
This creates many superfluous implicit filters, because they are created prematurely. To be admitted as prime, each number will be tested for divisibility here by all its preceding primes, while just those not greater than its square root would suffice. To find e.g. the 1001st prime (7927
), 1000 filters are used, when in fact just the first 24 are needed (up to 89
's filter only). Operational overhead here is huge.
[edit] 4.1 Guarded Filters
But this really ought to be changed into bounded and guarded variant, again achieving the "miraculous" complexity improvement from above quadratic to about O(n^{1.45}) empirically (in n primes produced):
primesToGT m = sieve [2..m] where sieve (p:xs) | p*p > m = p : xs | True = p : sieve [x | x <- xs, rem x p > 0] -- (\(a,b:_) -> map head a ++ b) . span ((< m).(^2).head) -- $ iterate (\(p:xs) -> [x | x <- xs, rem x p > 0]) [2..m]
[edit] 4.2 Postponed Filters
Or it can remain unbounded, just filters creation must be postponed until the right moment:
primesPT1 = 2 : sieve primesPT1 [3..] where sieve (p:ps) xs = let (h,t) = span (< p*p) xs in h ++ sieve ps [x | x <- t, rem x p > 0] -- fix $ concatMap (fst . fst) -- . iterate (\((_,xs), p:ps) -> let (h,t) = span (< p*p) xs in -- ((h, [x | x <- t, rem x p > 0]), ps)) -- . (,) ([2],[3..])
This is better re-written with span
and (++)
inlined and fused into the sieve
:
primesPT = 2 : oddprimes where oddprimes = sieve [3,5..] 9 oddprimes sieve (x:xs) q ps@ ~(p:t) | x < q = x : sieve xs q ps | True = sieve [x | x <- xs, rem x p /= 0] (head t^2) t
creating here as well the linear nested structure at run-time, (...(([3,5..] >>= filterBy [3]) >>= filterBy [5])...)
, where filterBy ds n = [n | noDivs n ds]
(see noDivs
definition below) – but unlike the original code, each filter being created at its proper moment, not sooner than the prime's square is seen.
[edit] 4.3 Optimal trial division
The above is equivalent to the traditional formulation of trial division,
ps = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (\p -> p^2 <= i) ps]]
or,
noDivs n fs = foldr (\f r -> f*f > n || (rem n f > 0 && r)) True fs -- primes = filter (`noDivs`[2..]) [2..] -- = 2 : filter (`noDivs`[3,5..]) [3,5..] primesTD = 2 : 3 : filter (`noDivs` tail primesTD) [5,7..] isPrime n = n > 1 && noDivs n primesTD
except that this code is rechecking for each candidate number which primes to use, whereas for every candidate number in each segment between the successive squares of primes these will just be the same prefix of the primes list being built.
Trial division is used as a simple primality test and prime factorization algorithm.
[edit] 4.4 Segmented Generate and Test
Next we turn the list of filters into one filter by an explicit list, each one in a progression of prefixes of the primes list. This seems to eliminate most recalculations, explicitly filtering composites out from batches of odds between the consecutive squares of primes.
import Data.List primesST = 2 : oddprimes where oddprimes = sieve 3 9 oddprimes (inits oddprimes) -- [],[3],[3,5],... sieve x q ~(_:t) (fs:ft) = filter ((`all` fs) . ((/=0).) . rem) [x,x+2..q-2] ++ sieve (q+2) (head t^2) t ft
[edit] 4.4.1 Generate and Test Above Limit
The following will start the segmented Turner sieve at the right place, using any primes list it's supplied with (e.g. TMWE etc.) or itself, as shown, demand computing it just up to the square root of any prime it'll produce:
primesFromST m | m > 2 = sieve (m`div`2*2+1) (head ps^2) (tail ps) (inits ps) where (h,ps) = span (<= (floor.sqrt $ fromIntegral m+1)) oddprimes sieve x q ps (fs:ft) = filter ((`all` (h ++ fs)) . ((/=0).) . rem) [x,x+2..q-2] ++ sieve (q+2) (head ps^2) (tail ps) ft oddprimes = 3 : primesFromST 5 -- odd primes
This is usually faster than testing candidate numbers for divisibility one by one which has to re-fetch anew the needed prime factors to test by, for each candidate. Faster is the offset sieve of Eratosthenes on odds, and yet faster the one w/ wheel optimization, on this page.
[edit] 4.5 Conclusions
All these variants being variations of trial division, finding out primes by direct divisibility testing of every candidate number by sequential primes below its square root (instead of just by its factors, which is what direct generation of multiples is doing, essentially), are thus principally of worse complexity than that of Sieve of Eratosthenes.
The initial code is just a one-liner that ought to have been regarded as executable specification in the first place. It can easily be improved quite significantly with a simple use of bounded, guarded formulation to limit the number of filters it creates, or by postponement of filter creation.
[edit] 5 Euler's Sieve
[edit] 5.1 Unbounded Euler's sieve
With each found prime Euler's sieve removes all its multiples in advance so that at each step the list to process is guaranteed to have no multiples of any of the preceding primes in it (consists only of numbers coprime with all the preceding primes) and thus starts with the next prime:
primesEU = 2 : eulers [3,5..] where eulers (p:xs) = p : eulers (xs `minus` map (p*) (p:xs)) -- eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+2*p..])
This code is extremely inefficient, running above O(n^{2}) empirical complexity (and worsening rapidly), and should be regarded a specification only. Its memory usage is very high, with empirical space complexity just below O(n^{2}), in n primes produced.
In the stream-based sieve of Eratosthenes we are able to skip along the input stream xs
directly to the prime's square, consuming the whole prefix at once, thus achieving the results equivalent to the postponement technique, because the generation of the prime's multiples is independent of the rest of the stream.
But here in the Euler's sieve it is dependent on all xs
and we're unable in principle to skip along it to the prime's square - because all xs
are needed for each prime's multiples generation. Thus efficient unbounded stream-based implementation seems to be impossible in principle, under the simple scheme of producing the multiples by multiplication.
[edit] 5.2 Wheeled list representation
The situation can be somewhat improved using a different list representation, for generating lists not from a last element and an increment, but rather a last span and an increment, which entails a set of helpful equivalences:
{- fromElt (x,i) = x : fromElt (x + i,i) === iterate (+ i) x [n..] === fromElt (n,1) === fromSpan ([n],1) [n,n+2..] === fromElt (n,2) === fromSpan ([n,n+2],4) -} fromSpan (xs,i) = xs ++ fromSpan (map (+ i) xs,i) {- === concat $ iterate (map (+ i)) xs fromSpan (p:xt,i) === p : fromSpan (xt ++ [p + i], i) fromSpan (xs,i) `minus` fromSpan (ys,i) === fromSpan (xs `minus` ys, i) map (p*) (fromSpan (xs,i)) === fromSpan (map (p*) xs, p*i) fromSpan (xs,i) === forall (p > 0). fromSpan (concat $ take p $ iterate (map (+ i)) xs, p*i) -} spanSpecs = iterate eulerStep ([2],1) eulerStep (xs@(p:_), i) = ( (tail . concat . take p . iterate (map (+ i))) xs `minus` map (p*) xs, p*i ) {- > mapM_ print $ take 4 spanSpecs ([2],1) ([3],2) ([5,7],6) ([7,11,13,17,19,23,29,31],30) -}
Generating a list from a span specification is like rolling a wheel as its pattern gets repeated over and over again. For each span specification w@((p:_),_)
produced by eulerStep
, the numbers in (fromSpan w)
up to p^{2} are all primes too, so that
eulerPrimesTo m = if m > 1 then go ([2],1) else [] where go w@((p:_), _) | m < p*p = takeWhile (<= m) (fromSpan w) | True = p : go (eulerStep w)
This runs at about O(n^{1.5..1.8}) complexity, for n
primes produced, and also suffers from a severe space leak problem (IOW its memory usage is also very high).
[edit] 6 Using Immutable Arrays
[edit] 6.1 Generating Segments of Primes
The sieve of Eratosthenes' removal of multiples on each segment of odds can be done by actually marking them in an array, instead of manipulating ordered lists, and can be further sped up more than twice by working with odds only:
import Data.Array.Unboxed primesSA :: [Int] primesSA = 2 : oddprimes () where oddprimes () = 3 : sieve (oddprimes ()) 3 [] sieve (p:ps) x fs = [i*2 + x | (i,True) <- assocs a] ++ sieve ps (p*p) ((p,0) : [(s, rem (y-q) s) | (s,y) <- fs]) where q = (p*p-x)`div`2 a :: UArray Int Bool a = accumArray (\ b c -> False) True (1,q-1) [(i,()) | (s,y) <- fs, i <- [y+s, y+s+s..q]]
Runs significantly faster than TMWE and with better empirical complexity, of about O(n^{1.10..1.05}) in producing first few millions of primes, with constant memory footprint.
[edit] 6.2 Calculating Primes Upto a Given Value
Equivalent to Accumulating Array above, running somewhat faster (compiled by GHC with optimizations turned on):
{-# OPTIONS_GHC -O2 #-} import Data.Array.Unboxed primesToNA n = 2: [i | i <- [3,5..n], ar ! i] where ar = f 5 $ accumArray (\ a b -> False) True (3,n) [(i,()) | i <- [9,15..n]] f p a | q > n = a | True = if null x then a2 else f (head x) a2 where q = p*p a2 :: UArray Int Bool a2 = a // [(i,False) | i <- [q, q+2*p..n]] x = [i | i <- [p+2,p+4..n], a2 ! i]
[edit] 6.3 Calculating Primes in a Given Range
primesFromToA a b = (if a<3 then [2] else []) ++ [i | i <- [o,o+2..b], ar ! i] where o = max (if even a then a+1 else a) 3 -- first odd in the segment r = floor . sqrt $ fromIntegral b + 1 ar = accumArray (\_ _ -> False) True (o,b) -- initially all True, [(i,()) | p <- [3,5..r] , let q = p*p -- flip every multiple of an odd s = 2*p -- to False (n,x) = quotRem (o - q) s q2 = if o <= q then q else q + (n + signum x)*s , i <- [q2,q2+s..b] ]
Although sieving by odds instead of by primes, the array generation is so fast that it is very much feasible and even preferable for quick generation of some short spans of relatively big primes.
[edit] 7 Using Mutable Arrays
Using mutable arrays is the fastest but not the most memory efficient way to calculate prime numbers in Haskell.
[edit] 7.1 Using ST Array
This method implements the Sieve of Eratosthenes, similar to how you might do it in C, modified to work on odds only. It is fast, but about linear in memory consumption, allocating one (though apparently packed) sieve array for the whole sequence to process.
import Control.Monad import Control.Monad.ST import Data.Array.ST import Data.Array.Unboxed sieveUA :: Int -> UArray Int Bool sieveUA top = runSTUArray $ do let m = (top-1) `div` 2 r = floor . sqrt $ fromIntegral top + 1 sieve <- newArray (1,m) True -- :: ST s (STUArray s Int Bool) forM_ [1..r `div` 2] $ \i -> do isPrime <- readArray sieve i when isPrime $ do -- ((2*i+1)^2-1)`div`2 == 2*i*(i+1) forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do writeArray sieve j False return sieve primesToUA :: Int -> [Int] primesToUA top = 2 : [i*2+1 | (i,True) <- assocs $ sieveUA top]
Its empirical time complexity is improving with n (number of primes produced) from above O(n^{1.20}) towards O(n^{1.16}). The reference C++ vector-based implementation exhibits this improvement in empirical time complexity too, from O(n^{1.5}) gradually towards O(n^{1.12}), where tested (which might be interpreted as evidence towards the expected quasilinearithmic O(nlog(n)log(logn)) time complexity).
[edit] 7.2 Bitwise prime sieve with Template Haskell
Count the number of prime below a given 'n'. Shows fast bitwise arrays, and an example of Template Haskell to defeat your enemies.
{-# OPTIONS -O2 -optc-O -XBangPatterns #-} module Primes (nthPrime) where import Control.Monad.ST import Data.Array.ST import Data.Array.Base import System import Control.Monad import Data.Bits nthPrime :: Int -> Int nthPrime n = runST (sieve n) sieve n = do a <- newArray (3,n) True :: ST s (STUArray s Int Bool) let cutoff = truncate (sqrt $ fromIntegral n) + 1 go a n cutoff 3 1 go !a !m cutoff !n !c | n >= m = return c | otherwise = do e <- unsafeRead a n if e then if n < cutoff then let loop !j | j < m = do x <- unsafeRead a j when x $ unsafeWrite a j False loop (j+n) | otherwise = go a m cutoff (n+2) (c+1) in loop ( if n < 46340 then n * n else n `shiftL` 1) else go a m cutoff (n+2) (c+1) else go a m cutoff (n+2) c
And place in a module:
{-# OPTIONS -fth #-} import Primes main = print $( let x = nthPrime 10000000 in [| x |] )
Run as:
$ ghc --make -o primes Main.hs $ time ./primes 664579 ./primes 0.00s user 0.01s system 228% cpu 0.003 total
[edit] 8 Implicit Heap
See Implicit Heap.
[edit] 9 Prime Wheels
See Prime Wheels.
[edit] 10 Using IntSet for a traditional sieve
See Using IntSet for a traditional sieve.
[edit] 11 Testing Primality, and Integer Factorization
See Testing primality:
[edit] 12 One-liners
See primes one-liners.
[edit] 13 External links
- A collection of prime generators; the file "ONeillPrimes.hs" contains one of the fastest pure-Haskell prime generators; code by Melissa O'Neill.
- WARNING: Don't use the priority queue from older versions of that file for your projects: it's broken and works for primes only by a lucky chance. The revised version of the file fixes the bug, as pointed out by Eugene Kirpichov on February 24, 2009 on the haskell-cafe mailing list, and fixed by Bertram Felgenhauer.
- test entries for (some of) the above code variants.
- Speed/memory comparison table for sieve of Eratosthenes variants.
- Empirical orders of growth on Wikipedia.