[Performance] Beat the pants off of my best time

[zylum]

gcc p.c -O -Wl,--stack,150000000 -o p

The -Wl,--stack,150000000 changes the stack size to 150MB.

[Brightguy]

Eratosthenes with a twist. It has not been optimized, except for tight bit packing. Did the first billion primes in just under a minute on my Eee PC.

c:

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> int main(int argc, char* argv[]) {   time_t timer = time(NULL);         int i,j,np=0,n=atoi(argv[1]);     char* p = (char*)malloc((n>>3)+1);     if(p==NULL)         exit(1);     memset(p,255,(n>>3)+1);     for(i=2;i*i<=n;i++)         if(p[i>>3]&(1<<(i&7)))             for(j=n/i;j>=i;j--)                 if(p[j>>3]&(1<<(j&7)))                     p[(i*j)>>3]&=~(1<<((i*j)&7));     /*for(i=2; i<=n; i++)         if(p[i>>3]&(1<<(i&7)))         {   printf("%u\n", i);             np++;         }     printf("%u/%u primes\n", np, n);*/     printf("%u seconds\n", time(NULL) - timer);     free(p);     return 0; }

[wtd]

While I do not have a proper environment to test this in optimized form, I ran a naive Sieve of Erastothenes through the O'Caml top-level.

code:

# let t = Sys.time ()   and a = Array.make 2_097_151 true in       for i = 1 to Array.length a - 1 do           if a.(i) then               for j = 2 to Array.length a / (i + 1) do                   a.(j * (i + 1) - 1) <- false               done       done;       Printf.printf "%f\n" (Sys.time () -. t);; 3.875000 - : unit = () #

[zylum]

Brightguy, pretty much what I did but I used ints instead of chars XD

[wtd]

code:

chris@frankenstein:~/Documents$ cat primes.ml let t = Sys.time ()   and a = Array.make 2_097_151 true in       for i = 1 to Array.length a - 1 do           if a.(i) then               for j = 2 to Array.length a / (i + 1) do                   a.(j * (i + 1) - 1) <- false               done       done;       Printf.printf "%f\n" (Sys.time () -. t);; chris@frankenstein:~/Documents$ ocamlopt primes.ml -o primes chris@frankenstein:~/Documents$ ./primes 0.536032 chris@frankenstein:~/Documents$

[wtd]

code:

chris@frankenstein:~/Documents$ cat primes2.sml structure ArrayUtils = struct     fun fromToByDo(array, startIndex, endIndex, incrementBy, func) =         if startIndex <= endIndex then            ( func(array, startIndex, Array.sub(array, startIndex));              fromToByDo(array, startIndex + incrementBy, endIndex, incrementBy, func) )         else () end; let     val t = Time.now()     val a = Array.array(2097151, true) in     Array.update(a, 0, false);     Array.appi(fn (i, x) =>         if x then             let                 val number = i + 1             in                 ArrayUtils.fromToByDo(a, number * 2 - 1, Array.length a - 1, number,                                       fn (a, i, _) => Array.update(a, i, false))             end         else ()) a;     let         val t' = Time.now()         val diff = Time.-(t', t)     in         print ((IntInf.toString(Time.toMilliseconds diff)) ^ "\n")      end end; chris@frankenstein:~/Documents$ mlton -output sml_primes2 primes2.sml chris@frankenstein:~/Documents$ ./sml_primes2 584 chris@frankenstein:~/Documents$ ./sml_primes2 584 chris@frankenstein:~/Documents$ ./sml_primes2 584 chris@frankenstein:~/Documents$

[TheFerret]

Ok, I found another way of doing this, the sieve of Atkins, so here is a solution for that, http://ferret22ca.googlepages.com/soln2.txt

You need to use the same mem flag as for the first one and this one runs about 3 seconds faster than the first one...

[andrew.]

Here's mine:

Turing:

var n : int put "Enter a number." get n for i : 1..n put i end for

Sorry, just had to . Turing is so lame.

[gitoxa]

andrew. @ Thu Aug 07, 2008 10:41 am wrote:

Sorry, just had to . Turing is so lame.

That doesn't even work...

[andrew.]

My bad, didn't read the part about the prime numbers. Hmm...that is a hard task to do....