Re: As the Crow flies.

On 2008-10-20, Garamond Lethe <cartographical@xxxxxxxxx> wrote:
On Oct 19, 10:04?pm, Mark VandeWettering <wetter...@xxxxxxxxxxx>
wrote:
On 2008-10-20, spintronic <spintro...@xxxxxxxxxxx> wrote:



On 20 Oct, 01:00, Mark VandeWettering <wetter...@xxxxxxxxxxx> wrote:
On 2008-10-19, spintronic <spintro...@xxxxxxxxxxx> wrote:

On 19 Oct, 14:30, r norman <r_s_norman@xxxxxxxxxxxx> wrote:

On Tue, 14 Oct 2008 12:29:25 -0700 (PDT), Garamond Lethe
Incidentally, my own all-too-clever algorithm thought up in the shower
produces correct values, but takes 8 seconds for N = 1,000,000 so it
is a real loser

Incidentally, my gift also takes 8 seconds, to calculate pi(1000000).

But after all, it is printing 78,498 primes to screen, and working
the
value
of each one individually.

My code on my macbook does that in about 117ms (printing to a file).
Takes about 1.8s to do it to the screen.

Not bad for a (supposed bafoon, eh?)

There is no such word as "bafoon".

? ? ? ? Mark

either upload the exe like I did, or upload the code here.

Almost any sieve would do. ?This one is really silly, and uses functions
to set bits in the flag array. ?It uses 64 bit ints for no real
particular reason (32 bit ints would work just as well). ?It was simply
trimmed down from a more complex program I had on time, and it seemed
convenient to modify it rather than starting from scratch. ?It isn't
particularly hard to write a sieve which is quite a bit faster. ?For
example, you could just avoid doing anything with the multiples of
two and you'd almost double the speed of the sieve. ?Adding "inline"
declarations for the bit manipulation functions trims about 30% from the
runtime. ?On my macbook, I get the following.

% time ./sieve 1000000 > /dev/null
counting primes < 1000000
78498 primes less than 1000000

real ? ?0m0.090s
user ? ?0m0.064s
sys ? ? 0m0.004s

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

void
set(uint64_t *a, uint64_t n)
{
? ? uint64_t nd = n >> 6 ;
? ? uint64_t nr = n & 63 ;
? ? a[nd] |= (1LL << nr) ;

}

void
clr(uint64_t *a, uint64_t n)
{
? ? uint64_t nd = n >> 6 ;
? ? uint64_t nr = n & 63 ;
? ? a[nd] &= ~(1LL << nr) ;

}

void
flip(uint64_t *a, uint64_t n)
{
? ? uint64_t nd = n >> 6 ;
? ? uint64_t nr = n & 63 ;
? ? a[nd] ^= (1LL << nr) ;

}

uint64_t
bit(uint64_t *a, uint64_t n)
{
? ? uint64_t nd = n >> 6 ;
? ? uint64_t nr = n & 63 ;
? ? return a[nd] & (1LL << nr) ;

}

int
popcount(uint64_t t)
{
? ? int cnt = 0;
? ? while (t) {
? ? ? ? cnt ++ ;
? ? ? ? t = t & (t-1) ;
? ? }
? ? return cnt ;

}

main(int argc, char *argv[])
{
? ? uint64_t *ip ;
? ? uint64_t limit = atol(argv[1]) ;
? ? uint64_t sqlimit = (uint64_t) sqrt((double) limit) ;
? ? uint64_t i, j, cnt ;

? ? fprintf(stderr, "counting primes < %lld\n", limit) ;

? ? ip = (uint64_t *) calloc((limit + 63) / 64, sizeof(uint64_t)) ;

? ? set(ip, 0) ;
? ? set(ip, 1) ;
? ? for (i=2; i<= sqlimit; i++) {
? ? ? ? if (bit(ip, i) == 0) {
? ? ? ? ? ? j = i + i ;
? ? ? ? ? ? while (j < limit) {
? ? ? ? ? ? ? ? set(ip, j) ;
? ? ? ? ? ? ? ? j += i ;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? cnt = 0 ;
? ? for (i=2; i<limit; i++)
? ? ? ? if (bit(ip, i) == 0) {
? ? ? ? ? ? ? ? printf("%d\n", i) ;
? ? ? ? ? ? ? ? cnt ++ ;
? ? ? ? }
? ? fprintf(stderr, "%lld primes less than %lld\n", cnt, limit) ;

}

From the nit list:

-@sleipnir:~$ gcc -O3 -Wall -o mark mark.c -lm
mark.c:50: warning: return type defaults to ?int?
mark.c: In function ?main?:
mark.c:56: warning: format ?%lld? expects type ?long long int?, but
argument 3 has type ?uint64_t?
mark.c:74: warning: format ?%d? expects type ?int?, but argument 2 has
type ?uint64_t?
mark.c:77: warning: format ?%lld? expects type ?long long int?, but
argument 3 has type ?uint64_t?
mark.c:77: warning: format ?%lld? expects type ?long long int?, but
argument 4 has type ?uint64_t?
mark.c:78: warning: control reaches end of non-void function

Segfaults when no parameters are given.

I must admit that I don't completely understand the right way to code
printf formats that are truly portable. Yep, it does segfault on no
args. If it hurts when you do that, don't do that. :-) Or, fix it
yourself. You have source.

Aside from that, you have the fastest one posted so far.

-@sleipnir:~$ /usr/bin/time ./mark 1000000000 > /dev/null
counting primes < 1000000000
50847534 primes less than 1000000000
Command exited with non-zero status 37
35.30user 0.11system 0:35.41elapsed 99%CPU (0avgtext+0avgdata
0maxresident)k
0inputs+0outputs (0major+30689minor)pagefaults 0swaps

-@sleipnir:~$ /usr/bin/time ./mark 10000000000 > /dev/null
counting primes < 10000000000
455052511 primes less than 10000000000
Command exited with non-zero status 39
381.74user 0.79system 6:22.52elapsed 100%CPU (0avgtext+0avgdata
0maxresident)k
0inputs+0outputs (0major+305350minor)pagefaults 0swaps

Getting rid of the printf statement that prints out individual primes
takes you down to 25.78 in the first case.

1,000,000 (sans printf) runs too fast to be registered by /usr/bin/
time.

The wikipedia article on stdint.h may be useful to those trying to
compile this using Visual Studio.

It's actually not hard at all to double the speed (or nearly double) of
this sieve. Half the time is spent crossing out all the even primes.
So, don't bother doing them. Where you strike out prime multiples
of p, don't increment by p, increment by 2*p. This will generate all
odd multiples of p, avoiding all the wasteful even ones. Then, when
counting and printing, just don't bother with the even numbers at all.
If you are really clever, you can extend this idea to avoid multiples of
2, 3, and 5, which net you about a factor six increase in speed. Even
more clever, you use something like the Sieve of Atkin. Even more clever,
you start working on paging behavior, and sieve in pieces.

None of these really approach the best known results for computing pi(x),
but they are a heck of a lot easier to understand.

Mark

.

Relevant Pages

  • Re: Prime number algorithm in C
    ... Here is a sieve that computes the first ULONG_MAX primes or until it runs out ... static void *heap{ ... static int decrement{ ...
    (comp.programming)
  • Re: Beginner Projects
    ... 1998-11-10 Calculate primes using Eratostheses Sieve. ... @param candidate number you want to find a prime near. ... public int above ...
    (comp.lang.java.help)
  • Re: As the Crow flies.
    ... counting primes < 1000000 ... real    0m0.090s ... mark.c:50: warning: return type defaults to ?int? ...
    (talk.origins)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slower with larger sieve sizes due to the large number of memory accesses. ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slows down based on size memory used ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
Loading