Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: Sieve of Erastosthenes optimized to the max
Date: Sat, 20 Jul 2024 07:41:18 -0700
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <861q3o5do1.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <umgbci$3qpao$1@raubtier-asyl.eternal-september.org> <utlf3h$393l6$1@dont-email.me> <utn1fp$3oeks$2@raubtier-asyl.eternal-september.org> <utng4n$3rn1f$2@dont-email.me> <utoh9d$6lrr$1@raubtier-asyl.eternal-september.org> <utq0ag$hvrl$3@dont-email.me> <utq0os$ibqn$1@raubtier-asyl.eternal-september.org> <utq11p$icmm$1@dont-email.me> <v25c87$1ld9m$1@dont-email.me> <86r0duwqgg.fsf@linuxsc.com> <v39o3l$1lvju$1@dont-email.me> <86o78mpnlf.fsf@linuxsc.com> <v3fv2u$2ursd$1@dont-email.me> <86ttibod7n.fsf@linuxsc.com> <86h6eaoi2r.fsf@linuxsc.com> <v4sool$1grge$1@dont-email.me> <867celixcw.fsf@linuxsc.com> <v5sg9s$mat4$1@dont-email.me> <86zfr0b9hw.fsf@linuxsc.com> <v638ud$25623$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 20 Jul 2024 16:41:19 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ec269dcb7a3ff6bcf4ae70bc0b859489";
	logging-data="3747114"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+s59wDri+vb6r7KfTtWxVjv8eVqKdebEE="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:8cKbooshMyjfxGRiwZ4tFu47Wm4=
	sha1:0RPGoyuEsNSdnpEfr0ut/OAMtlw=
Bytes: 3479

Vir Campestris <vir.campestris@invalid.invalid> writes:

> On 02/07/2024 07:20, Tim Rentsch wrote:
>
>> I got the code.  [...]
>>
>
> I checked.  The modulus operations (%) are easy to check for.
>
> There are two for each prime number.  Not for each multiple of it, but
> for the primes themselves.
>
> And there's one in the "get" function that checks to see if a number
> is prime.  [...]

And one divide for each modulus.

Both divide and mod can be simplified if we use a different
representation for numbers.  The idea is to separate the
number into a mod 30 part and divided by 30 part.  An
arbitrary number N can be split into an ordered pair

   N/30 , N%30

stored in, let's say, an 8 byte quantity with seven bytes
for N/30 and one byte for N%30.  Let me call these two
parts i and a for one number N, and j and b for a second
number M.  Then two form N*M we need to find

   (i*30+a) * (j*30+b)

which is

   (i*30*j*30) + (i*30*b) + (j*30*a) + a*b

Of course we want to take the product and express it in
the form (product/30, product%30), which can be done by

   30*i*j + i*b + j*a + (a*b)/30,   (a*b)%30

The two numbers a and b are both under 30, so a*b/30 and
a*b%30 can be done by lookup in a small array.

   30*i*j + i*b + j*a + divide_30[a][b],   modulo_30[a][b]

Now all operations can be done using just multiplies and
table lookups.  Dividing by 30 is just taking the first
component;  remainder 30 is just taking the second component.

One further refinement:  for numbers relatively prime to 2,
3, and 5, there are only 8 possibles, so the modulo 30
component can be reduced to just three bits.  That makes the
tables smaller, at a cost of needing a table lookup to find
and 'a' or 'b' part.

Does this all make sense?