The computational complexity of continued fractions

ABSTRACT

The Knuth-Schönhage algorithm for expanding a quolynomial into a continued fraction is shown to be essentially optimal with respect to the number of multiplications/divisions used, uniformly in the inputs.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Borodin, A. and Munro, I., Computational complexity of algebraic and numeric problems, American Elsevier, 1975.
• 3: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 4: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 5: Fano, R.M., Transmission of information, a statistical theory of communications, Wiley, 1961.
• 6: Hartshorne, R., Algebraic geometry, Springer, 1977.
• 7: Heintz, J. and Sieveking, M., Lower bounds for polynomials with algebraic coefficients, Theor. Comput. Science 11(1980), 321-330.
• 8: Knuth, D.E., The analysis of algorithms, Proc. Internat. Congress Math. (Nice, 1970), vol. 3, Gauthier-Villars, 1971, 269-274.
• 9: Kung, H.T., On computing reciprocals of power series, Numer. Math. 22(1974), 341-348.
• 10: Lehmer, D.H., Amer. Math. Monthly 45(1937), 227-233.
• 11: R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
• 12: Mumford, D., Introduction to algebraic geometry, Chapter I, Harvard University (mimeogr. notes).
• 13: Perron, O., Die Lehre von den Kettenbrüchen, Teubner, 1913.
• 14: Samuel, P., Méthodes d'algèbre abstraite en géométrie algebrique, Springer, 1967.
• 15: Schnorr, C.P., An extension of Strassen's degree bound, preprint in: Prof. of the FCT Conf. in Berlin/Wendisch-Rietz, 1979, ed. L. Budach, Akademie-Verlag, 1979 (a), 404-416.
• 16: Schönhage, A., Schnelle Berechnung von Ketten-bruchentwicklungen, Acta Inform. 1(1971), 139-144.
• 17: Schönhage, A., An elementary proof of Strassen's degree bound, Theor. Comput. Science 3(1976), 267-272.
• 18: Shafarevich, I.R., Basic algebraic geometry, Part I, Springer, 1974.
• 19: Sieveking, M., An algorithm for division of power series, Computing 10(1971), 153-156.
• 20: Strassen, V., Gaussian elimination is not optimal, Numer. Math. 13(1969), 354-456.
• 21: Strassen, V., Berechnung und Programm I, Acta Inform. 1(1972), 320-335.
• 22: Strassen, V., Berechnung und Programm II, Acta Inform. 2(1973), 64-79.
• 23: Strassen, V., Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20(1973), 238-251.
• 24: Strassen, V., Computational complexity over finite fields, SIAM J. Comput. 5(1976), 324-331.
• 25: Strassen, V., Some results in algebraic complexity theory, Proc. Internat. Congress Math., Vancouver, 1974.
• 26: Wall, H.S., Analytic theory of continued fractions, van Nostrand, 1948.
• 27: van der Waerden, B.L., Einführung in die algebraische Geometrie, Springer, 1973.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory