On the complexity of computing prime tables

DOI10.1007/978-3-662-48971-0_57MaRDI QIDQ3459904zbMATH OpenOpenAlexWikidataFDO

Authors Martin Farach-Colton, Meng-Tsung Tsai

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.05240

zbMATH Keywords

factoriallower boundmultiplicationprime tables

Mathematics Subject Classification ID

Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

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(nlogn)+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 $$ 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(nlogn)$, given advances in the complexity of multiplication cite{Furer07,De08}. 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(nlogn))$ and $O(nlo{g}^{2}n/loglogn)$, respectively. We achieve our results by speeding up Atkin's sieve. Given that the current best bound on $M(n)$ is $nlogn{2}^{O(lo{g}^{\ast }n)}$, the second algorithm is faster and improves on the previous best algorithm by a factor of $lo{g}^{2}logn$. Our fast prime-table algorithms speed up both the computation of $n!$ and $$. Finally, we show that computing the factorial takes $Omega(M(nlo{g}^{4/7-epsilon}n))$ for any constant $epsilon>0$ assuming only multiplication is allowed.

Recommendations

• On the complexity of calculating factorials
• Algorithms for the Multiplication Table Problem
• The straight line complexity of small factorials and primorials
• A space-efficient fast prime number sieve
• Computing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method

Cited in

(2)

• Volume computation for sparse Boolean quadric relaxations
• ON THE COMPLEXITY OF COMPUTING PRIME TABLES ON THE TURING MACHINE

This page was built for publication: On the complexity of computing prime tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459904)