The I/O complexity of computing prime tables

Michael A. Bender, Rezaul Chowdhury, Alexander Conway, Martín Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon, Shikha Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationLATIN 2016
Subtitle of host publicationTheoretical Informatics - 12th Latin American Symposium, Proceedings
EditorsGonzalo Navarro, Evangelos Kranakis, Edgar Chávez
PublisherSpringer Verlag
Pages192-206
Number of pages15
ISBN (Print)9783662495285
DOIs
StatePublished - 2016
Event12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexico
Duration: Apr 11 2016Apr 15 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9644
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th Latin American Symposium on Theoretical Informatics, LATIN 2016
CountryMexico
CityEnsenada
Period4/11/164/15/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • External-memory algorithms
  • Prime tables
  • Priority queues
  • Sorting

Fingerprint Dive into the research topics of 'The I/O complexity of computing prime tables'. Together they form a unique fingerprint.

Cite this