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.
Type de document :
Communication dans un congrès
Latin American Theoretical Informatics Symposium, 2016, Ensenada, Mexico. LATIN 2016: Theoretical Informatics, 9644, pp.192-206, 2016, LNCS. 〈10.1007/978-3-662-49529-2_15〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01326317
Contributeur : Equipe Roma <>
Soumis le : vendredi 3 juin 2016 - 14:22:51
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Fichier

sieve.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. LATIN 2016: Theoretical Informatics, 9644, pp.192-206, 2016, LNCS. 〈10.1007/978-3-662-49529-2_15〉. 〈hal-01326317〉

Partager

Métriques

Consultations de la notice

93

Téléchargements de fichiers

217