The Computational Complexity of Continued Fractions
Volker Strassen · SIAM Journal on Computing · 1983
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.