I see that there has been some discussion on the list about prime finding algorithms recently. I just wanted to contribute my own humble algorithm: primes :: [Integer] primes = primesFilter 1 [2..] primesFilter :: Integer -> [Integer] -> [Integer] primesFilter primorial (n:ns) | (gcd primorial n == 1) = n : (primesFilter (primorial*n) ns) | otherwise = primesFilter primorial ns Comparing it to some of the algorithms in: http://www.haskell.org/pipermail/haskell-cafe/2007-February/022765.html It seems to perform reasonably well. It also has the advantage of being quite short. Ruben
On 2/22/07, Ruben Zilibowitz
I see that there has been some discussion on the list about prime finding algorithms recently. I just wanted to contribute my own humble algorithm: [snip] Comparing it to some of the algorithms in: http://www.haskell.org/pipermail/haskell-cafe/2007-February/022765.html
It seems to perform reasonably well. It also has the advantage of being quite short.
It has the advantage of conciseness, and for small enough examples will give reasonable results, though computing O(n/log(n)) gcds can be very expensive. One suggestion I would make is to build the list in reverse order. Since the test proceeds through the list from left to right, and an arbitrary positive integer is more likely to be divisible by a small primes than a larger one, this ought to produce a faster result when the input is composite. Steve
Ruben Zilibowitz wrote:
I see that there has been some discussion on the list about prime finding algorithms recently. I just wanted to contribute my own humble algorithm:
Thanks!
Comparing it to some of the algorithms in: http://www.haskell.org/pipermail/haskell-cafe/2007-February/ 022765.html
It seems to perform reasonably well. It also has the advantage of being quite short.
I've added it to my table. It's fun to find new ways to figure out primes, but I think the "shortness advantage" goes to the naive primes algorithm, which is faster and shorter. Melissa. ------------------------------------------------------------------ Time (in seconds) for Number of Primes ---------------------------------------------------- Algorithm 10^3 10^4 10^5 10^6 10^7 10^8 ------------------------------------------------------------------ C-Sieve 0.00 0.00 0.01 0.29 5.12 88.24 O'Neill (#2) 0.01 0.09 1.45 22.41 393.28 - O'Neill (#1) 0.01 0.14 2.93 47.08 - - Bromage 0.02 0.39 6.50 142.85 - - "sieve" (#3) 0.01 0.25 7.28 213.19 - - Naive 0.32 0.66 16.04 419.22 - - Runciman 0.02 0.74 29.25 - - - Reinke 0.04 1.21 41.00 - - - Zilibowitz 0.02 2.50 368.33 - - - Gale (#1) 0.12 17.99 - - - - "sieve" (#1) 0.16 32.59 - - - - "sieve" (#2) 0.01 32.76 - - - - Gale (#2) 1.36 268.65 - - - - ------------------------------------------------------------------
I ran a few of the tests myself on my Mac Mini G4 with 512 Mb ram. I compiled the programs with ghc 6.6. I got different results however. 10^3 10^4 10^5 Reinke 0.7251 1.751 1m0.310s Runciman 0.126 1.097 5m19.569s Zilibowitz 0.07 4.668 11m45.877s NaiveSeive 0.369 47.795 - The NaiveSeive program ran somewhat slower on my machine than it seemed to on yours. Also the Reinke program seemed to be faster than Runciman on my machine. It may be to do with not having enough ram. But I'm not too sure. Can you suggest any explanation for the different results? Ruben On 23/02/2007, at 4:46 PM, Melissa O'Neill wrote:
Ruben Zilibowitz wrote:
I see that there has been some discussion on the list about prime finding algorithms recently. I just wanted to contribute my own humble algorithm:
Thanks!
Comparing it to some of the algorithms in: http://www.haskell.org/pipermail/haskell-cafe/2007-February/ 022765.html
It seems to perform reasonably well. It also has the advantage of being quite short.
I've added it to my table. It's fun to find new ways to figure out primes, but I think the "shortness advantage" goes to the naive primes algorithm, which is faster and shorter.
Melissa.
------------------------------------------------------------------ Time (in seconds) for Number of Primes ---------------------------------------------------- Algorithm 10^3 10^4 10^5 10^6 10^7 10^8 ------------------------------------------------------------------ C-Sieve 0.00 0.00 0.01 0.29 5.12 88.24 O'Neill (#2) 0.01 0.09 1.45 22.41 393.28 - O'Neill (#1) 0.01 0.14 2.93 47.08 - - Bromage 0.02 0.39 6.50 142.85 - - "sieve" (#3) 0.01 0.25 7.28 213.19 - - Naive 0.32 0.66 16.04 419.22 - - Runciman 0.02 0.74 29.25 - - - Reinke 0.04 1.21 41.00 - - - Zilibowitz 0.02 2.50 368.33 - - - Gale (#1) 0.12 17.99 - - - - "sieve" (#1) 0.16 32.59 - - - - "sieve" (#2) 0.01 32.76 - - - - Gale (#2) 1.36 268.65 - - - - ------------------------------------------------------------------
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Ruben writes:
I ran a few of the tests myself on my Mac Mini G4 with 512 Mb ram. I compiled the programs with ghc 6.6. I got different results however.
I suspect that's due to inconsistent naming on my part, I think. The algorithm named "Naive" in my table is called SimplePrimes in the zip file, and the example named "sieve" in my table is called "NaivePrimes" in the zip file. Melissa.
*sigh* don't click send at 2:30am... I wrote:
The algorithm named "Naive" in my table is called SimplePrimes in the zip file, and the example named "sieve" in my table is called "NaivePrimes" in the zip file.
The algorithm named "Naive" in my table is called SimplePrimes in the zip file, and the example named "sieve" in my table is called "NaiveSieve" in the zip file. Melissa.
participants (3)
-
Melissa O'Neill -
Ruben Zilibowitz -
Stephen Forrest