×

zbMATH — the first resource for mathematics

Cache optimized linear sieve. (English) Zbl 1298.11115
Summary: Sieving is essential in different number theoretical algorithms. Sieving with large primes violates locality of memory access, thus degrading performance. Our suggestion on how to tackle this problem is to use cyclic data structures in combination with in-place bucket-sort.
We present our results on the implementation of the sieve of Eratosthenes, using these ideas, which show that this approach is more robust and less affected by slow memory.
MSC:
11Y11 Primality
68W30 Symbolic computation and algebraic computation
11A41 Primes
11-04 Software, source code, etc. for problems pertaining to number theory
PDF BibTeX XML Cite