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

Liste des GroupesRevenir à cl c++ 
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 : 02. Sep 2024, 04:40:59
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <86tteyrad0.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 27/08/2024 05:09, Bonita Montero wrote:
>
Am 26.08.2024 um 21:08 schrieb Tim Rentsch:
>
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.
>
You don't need to hold all primes in memory.  Just calculate the primes
up to the square root and then you can calculate every segment up to
the maximum from that.

This is a brainless statement (and incidentally illustrates why I
was motivated not to read postings from BM).  In fact no primes need
be pre-calculated to determine whether any given number is prime.
The point of using a sieve is the sieve method is much faster than
not using one.  For example, suppose we want to determine all primes
less than a trillion.  Taking the approach of pre-computing only
those primes less than a million (the square root) and then testing
numbers individually takes more than 100 times as many operations as
using a sieve.  Furthermore the operations used are more expensive
for the non-sieve approach - simply setting a bit in the case of a
sieve, versus computing a remainder in the non-sieve case.

So you compute all the primes up to the square root of a larger number.
>
I was cleaning up my odds-only code with a view to posting it, when I
had an idea.
>
Take 101 (because I can write things more easily).
>
I want to mark
>
10201,10302,10403,10504,10605,10706...
>
With odds only that becomes
10201,10403,10605,10807,11009,11211...

Right.  Marking of multiples needs to start only at p*p, not
at p+2.

and as the loop increment is a constant it is nice and fast.  With
mod30 it isn't a constant, and it hurts to work out the increment.
>
Except...
>
If I mark 10201,13231,16261,19291,22321
with an increment of 30*p,
>
then go back to 10201, add 2p, then increment that by 30
10201 13231 16261
and do that for the other 6 of the 8, my inner loop has a constant
increment, and my code is compatible with the mod30 store.

Yes, reordering the loops this way might very well make things
work better.  It also has the property, I believe, that the
bit to set is the same in each of the eight outer loops, and
so can be computed only once for each of the eight outer loops.
Very good!

That might be quicker.  I also have some thoughts over storing the
prime as two parts.  It's 30m+r, where m is modulus and r remainder. r
maps one-for-one into the byte mask, and m is the index.

This is what I've been saying all along!

I'm going to waste lots more time on this I can see!

I'm interested to see what you come up with.

Date Sujet#  Auteur
30 Jun 24 * Re: Sieve of Erastosthenes optimized to the max54Vir Campestris
2 Jul 24 `* Re: Sieve of Erastosthenes optimized to the max53Tim Rentsch
2 Jul 24  +- Re: Sieve of Erastosthenes optimized to the max1Vir Campestris
3 Jul 24  `* Re: Sieve of Erastosthenes optimized to the max51Vir Campestris
15 Jul 24   +- Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
20 Jul 24   +* Re: Sieve of Erastosthenes optimized to the max48Tim Rentsch
25 Jul 24   i`* OT: Re: Sieve of Erastosthenes optimized to the max47Vir Campestris
10 Aug 24   i +* Re: OT: Re: Sieve of Erastosthenes optimized to the max44Tim Rentsch
12 Aug 24   i i+* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Vir Campestris
16 Aug 24   i ii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
15 Aug 24   i i`* Re: OT: Re: Sieve of Erastosthenes optimized to the max41Vir Campestris
16 Aug 24   i i `* Re: OT: Re: Sieve of Erastosthenes optimized to the max40Tim Rentsch
16 Aug 24   i i  +* Re: OT: Re: Sieve of Erastosthenes optimized to the max38Bonita Montero
16 Aug 24   i i  i+- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
19 Aug 24   i i  i+* Re: OT: Re: Sieve of Erastosthenes optimized to the max19Vir Campestris
20 Aug 24   i i  ii`* Re: OT: Re: Sieve of Erastosthenes optimized to the max18Bonita Montero
20 Aug 24   i i  ii `* Re: OT: Re: Sieve of Erastosthenes optimized to the max17Bonita Montero
20 Aug 24   i i  ii  +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
20 Aug 24   i i  ii  `* Re: OT: Re: Sieve of Erastosthenes optimized to the max15Vir Campestris
20 Aug 24   i i  ii   +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
26 Aug 24   i i  ii   `* Re: OT: Re: Sieve of Erastosthenes optimized to the max13Tim Rentsch
27 Aug 24   i i  ii    `* Re: OT: Re: Sieve of Erastosthenes optimized to the max12Bonita Montero
1 Sep 24   i i  ii     `* Re: OT: Re: Sieve of Erastosthenes optimized to the max11Vir Campestris
2 Sep 24   i i  ii      `* Re: OT: Re: Sieve of Erastosthenes optimized to the max10Tim Rentsch
2 Sep 24   i i  ii       +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
3 Sep 24   i i  ii       `* Re: OT: Re: Sieve of Erastosthenes optimized to the max8Vir Campestris
28 Sep 24   i i  ii        `* Re: OT: Re: Sieve of Erastosthenes optimized to the max7Tim Rentsch
28 Sep 24   i i  ii         `* Re: OT: Re: Sieve of Erastosthenes optimized to the max6Keith Thompson
2 Oct 24   i i  ii          `* Re: OT: Re: Sieve of Erastosthenes optimized to the max5Vir Campestris
2 Oct 24   i i  ii           +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
7 Oct 24   i i  ii           `* Re: OT: Re: Sieve of Erastosthenes optimized to the max3Tim Rentsch
20 Oct 24   i i  ii            `* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Vir Campestris
4 Nov 24   i i  ii             `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
19 Aug 24   i i  i+* Re: OT: Re: Sieve of Erastosthenes optimized to the max12Vir Campestris
20 Aug 24   i i  ii+* Re: OT: Re: Sieve of Erastosthenes optimized to the max4red floyd
20 Aug 24   i i  iii+* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Vir Campestris
26 Aug 24   i i  iiii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
26 Aug 24   i i  iii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
20 Aug 24   i i  ii+* Re: OT: Re: Sieve of Erastosthenes optimized to the max3Bonita Montero
20 Aug 24   i i  iii+- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
20 Aug 24   i i  iii`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Bonita Montero
20 Aug 24   i i  ii`* Re: OT: Re: Sieve of Erastosthenes optimized to the max4Bonita Montero
22 Aug 24   i i  ii `* Re: OT: Re: Sieve of Erastosthenes optimized to the max3Vir Campestris
22 Aug 24   i i  ii  `* Re: OT: Re: Sieve of Erastosthenes optimized to the max2Bonita Montero
22 Aug 24   i i  ii   `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Vir Campestris
22 Aug 24   i i  i`* Re: OT: Re: Sieve of Erastosthenes optimized to the max5Vir Campestris
23 Aug 24   i i  i +* Re: OT: Re: Sieve of Erastosthenes optimized to the max3red floyd
26 Aug 24   i i  i i+- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
28 Sep 24   i i  i i`- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Andrey Tarasevich
26 Aug 24   i i  i `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
19 Aug 24   i i  `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
11 Aug 24   i +- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
11 Aug 24   i `- Re: OT: Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch
23 Jul 24   `- Re: Sieve of Erastosthenes optimized to the max1Tim Rentsch

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal