Fast computation of periodic continued fractions

DOI10.1016/0020-0190(89)90157-9MaRDI QIDQ750520zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://ntur.lib.ntu.edu.tw/bitstream/246246/154483/1/02.pdf

zbMATH Keywords

algorithmcomputation of quadratic surdsconvergent of a periodic continued fractionrational formssecond order linear recurrencessubstitution scheme

Mathematics Subject Classification ID

Continued fractions (11A55) Continued fraction calculations (number-theoretic aspects) (11Y65) Continued fractions; complex-analytic aspects (30B70) Convergence and divergence of continued fractions (40A15) Analysis of algorithms and problem complexity (68Q25)

Review text

The authors describe an O(log n) algorithm for computing the n-th convergent of a periodic continued fraction. Their algorithm is based on a scheme for substituting rational forms as symbolic terms in other rational forms. This allows a successive doubling of the number of cycles computed, where the first cycle is the periodic component of the continued fraction. The applications listed are to the computation of quadratic surds and to second order linear recurrences.

Recommendations

• Fast computation of continued fractions
• Fast computation of continued fraction expansions.
• scientific article; zbMATH DE number 3874603
• On the computing time of the continued fractions method
• An O(log n) algorithm for computing periodic continued fractions and its applications
• Algorithmes des fractions continues et de Jacobi-Perron
• The Computational Complexity of Continued Fractions
• scientific article; zbMATH DE number 1408352
• scientific article; zbMATH DE number 3965304

Cites work

• A presentation of the Fibonacci algorithm
• An \(O(\log n)\) algorithm for computing the \(n\)th element of the solution of a difference equation
• An essay on continued fractions
• An O(log n) algorithm for computing general order-k Fibonacci numbers
• Computing Fibonacci numbers (and similarly defined functions) in log time
• scientific article; zbMATH DE number 3695547 (Why is no real title available?)
• scientific article; zbMATH DE number 3053340 (Why is no real title available?)

Cited in

(15)

• Comparison of various generalizations of continued fractions
• Algebraic computations with continued fractions
• A chained-matrices approach for parallel computation of continued fractions and its applications
• Algorithms for calculating continued fractions
• Fast computation of continued fraction expansions.
• scientific article; zbMATH DE number 3874603 (Why is no real title available?)
• scientific article; zbMATH DE number 1186953 (Why is no real title available?)
• scientific article; zbMATH DE number 1113823 (Why is no real title available?)
• On the computing time of the continued fractions method
• A fast method to transform continued fractions to common fractions
• On the partial quotients of one of the continued fractions
• On the optimal continued fraction expansion of a quadratic surd
• Fast arithmetic with general Gauß periods
• Fast computation of continued fractions
• An O(log n) algorithm for computing periodic continued fractions and its applications

This page was built for publication: Fast computation of periodic continued fractions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q750520)