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

On 20/08/2024 16:24, Bonita Montero wrote:

Am 20.08.2024 um 17:21 schrieb Bonita Montero:

Am 19.08.2024 um 22:23 schrieb Vir Campestris:

On 16/08/2024 18:35, Bonita Montero wrote:
<snip>

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.
>

It's not just storage you save, it's also computation.
>
That program I published up-thread is almost as fast as yours - within 10% of the elapsed time - while only using a single core. The amount of CPU used is much lower.
>
Andy

>
On my AMD 7990X all primes up to 2 ^ 32 are calculated with my code
with a 65W-setting of the CPU in 0.168s. The total CPU-time is 3.688s.
With your code all primes up to 2 ^ 32 take nearly exactly four seconds
with a single thread. So the overall computation time with my algorithm
is about seconds less.

 And if I run my code with a single core:
      C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 0x100000000 "" 1
     real   1.795s
     user   1.766s
     sys    0.000s
     cylces 8.011.804.500
 Thats less than half the computation time.

That's really odd. I too have an AMD - although my AMD Ryzen 5 3400G is chosen for low power, not speed. Surely it can't be because I use Linux, not Windows?
I'm leaning towards thinking you may have a point on the mod30 code. There are more operations on the innermost loop with mod30, although the loop goes around fewer times. It also means that the store is forced to be byte wide - I find that my original odd-only code is significantly faster - about 30% - when the store is 64 bit wide rather than byte.
Speed of writing the primes out? I don't care. The only reason I put it in there was to allow me to check the output. If I did care I'd be putting a more efficient enumeration function too.
Andy