I have taken the classic Sieve of Erotastanese and implemented it as a true boolean array (every bit is utilized as a seperate bool variable). After I fininshed it took about 40 seconds to run through the first 8,000,000 numbers. I took it opon myself to make this an exercise in optimazation. Did I optimize this correctly? Did I leave anything out. One other thing, is it quicker to say 2*8 or 2<<3?

  
#include <iostream.h>

typedef unsigned char BYTE;

int main()
{
  const int MAX=1000000;
  BYTE p[MAX];
  long int x,y;
  for(x=0;x<MAX;x++) p[x]=255;//Init boolean array to all 1''s


  //This is the main loop, it sets up the boolean array by

  //using a nested loop to set all possible composites to ''0''

  for(x=2;x<=MAX*4;x++)
    for(y=x;y<=MAX*8/x;y++)
      p[x*y/8]=(p[x*y/8]|(1<<(x*y%8))) ^ (1<<(x*y%8));
      //This is p[BYTE # x*y/8, BIT # x*y%8] = 0;

      //This works because after all values of x * y

      //The only bits left as 1, have prime indexes

      //because a prime can''t be written as x*y

  
  //Output primes

  for(x=2;x<MAX*8;x++)
    if(p[x/8]&(1<<(x%8)))
      cout << x << " ";
  return 0;
}

/*
This is the old main loop

for(x=2;x<=MAX*4;x++)
  for(y=x;y<=MAX*8/x;y++)
  {
    bit=pow(1,x*y%8);
    p[x*y/8]|=bit;
    p[x*y/8]^=bit;
  }
*/
  

I will clarify any part of the code if needed...

Any modern compiler will change x * 8 into x << 3 for you.
Also one optimization you missed is only going through the y loop on prime x. No point in marking out all multiples of 4, when you got them all on 2.

Do what SiCrane said first, it'll make the biggest difference.

Will the compiler replace MAX*4, MAX*8 with literals? (in release for speed?) I would expect it to...

  //use memset(p, 0xFF, MAX); //this is *one* op code (well thats not true, but the first few only execute once)/instead of for(x=0;x<MAX;x++) p[x]=255; //this is several, executed over&over again//unwind these loopsfor(x=2;x<=MAX*4;x++)//make em like so... it reduces the loop overhead slightlyfor(x=2;x<MAX*4;x++)//...loopXif(x=MAX*4)//...loopX//ok this is an opt the compiler can't do for you (not MSVC anyway, borland might)for(y=x;y<=MAX*8/x;y++)//change toint MaxY = MAX*8/x;for(y=x;y<MaxY;y++)//...loopYif(y=MaxY)//...loopY//Only do the x*y once each loopp[x*y/8]=(p[x*y/8]|(1<<(x*y%8))) ^ (1<<(x*y%8));int xy = x*y;int xydiv8 = xy>>3;int xymod8 = xy%8;p[xydiv8]=(p[xydiv8]|(1<<(xymod8))) ^ (1<<(xymod8));//is (1<<(xymod8)); always a power of 2?//seems like you should be able to reduce the ^ somehow... nothing comes to me though...  

you may want to consider asm...
How long do you think it'd take to find the primes in the first 3.4028236692093846346337460743177e+38 integers?

Cracking RC5 might be a bit easier with all the primes sitting & waiting...

Edited by - Magmai Kai Holmlor on December 5, 2000 1:40:14 AM

one quick optimzing tip,

for stuff like

for ( x=0; x
use
for x=LIMIT-1; x ; x-- )

it will save the compiler one register and you''ll save the
testing sequence x
Hmm, well that is all for now...

"Optimzation is the root to all evil"

quote: Original post by Magmai Kai Holmlor
Will the compiler replace MAX*4, MAX*8 with literals? (in release for speed?) I would expect it to...

The compiler should constant fold those out.

quote:
memset(p, 0xFF, MAX); //this is *one* op code (well thats not true, but the first few only execute once)

In order for that to be true, you need to tell the compiler to inline intrinsics. Otherwise you''ll be doing a function call.

quote:
you may want to consider asm...
How long do you think it''d take to find the primes in the first 3.4028236692093846346337460743177e+38 integers?

Cracking RC5 might be a bit easier with all the primes sitting & waiting...

RC5 does not use prime numbers in it''s encryption/decryption. The only "interesting" numbers involved are e, the base of the natural logarithm, and phi, the golden ratio.