Sieve of Eratosthenes: Difference between revisions
→{{header|Scala}}: corrected code and comments, added a section using HashMap...
GordonBGood (talk | contribs) (→Sub-optimal tail recursive trial division: Scala - used tail recursion to implement a true Sieve of Eratosthenes (page segmented "infinite" iteration)...) |
GordonBGood (talk | contribs) (→{{header|Scala}}: corrected code and comments, added a section using HashMap...) |
||
Line 4,444:
}
// BitSet toList is shuffled when using the ParSet version.
println(sieveOfEratosthenes(100).toList.sorted)
println(sieveOfEratosthenes(100000000).size)</lang>
{{out}}
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
5761455</pre>
=== Using tail recursion===
The below code using a primitive array (bit packed) and tail recursion to avoid some of the enumeration delays is almost three times faster:
<lang Scala>
def sieveOfEratosthenes(nTo: Int) = {
val nonprimes: Array[Int] = new Array((nTo >>> 5) + 1)
def cullp(p: Int) = { @tailrec def cull(c: Int): Unit = { if (c <= nTo) {
for { p <- 2 to Math.sqrt(nTo).toInt
if ((nonprimes(p >>> 5). & (1 << (p & 31))) == 0) } cullp(p)
def nextprime(i: Int): Int = { if (i > nTo) i else
if ((nonprimes(i >>> 5) & (1 << (i & 31))) != 0) nextprime(i + 1) else i }
Iterator.iterate(2)(c => nextprime(c + 1)).takeWhile(_ <= nTo)
}</lang>
===Odds-only page-segmented "infinite" generator version using tail recursion===
The above code still uses an amount of memory proportional to the range of the sieve (although bit packed). As well as only sieving odd candidates, the following code uses a fixed range buffer that is about the size of the CPU L1 cache plus only storage for the base primes up to the square root of the range for a large potential saving in RAM memory used. The use of innermost tail recursive loops rather than "higher order" functions from iterators also greatly reduces execution time, with much of the remaining time used just to enumerate the primes output:
<lang Scala>import scala.annotation.tailrec
def SoEPg(): Iterator[Int] = {
val basePrimesArr : ArrayBuffer[Int] = ArrayBuffer()
def makePg(lowp: Int, basePrimes: Iterator[Int]) = {
val buf: Array[Int] = new
def
if ((i < 131072) && ((buf(i >>> 5) & (1 << (i & 31)))) != 0) nexti(i + 1)
def cullp(s: Int, p: Int) = { @tailrec def cull(c: Int): Unit = {
if (
cull(c + p) } }; cull(s) }
val bps = if (low <= 0) { //page zero has no base primes...
.takeWhile(_ <= Math.sqrt(262145).toInt).foreach(p => {
cullp((p * p - 3) >>> 1, p) }); basePrimes }
else { val nbps = if (basePrimesArr.length == 0) {
val nbasePrimes = SoEPg(); nbasePrimes.next() // new source primes > 2
basePrimesArr += nbasePrimes.next(); nbasePrimes; } else basePrimes
val np =
fillBasePrimes(np) } else bp }
fillBasePrimes(basePrimesArr(basePrimesArr.length - 1))
for (p <- basePrimesArr) {
val s = if (
(Iterator.iterate(nextPrime(lowp))(p => nextPrime(p + 2))
.takeWhile(_ < nxtlowp), nxtlowp, bps) }
Iterator.single(2) ++
}</lang>
As the above and all following sieves are "infinite", they all require an extra range limiting condition to produce a finite output, such as the addition of ".takeWhile(_ <= topLimit)" where "topLimit" is the specified range.
While the above code is reasonably fast, much of the execution time is consumed by the use of the built-in functions and iterators for concise code, especially in the use of iterators for primes output. A longer version using "roll-your-own" iteration or using a class with built in combined "higher-order" functions would be faster for many tasks using primes such as summing over a range, counting, et cetera.
===Odds-Only "infinite" generator sieve using Streams and Co-Inductive Streams===
Using Streams, [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf the "unfaithful sieve"], i.e. '''sub-optimal trial division sieve. Not a sieve of Eratosthenes'''.
<lang scala>def sieve(nums: Stream[Int]): Stream[Int] =
Line 4,540 ⟶ 4,520:
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</pre>
The above code is extremely inefficient for larger ranges, both because it tests for primality using computationally expensive divide (modulo) operations and because it sets up deferred tests for division by all of the primes up to each prime candidate, meaning that it has approximately a square law computational complexity with range.
The following code uses delayed recursion via Streams to implement the Richard Bird algorithm mentioned in the last part (the Epilogue) of the above linked article, which is '''a true incremental Sieve of Eratosthenes'''. It is nowhere near as fast as the array based solutions due to the overhead of functionally chasing the merging of the prime multiple streams; this also means that the empirical performance is not according to the usual Sieve of Eratosthenes approximations due to this overhead increasing as the log of the sieved range, but it is much better than the above "unfaithful" sieve.
<lang scala>def primesBird() : Stream[Int] = {
Line 4,591 ⟶ 4,573:
Further gains in performance for these last two implementations can be had by using further wheel factorization and "tree folding/merging" as per [http://www.haskell.org/haskellwiki/Primes#Tree_merging_with_Wheel this Haskell implementation].
===Odds-Only "infinite" generator sieve using a hash table (HashMap)===
As per the "unfaithful sieve" article linked above, the incremental "infinite" Sieve of Eratosthenes can be implemented using a hash table instead of a Priority Queue or Map (Binary Heap) as were used in that article. The following implementation postpones the adding of base prime representations to the hash table until necessary to keep the hash table small:
<lang scala>def SoEInc(): Iterator[Int] = {
val nextComposites = scala.collection.mutable.HashMap[Int,Int]()
def oddPrimes(): Iterator[Int] = {
val basePrimes = SoEInc(); basePrimes.next(); basePrimes.next() // skip the two and three prime factors
@tailrec def makePrime(state: (Int,Int,Int)): (Int,Int,Int) = {
val (candidate, nextBasePrime, nextSquare) = state
if (candidate >= nextSquare) {
val adv = nextBasePrime << 1
nextComposites.+=((nextSquare + adv) -> adv)
val np = basePrimes.next()
makePrime((candidate + 2, np, np * np))
}
else if (nextComposites.contains(candidate)) {
val adv = nextComposites(candidate)
nextComposites.-=(candidate)
.+=(Iterator.iterate(candidate + adv)(_ + adv)
.dropWhile(nextComposites.contains(_)).next() -> adv)
makePrime((candidate + 2, nextBasePrime, nextSquare))
} else (candidate, nextBasePrime, nextSquare)
}
Iterator.iterate((5,3,9))({case (c, p, q) => makePrime((c + 2, p, q)) })
.map({case (p, _, _) => p})
}
List(2,3).toIterator ++ oddPrimes()
}</lang>
The above could be implemented using Streams or Co-Inductive Streams to pass the continuation parameters as passed here in a tuple but there would be no real difference in speed and there is no need to use the implied laziness. As compared to the versions of the Bird (or tree folding) Sieve of Eratosthenes, this has the expected same computational complexity as the array based versions, but is about 20 times slower due to the constant overhead of processing the key value hashing. Memory use is quite low, only being the hash table entries for each of the base prime values less than the square root of the last prime enumerated multiplied by the size of each hash entry (about 12 bytes in this case) plus a "load factor" percentage overhead in hash table size to minimize hash collisions (about twice as large as entries actually used by default on average).
The Scala implementable of a mutable HashMap is slower than the java.util.HashMap one by a factor of almost two, but the Scala version is used here to keep the code more portable (as to CLR). One can also quite easily convert this code to use the immutable Scala HashMap, but the code runs about four times slower due to the required "copy on update" operations for immutable objects.
This algorithm is very responsive to further application of wheel factorization, which can make it run up to about four times faster for the composite number culling operations; however, that is not enough to allow it to catch up to the array based sieves.
=={{header|Scheme}}==
| |||