Sujet : Re: OT: Re: Sieve of Erastosthenes optimized to the max
De : tr.17687 (at) *nospam* z991.linuxsc.com (Tim Rentsch)
Groupes : comp.lang.c++Date : 26. Aug 2024, 21:08:11
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <86v7zn3xwk.fsf@linuxsc.com>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
User-Agent : Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Vir Campestris <
vir.campestris@invalid.invalid> writes:
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. [...] I think this extra computation
is higher than the time for the saved memory loads.
[...]
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. [...]
One motivation for choosing a mod30 representation is being able to
compute more primes -- almost twice as many. Any machine with 64GB
of memory should be able to compute primes up to 1.5 trillion.
Even if an odds-only representation runs faster for more limited
sizes (and I'm not yet convinced that it does), it doesn't matter
if it's faster, because it doesn't do the job. I was computing all
32-bit primes 20 years ago, back when 32-bit machines were a thing.
The challenge for today's world is correspondingly higher.