On the complexity of computing prime tables

Martín Farach-Colton, Meng-Tsung Tsai*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

Many large arithmetic computations rely on tables of all primes less than n. For example, the fastest algorithms for computing n! takes time O(M(n log n) + P(n)), where M(n) is the time to multiply two n-bit numbers, and P(n) is the time to compute a prime table up to n. The fastest algorithm to compute (nn/2) also uses a prime table. We show that it takes time O(M(n) + P(n)). In various models, the best bound on P(n) is greater than M(n log n), given advances in the complexity of multiplication [8,13]. In this paper, we give two algorithms to computing prime tables and analyze their complexity on a multitape Turing machine, one of the standard models for analyzing such algorithms. These two algorithms run in time O(M(n log n)) and O(n log2 n/ log log n), respectively. We achieve our results by speeding up Atkin’s sieve. Given that the current best bound on M(n) is n log n2 O(log n), the second algorithm is faster and improves on the previous best algorithm by a factor of log2 log n. Our fast prime-table algorithms speed up both the computation of n! and (n/n2). Finally, we show that computing the factorial takes Ω(M(n log4/7−εn)) for any constant ε > 0 assuming only multiplication is allowed.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
EditorsKhaled Elbassioni, Kazuhisa Makino
PublisherSpringer Verlag
Pages677-688
Number of pages12
ISBN (Print)9783662489703
DOIs
StatePublished - 1 Jan 2015
Event26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Japan
Duration: 9 Dec 201511 Dec 2015

Publication series

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

Conference

Conference26th International Symposium on Algorithms and Computation, ISAAC 2015
CountryJapan
CityNagoya
Period9/12/1511/12/15

Keywords

  • Factorial
  • Lower bound
  • Multiplication
  • Prime tables

Fingerprint Dive into the research topics of 'On the complexity of computing prime tables'. Together they form a unique fingerprint.

Cite this