OT: Re: Sieve of Erastosthenes optimized to the max

On 23/07/2024 15:34, Tim Rentsch wrote:
 > Vir Campestris <vir.campestris@invalid.invalid> writes:
 >
 > [...]
 >
 > I was hoping for some feedback, even if very brief,
 > before I continue.
Sorry, I was slow. It's really odd, I'm retired, and I ought to have lots of time for things like this... and yet I seem to be busy all the time.
On 20/07/2024 15:41, Tim Rentsch wrote:

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.

I found searching my code for the '%' character was quite easy.
'/', however, is in all my comments, so I get lots of false positives.

 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 suspect the cost of extracting the divided value from the 7 bytes will be prohibitive. You may find it's best to have one table for the N/30 parts (big entries, word aligned) and another for the N%30 part (small entries, byte aligned). BICBW.

    (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?

Yes, it does. It's not a direction I was thinking of at all, although I too had table lookups in mind.
What I had considered is an extrapolation from my original code.
For each prime my original code  starts with p^2, and sets the bit. It than adds p*2, and sets the bit for that. Since I wasn't storing even numbers every prime is odd, which means p^2 is odd. p^2+p would be even, so I skip that and go on to p^2+p*2, and so on.
Given the mod30 storage I should be able to make a table with 8 entries, each containing a step and a mask. The step is the number of bytes in the big table to step to for the next bit to set; the mask is the bit to set.
For 37, for example, the first bits we need to set are these:
Mul'ple value /30 Step %30
37 1369 45 19
41 1517 50 5 17
47 1739 57 7 29
49 1813 60 3 13
53 1961 65 5 11
59 2183 72 7 23
61 2257 75 3 7
67 2479 82 7 19
71 2627 87 5 17
77 2849 94 7 29
79 2923 97 3 13
83 3071 102 5 11
89 3293 109 7 23
91 3367 112 3 7
You'll see the pattern; there is a repeat 8 lines long of both the Step (which is the delta in the word we need to access) and the %30 value.
So what the code should do is start at p^2, and build this table. It'll be different for every prime, and will be quite expensive to build. But once the table is built it can add the step onto the current table index, then set the bit corresponding to the %30 value. The table should of course contain only the step and the bitmask corresponding to the %30 value.
(I used 37 in this example BTW, because I wanted a value more than 30, and with 31 the /30 column increments by 1 each time I added a prime)
For small values, as we discussed, it's going to be faster to copy the small table for that prime than to apply the mask to each word of the store individually.
I had also considered looking for a mod-div value greater than 30.
Bonita's original code stored a bit for every prime. We can call that a compression ratio of 1. I store the odd only, so the compression ratio is 2. By storing mod30 you increase that to 3.75. But there's a cost on modern computers because it implies lots of byte level access to store.
If on the other hand we store mod(2*3*5*7*11), which is 2310, we get 480 candidates. 480 isn't far off 512 which is a nice size for us to handle, and gives us an even better compression ratio of just over 4.5. But of course all those tables with 8 or 30 entries will be getting a bit big and painful.
I might even get around to writing some of it. Be warned, this is a time trap!
Andy