Skip to Main content Skip to Navigation
Conference papers

The I/O Complexity of Computing Prime Tables

Abstract : We revisit classical sieves for computing primes and analyze their performance in the external-memory model. Most prior sieves are analyzed in the RAM model, where the focus is on minimizing both the total number of operations and the size of the working set. The hope is that if the working set fits in RAM, then the sieve will have good I/O performance, though such an outcome is by no means guaranteed by a small working-set size. We analyze our algorithms directly in terms of I/Os and operations. In the external-memory model, permutation can be the most expensive aspect of sieving, in contrast to the RAM model, where permutations are trivial. We show how to implement classical sieves so that they have both good I/O performance and good RAM performance, even when the problem size N becomes huge—even superpolynomially larger than RAM. Towards this goal, we give two I/O-efficient priority queues that are optimized for the operations incurred by these sieves.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01326317
Contributor : Equipe Roma <>
Submitted on : Friday, June 3, 2016 - 2:22:51 PM
Last modification on : Wednesday, November 20, 2019 - 3:14:41 AM

File

sieve.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Michael Bender, Rezaul Chowdhury, Alex Conway, Martín Farach-Colton, Pramod Ganapathi, et al.. The I/O Complexity of Computing Prime Tables. Latin American Theoretical Informatics Symposium, 2016, Ensenada, Mexico. pp.192-206, ⟨10.1007/978-3-662-49529-2_15⟩. ⟨hal-01326317⟩

Share

Metrics

Record views

241

Files downloads

951