The Bit Array Improvement in C

When it comes to memory usage, the quickest and most obvious improvement comes with the realization that each candidate number either is or is not prime, and that's all you need to know. It's binary. That means each candidate number could be represented by a single bit, instead of the 8 bit unsigned char used in the preceding article. Theoretically, this would allow an 8 fold increase in the range to be looked at.

To accomplish this we need to write put and get routines to map info into single bits of an array whose byte count is now topCandidate/8. The bit arithmetic inside those put and get routines will doubtlessly slow the algorithm. The question is, how much. The answer is simple enough -- it depends on how well you write them.

#include 
#include 
#include 
#include 

typedef  unsigned long long bignum;

typedef struct
{
unsigned int *p;  /* pointer to array */
int bitsPerByte;  /* 8 on normal systems */
int bytesPerInt;  /* sizeof(unsigned int) */
int bitsPerInt;   /* for bit arithmetic */
bignum bitsInArray;  /* how many bits in array */
bignum intsInArray;  /* how many uints to give necessary bits */
} BITARRAY;

void freeBitArray(BITARRAY *ba)
{
free(ba->p);
free(ba);
}

BITARRAY * createBitArray(bignum bits)
{
BITARRAY *ba = malloc(sizeof(BITARRAY));
assert(ba != NULL);
ba->bitsPerByte = 8;
ba->bytesPerInt = sizeof(unsigned int);
ba->bitsPerInt = ba->bitsPerByte * ba->bytesPerInt;
ba->bytesPerInt = sizeof(unsigned int);
ba->bitsInArray = bits;
ba->intsInArray = bits/ba->bitsPerInt + 1;
ba->p = malloc(ba->intsInArray * ba->bytesPerInt);
assert(ba->p != NULL);
return ba;
}

void setBit(BITARRAY *ba, bignum bitSS)
{
unsigned int *pInt = ba->p + (bitSS/ba->bitsPerInt);
unsigned int remainder = (bitSS % ba->bitsPerInt);
*pInt |= (1 << pint =" ba-">p + (bitSS/ba->bitsPerInt);
unsigned int remainder = (bitSS % ba->bitsPerInt);
unsigned int mask = 1 << mask =" ~mask;" pint =" ba-">p + (bitSS/ba->bitsPerInt);
unsigned int remainder = (bitSS % ba->bitsPerInt);
unsigned int ret = *pInt;
ret &= (1 << intss="0;">intsInArray; intSS++)
 {
 *(ba->p + intSS) = 0;
 }
}

void setAll(BITARRAY *ba)
{
bignum intSS;
for(intSS=0; intSS <= ba->intsInArray; intSS++)
 {
 *(ba->p + intSS) = ~0;
 }
}

void printPrime(bignum bn)
{
static char buf[1000];

sprintf(buf, "%ull", bn);
buf[strlen(buf) - 2] = '\0';
printf("%s\n", buf);
}

void findPrimes(bignum topCandidate)
{
BITARRAY *ba = createBitArray(topCandidate);
assert(ba != NULL);

/* SET ALL BUT 0 AND 1 TO PRIME STATUS */
setAll(ba);
clearBit(ba, 0);
clearBit(ba, 1);

/* MARK ALL THE NON-PRIMES */
bignum thisFactor = 2;
bignum lastSquare = 0;
bignum thisSquare = 0;
while(thisFactor * thisFactor <= topCandidate)  
{   /* MARK THE MULTIPLES OF THIS FACTOR */  
bignum mark = thisFactor + thisFactor;  
while(mark <= topCandidate)   
{   
clearBit(ba, mark);    mark += thisFactor;   
}   
/* PRINT THE PROVEN PRIMES SO FAR */  
thisSquare = thisFactor * thisFactor;  
for(;lastSquare < ba =" createBitArray(77);
" ss="0;">p));
}

int main(int argc, char *argv[])
{
bignum topCandidate = 1000;
if(argc > 1)
 topCandidate = atoll(argv[1]);
/* test();  */
findPrimes(topCandidate);
return 0;
}

Related Links :