[Haskell-cafe] Prime finding

[Ruben Zilibowitz]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe