Re: Primes | A Software Drag Race - Dave's Garage
- Posted by petelomax Jul 16, 2021
- 957 views
I've had another idea, or rather extended one I had above. Instead of setting every third bit I initialised 24 bits aka 3 bytes and replicated that. The 24 is lcm(3,8), though since we are dealing with primes we can just multiply them and since we are dealing with bytes we can just forget the 8. We could do much the same for 5: initialise lcm(5,24) = 120 bits or 15 bytes and replicate that. Likewise lcm(7,120) = 840 bits or 105 bytes. As we extend by another (p-1) blocks we can copy the prior bits, setting any new bits as we go. So the early passes for small primes can terminate early and rely on higher primes to replicate their bit pattern. Obviously the main loop guarantees the sieve always gets properly filled all the way to the end.
As ever there is a catch or in this case two. First, you need a pristine (copy of) earlier bytes and I suggest you can do that best by setting, for eg multiples of 5, bytes 4..15 first and only then bytes 1..3. Second, for the small primes {3,5,7,11,13} (or do I mean just {3,5,7}?) you will never skip a byte but you may set >1 bit in the same byte, and you need to avoid re-fetching the pristine byte when you do so, whereas when setting multiples of 17 and up you may skip bytes but will never touch the same byte twice, so for that I suggest breaking the main loop into two phases, one for <=13 and one for >=17. (erm, it might be <=7 and >=11 since we're doing odd-bits only)
It would greatly surprise me if non-one else has ever had the same idea on such an age-old task, or maybe it is just a subtly different way to implement a 3-5-7 wheel.
UPDATE: Doh. The pristine/replicate bytes want bits 3,5,7 etc set whereas the final result obviously does not. So it would need to be kept separately and beyond a certain size the overhead of updating two copies would start to outweigh any possible savings... Then again, looking at the numbers:
1 * 3 = 3 3 * 5 = 15 15 * 7 = 105 105 * 11 = 1,155 1155 * 13 = 15,015 15015 * 17 = 255,255 255255 * 19 = 4,849,845 4849845 * 23 = 111,546,435 111546435 * 29 = 3,234,846,615 3234846615 * 31 = 100,280,245,065A 1-million sieve would easily be filled on the 6th pass (the length of res for 1,000,000 is 62,500), after/during which we can leave any such copy well alone.
In the critical timed case the size of the copy need not exceed 25% of the result, and in fact "pristine pristine" could theoretically fit in just two bytes[??].
