Timeline for Sieve of Eratosthenes - segmented to increase speed and range
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 24, 2019 at 13:35 | comment | added | DarthGizka | some chosen phase for blasting through the in-phase whole-phase part of a segment, with setup and finisher code to get the operation into phase before the main loop and then to finish off odds and ends after the main loop. Huuugely complicated. | |
| Dec 24, 2019 at 13:33 | comment | added | DarthGizka | Gnasher has hit the nail squarley on the head. A packed odds-only bitmap (a.k.a. mod-2 wheel) realises most of the potential of wheeled representation already, and most of the remaining potential can be realised via presieving and/or wheelish striding when reading out the numbers from the packed bitmap, all at virtually no cost. By contrast, the famous mod-30 wheel offers a further space reduction to a bit more than half but it makes the code hugely more complicated. If you were to drive it with lookup tables then you would lose speed, which means you have to use massively unrolled code at | |
| Dec 17, 2019 at 13:48 | comment | added | gnasher729 | Greg, I suggest you try it and come back with results. Good caching will massively improve speed, and obviously he is using a wheel { 2 } which gives most of the potential savings already. | |
| Oct 9, 2019 at 14:52 | history | answered | Greg Ames | CC BY-SA 4.0 |