edit: found the problem.
Since I had nothing better to do, I thought I'd play around with some prime numbers, but there's a problem...
It gives me 3, 5, 7 and 11 just fine, then it skips 13 and 17, after which things get really funny. of course there is a mistake somewhere, but I can't find it and would like some help.
Code:
#include <stdint.h>
#include <stdio.h>
// For convinience, the width of the desired type.
#define WORD_BITS ( 8 * sizeof( uint_fast8_t ) )
// array size.
#define ARRAY_SIZE ( 0x10000000 / sizeof( uint_fast8_t ) )
// number of bits in the bitset.
#define ARRAY_SIZE_BITS ( 0x80000000 )
// allocate 2^31 bits of memory, to represent all uneven numbers from
// 0 -> 2^32-1
static uint_fast8_t b[ ARRAY_SIZE ];
// should be selfexplanatory. Flip bits, and and assign.
static inline void resetBit( uint_fast32_t idx )
{
b[ idx / WORD_BITS ] &= ~(1 << ( idx % WORD_BITS ) );
}
// This is a bit more complicated, as I don't really need to return 0 or 1,
// but will be parfectly happy with 0 and non-0. Thus there are two ways:
// (x>>n)&1 or x & (1 << n) and I would very much like to know which is more
// efficient.
static inline uint_fast8_t getBit( uint_fast32_t idx )
{
return ( 1 & ( b[ idx / WORD_BITS ] >> ( idx % WORD_BITS ) ) );
}
// Should initialize it all, but there are issues.
void initialize()
{
// set all bits to 1.
for( uint_fast32_t n = 0; n < ARRAY_SIZE; n++ )
b[ n ] = UINT_FAST8_MAX;
uint_fast32_t p;
// loop through all numbers from 0 -> 2^16.
for( uint_fast32_t n = 0; n < 0x8000; n++ )
{
// If prime...
if( getBit( n ) )
{
// calculate the actual value
p = 2 * n + 3;
printf("%d\n", p); //for testing purposes.
// loop through the bitset and reset required bits.
// found the flaw: uint_fast32_t i = p -> uint_fast32_t i = p + n
for( uint_fast32_t i = p + n; i < ARRAY_SIZE_BITS; i += p )
{
resetBit( i );
}
}
}
}
Important notes is that I completely disregard even numbers, and strive for the minimum amount of time to initialize b[], not usability.
other than that, apart from the fact that it does not work, I'm actually quite pleased with my self.
Any help is most welcome.
Best regards.
edit: found the flaw. missed +n at a rather crucial point.