Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems (Q5939726): Difference between revisions

The author develops a general analysis of the complexity of Euclidean (or gcd) algorithms, by viewing them as dynamical systems. The reader will be delighted to see in a same paper notions as complexity of continued fraction expansions, transfer operators, Tauberian theorems, and ergodic theory entering the picture. Note that the paper provides analyses of bit-complexities not only for the classical Euclidean algorithms, but also for the binary algorithm, the subtractive algorithm, and algorithms computing Jacobi symbols. A bibliography with 41 references ends the paper. For a survey on ancient work on this topic, the reader can look at: \textit{J. Shallit}, Hist. Math. 21, No. 4, 401-419 (1994; Zbl 0859.01004).