Computing everything in essentially linear time

Papers

[multapps] 45pp, draft. (PDF) (PS) (DVI) D. J. Bernstein. Fast multiplication and its applications. Abstract: ``This survey explains how some useful arithmetic operations can be sped up from quadratic time to essentially linear time.'' Contents:

1. Introduction
2. Product: the FFT case
3. Product: extension
4. Product: zero-padding and localization
5. Product: completion
6. Reciprocal
7. Quotient
8. Logarithm: the series case
9. Exponential: the series case
10. Power: the series case
11. Matrix product
12. Product tree
13. Sum of fractions
14. Fraction from continued fraction
15. Exponential: the short case
16. Exponential: the general case
17. Quotient and remainder
18. Remainder tree
19. Small factors of a product
20. Small factors of a sequence
21. Continued fraction from fraction
22. Greatest common divisor
23. Interpolator
24. Coprime base

[dcba] 23pp. (PDF) (PS) (DVI) D. J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms, to appear. Abstract: ``Let S be a finite set of positive integers. A `coprime base for S' means a set P of positive integers such that (1) each element of P is coprime to every other element of P and (2) each element of S is a product of powers of elements of P. There is a natural coprime base for S. This paper introduces an algorithm that computes the natural coprime base for S in essentially linear time. The best previous result was a quadratic-time algorithm of Bach, Driscoll, and Shallit. This paper also shows how to factor S into elements of P in essentially linear time. The algorithms apply to any free commutative monoid with fast algorithms for multiplication, division, and greatest common divisors; e.g., monic polynomials over a field. They can be used as a substitute for prime factorization in many applications.'' Contents:

1. Introduction
2. Outline of the paper
3. Coids and maximal common divisors
4. Coprime bases
5. Free coids and greatest common divisors
6. Quasiprimes and the ord function
7. The natural coprime base
8. Logarithms and M-time
9. From CBA to DCBA
10. Computing powers
11. The ppi, ppo, ppg, and pple functions
12. The ls function
13. Computing a coprime base for a two-element set
14. The prod function
15. The split function
16. Extending a coprime base
17. Merging coprime bases
18. Computing a coprime base for a finite set
19. Computing ord
20. Factoring over a coprime base
21. Factoring a set over a coprime base

[compose] 3pp. (PDF) (PS) (DVI) (PDF, AP version) D. J. Bernstein. Composing power series over a finite ring in essentially linear time. Journal of Symbolic Computation 26 (1998), 339-341. Abstract: ``Fix a finite commutative ring R. Let u and v be power series over R, with v(0)=0. This paper presents an algorithm that computes the first n terms of the composition u(v), given the first n terms of u and v, in n^{1+o(1)} ring operations. The algorithm is very fast in practice when R has small characteristic.'' Contents:

1. Introduction
2. Prime characteristic
3. Prime-power characteristic

[powers] 31pp. (PDF) (PS) (DVI) (PDF, AMS version) D. J. Bernstein. Detecting perfect powers in essentially linear time. Mathematics of Computation 67 (1998), 1253-1283. Abstract: ``This paper (1) gives complete details of an algorithm to compute approximate kth roots; (2) uses this in an algorithm that, given an integer n>1, either writes n as a perfect power or proves that n is not a perfect power; (3) proves, using Loxton's theorem on multiple linear forms in logarithms, that this perfect-power decomposition algorithm runs in time (log n)^{1+o(1)}.'' Contents:

1. Introduction
2. Acknowledgments
3. Integer arithmetic
4. Floating-point arithmetic
5. Floating-point truncation
6. Approximate powers
7. Some overly specific inequalities
8. Approximate roots
9. How to test if n=x^k
10. How to test if n is a kth power
11. How to test if n is a perfect power
12. Introduction to F(n)
13. Proof of Theorem 1
14. Intuition about F(n)
15. Analysis of F(n)
16. Multiplicative dependence
17. Linear forms in logarithms
18. More inequalities
19. Powers in short intervals
20. Final F(n) analysis
21. The 2-adic variant
22. Trial division

[fastgraeffe] D. J. Bernstein. High-precision roots of high-degree polynomials.

[westinghouse] 21pp. (scanned version) D. J. Bernstein. New fast algorithms for pi and e. Paper for the Westinghouse competition, distributed widely at the Ramanujan Centenary Conference (1987).