Re: Sieve of Erastosthenes optimized to the max

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?