TY - GEN

T1 - On the complexity of computing prime tables

AU - Farach-Colton, Martín

AU - Tsai, Meng Tsung

N1 - Funding Information:
M. Farach-Colton and M.-T. Tsai—Work supported by CNS-1408782 and IIS-1247750.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Factorial

KW - Lower bound

KW - Multiplication

KW - Prime tables

UR - http://www.scopus.com/inward/record.url?scp=84951913593&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84951913593&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48971-0_57

DO - 10.1007/978-3-662-48971-0_57

M3 - Conference contribution

AN - SCOPUS:84951913593

SN - 9783662489703

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 677

EP - 688

BT - Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings

A2 - Elbassioni, Khaled

A2 - Makino, Kazuhisa

PB - Springer Verlag

T2 - 26th International Symposium on Algorithms and Computation, ISAAC 2015

Y2 - 9 December 2015 through 11 December 2015

ER -