Re: OT: Re: Sieve of Erastosthenes optimized to the max

Am 16.08.2024 um 17:40 schrieb Tim Rentsch:

     bytes[0] = 1;
     for(  i = 0;  i < i_limit;  i++  ){
Bits cbits = bytes[i];
Bits pbits = cbits ^ -1;
if(  pbits & 0001  )  remove_multiples_x( N, i,  1, pbits );
if(  pbits & 0002  )  remove_multiples_x( N, i,  7, pbits );
if(  pbits & 0004  )  remove_multiples_x( N, i, 11, pbits );
if(  pbits & 0010  )  remove_multiples_x( N, i, 13, pbits );
if(  pbits & 0020  )  remove_multiples_x( N, i, 17, pbits );
if(  pbits & 0040  )  remove_multiples_x( N, i, 19, pbits );
if(  pbits & 0100  )  remove_multiples_x( N, i, 23, pbits );
if(  pbits & 0200  )  remove_multiples_x( N, i, 29, pbits );
     }
}

use a countr_zero() with a following switch-statement and make the
default std::unreachable() (C++23). Then everything is only a table
lookup. With your code you've got a lot of bad predictible branches.
But basically I don't think it is a good idea to skip numbers exept
multiples of two. With the three you save a sixth of memory, with
the five you save a 15-th and at the end you get about 20% less
storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
for a lot of computation. That's the point where I dropped this
idea and I think this extra computation is higher than the time
for the saved memory loads.