On 15/07/07, Hugh Perkins
Hey, I just realized I can shave off another 30% in C# ;-)
So now the timings become:
Safe Haskell =========
J:\dev\haskell>ghc -O2 -o primechaddai.exe PrimeChaddai.hs
J:\dev\haskell>primechaddai number of primes: 664579 Elapsed time: 26.234
Unsafe Haskell ===========
J:\dev\haskell>ghc -fglasgow-exts -O2 -o PrimeDonald2.exe PrimeDonald2.hs
J:\dev\haskell>primedonald2 number of primes: 664579 Elapsed time: 0.7030000000000001
mono ====
J:\dev\test\testperf>erase primecs.exe & gmcs primecs.cs
J:\dev\test\testperf>mono primecs.exe number of primes: 664579 elapsed time: 0,453
Microsoft.Net ==========
J:\dev\test\testperf>erase primecs.exe & csc /nologo primecs.cs
J:\dev\test\testperf>primecs number of primes: 664579 elapsed time: 0,421875
Here's the fabulously complicated ;-) new C# algorithm:
public int CalculateNumberOfPrimes( int maxprime ) { bool[]IsNotPrime = new bool[ maxprime ]; int NumberOfPrimes = 1;
int squarecutoff = (Int32)Math.Sqrt( maxprime ) + 1; for( int i = 3; i < maxprime; i+= 2 ) { if( !IsNotPrime [i] ) { NumberOfPrimes++; if( i < squarecutoff ) { for( int j = ( i << 1 ); j < maxprime; j+= i ) { if( !IsNotPrime [j] ) IsNotPrime [ j] = true; } }
} } return NumberOfPrimes; }
(basically, we only cross off primes up to the square root of the size of the grid. I think this is a standard part of the standard Arostophenes grid algorithm, so like I say the C# version is seriously unoptimized ;-) )
I don't see what the point of this is? Why do timings of different algorithms? Of course you could do the same optimization in any language, so why do you think it's relevant to change the algorithm in *one* of the languages and then make comparisons? BTW, I think a better optimization is to start the inner loop at the square of the current prime, since any numbers smaller than that would've already been crossed off by the other prime factors (which must be smaller than the current prime). Nevertheless, there's no point doing optimizations to this unless you do them to all implementations! -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862