[Haskell-cafe] In-place modification

[Sebastian Sylvan]

On 15/07/07, Hugh Perkins <hughperkins at gmail.com> wrote:
> 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