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

    Conference

    Conference12th Latin American Symposium on Theoretical Informatics, LATIN 2016
    Country/TerritoryMexico
    CityEnsenada
    Period4/11/164/15/16

    Keywords

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

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

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

    Cite this