The Computational Complexity of Continued Fractions

DOI10.1137/0212001zbMath0543.68026OpenAlexW1994398507MaRDI QIDQ3332243

Volker Strassen

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0212001

zbMATH Keywords

entropytime complexitycontinued fractionEuclidean representationdegree methodKnuth-Schönage algorithmquolynomialsymbolic multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05) Continued fractions (11A55)

Related Items (43)

An optimal bound for path weights in Huffman trees ⋮ Irreducibility of multivariate polynomials ⋮ Computing Frobenius maps and factoring polynomials ⋮ A tight bound for approximating the square root ⋮ The complexity of error-correcting codes ⋮ Some spectral formulas for systems and transmission lines ⋮ Boolean circuits versus arithmetic circuits ⋮ Computing special powers in finite fields ⋮ Semi-algebraic decision complexity, the real spectrum, and degree ⋮ Complexity of computation in finite fields ⋮ Cauchy index computation ⋮ Multiplicative complexity of some rational functions ⋮ Subresultants revisited. ⋮ Fast norm computation in smooth-degree abelian number fields ⋮ The bit-operation complexity of matrix multiplication and of all pair shortest path problem ⋮ New combinations of methods for the acceleration of matrix multiplication ⋮ Direct sums of bilinear algorithms ⋮ On the complexity of simplifying quadratic forms ⋮ Analysis of Euclidean algorithms for polynomials over finite fields ⋮ Computing lower bounds on tensor rank over finite fields ⋮ Fast matrix multiplication without APA-algorithms ⋮ A fast version of the Schur-Cohn algorithm. ⋮ Parallel information-based complexity ⋮ Algebraic decision trees and Euler characteristics ⋮ Some computational problems in linear algebra as hard as matrix multiplication ⋮ Test complexity of generic polynomials ⋮ On the complexity of the Lickteig-Roy subresultant algorithm ⋮ Sylvester-Habicht sequences and fast Cauchy index computation ⋮ Verification complexity of linear prime ideals ⋮ Piecewise algebraic functions ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ The complexity and depth of Boolean circuits for multiplication and inversion in some fields \(\mathrm{GF}(2^{n})\) ⋮ On the optimal computation of a set of symmetric and persymmetric bilinear forms ⋮ On the parallel complexity of the polynomial ideal membership problem ⋮ Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)] ⋮ Lower bound for the approximative complexity ⋮ Transmutation for systems by spectral methods ⋮ Complexity lower bounds for approximation algebraic computation trees ⋮ Rank and optimal computation of generic tensors ⋮ Decision trees: Old and new results. ⋮ Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2 ⋮ Quasi-gcd computations ⋮ Polynomial factorization over ${\mathbb F}_2$

This page was built for publication: The Computational Complexity of Continued Fractions