Anonymonk's implementation by an order of magnitude over oiskuu's:

C:\test\C>gcm
anonyM: gcm for s=2147483648 & r=1 to 1073741824 took: 33.607916866993
+ 
oiskuu: gcm for s=2147483648 & r=1 to 1073741824 took:329.551997991197
[download]

Thanks for the sanity check AnonyMonk!

And the difference between this benchmark and the previous (unbelievable) one? One keyword:

void main( int argc, char **argv ) {
    U64 s = argc > 1 ? _atoi64( argv[ 1 ] ) : 2*GB;
    U64 r, start, end;
    U64 volatile gsm;
//      ^^^^^^^^                                    *** Prevent the co
+mpiler from optimising the loop away in its entirety *** D'oh!

    start = __rdtsc();
    for( r = 1; r < ( s >> 1 ); ++r ) {
        gsm = gcm( s, r );
    }
    end = __rdtsc();
    printf( "anonyM: gcm for s=%I64u & r=1 to %I64u took:%.12f [%I64u]
+\n", s, s>>1, (double)( end - start ) / 2394046359.0 );

    start = __rdtsc();
    for( r = 1; r < ( s >> 1 ); ++r ) {
            gsm = s - ( s % lcm( r, 4096 ) );
    }
    end = __rdtsc();
    printf( "oiskuu: gcm for s=%I64u & r=1 to %I64u took:%.12f [%I64u]
+\n", s, s>>1, (double)( end - start ) / 2394046359.0 );

    return;
}
[download]