Primality by trial division: Difference between revisions

Content added Content deleted
m (→‎Sieve by trial division: whitespace (uniformity))
(→‎Sieve by trial division: rmv type signature ; promote "segmented generate-and-test"; copy-editing)
Line 476: Line 476:
===Sieve by trial division===
===Sieve by trial division===
One often sees a ''"naive"'' version presented as an unbounded [[Sieve of Eratosthenes#Haskell|sieve of Eratosthenes]], similar to David Turner's 1975 SASL code,
One often sees a ''"naive"'' version presented as an unbounded [[Sieve of Eratosthenes#Haskell|sieve of Eratosthenes]], similar to David Turner's 1975 SASL code,
<lang haskell>primes :: [Integer]
<lang haskell>primes = sieve [2..] where
primes = sieve [2..] where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]</lang>
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]</lang>
As is shown in Melissa O'Neill's [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], this is rather a sub-optimal ''trial division'' algorithm. Its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced. A priority queue-based SoE version also is presented in the article, with and without [http://en.wikipedia.org/wiki/Wheel_factorization wheels].
As is shown in Melissa O'Neill's [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], this is rather a sub-optimal ''trial division'' algorithm. Its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced.


The above is easily fixed into having normal trial division complexity, at a price of making it bounded again:
The above is easily fixed into having normal trial division complexity, by making it bounded again:


<lang haskell>primesTo m = 2 : sieve [3,5..m] where
<lang haskell>primesTo m = 2 : sieve [3,5..m] where
Line 489: Line 488:
To make it unbounded, the guard can not be simply discarded.
To make it unbounded, the guard can not be simply discarded.


====Segmented Generate and Test====
===Segmented Generate and Test===
Starting each filter no sooner than it is actually needed, and rearranging to avoid redundant recalculations, leads to the following.
Starting each filter no sooner than it is actually needed, and rearranging to avoid recalculations, leads to this:
<lang haskell>primes = 2 : 3 : sieve 5 9 (drop 2 primes) 0 where
<lang haskell>primes = 2 : 3 : sieve 5 9 (drop 2 primes) 0 where
sieve x q ps k = let fs = take k (tail primes) in
sieve x q ps k = let fs = take k (tail primes) in
Line 496: Line 495:
++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang>
++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang>


Can be used as a framework for unbounded segmented sieves, replacing divisibility testing with e.g. proper SoE code on arrays etc. Runs at empirical <math>O(n^{1.45})</math> time complexity, in ''n'' primes produced.
Runs at empirical <math>O(n^{1.45})</math> time complexity, in ''n'' primes produced. Can be used as a framework for unbounded segmented sieves, replacing divisibility testing with proper sieve of Eratosthenes etc.


=={{header|HicEst}}==
=={{header|HicEst}}==
Retrieved from "https://rosettacode.org/wiki/Primality_by_trial_division"