Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems (Q5939726)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1626662
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems |
scientific article; zbMATH DE number 1626662 |
Statements
Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems (English)
0 references
30 July 2001
0 references
Euclidean algorithms
0 references
bit-complexity
0 references
Dirichlet series
0 references
complexity
0 references
gcd
0 references
dynamical systems
0 references
complexity of continued fraction expansions
0 references
transfer operators
0 references
Tauberian theorems
0 references
ergodic theory
0 references
binary algorithm
0 references
subtractive algorithm
0 references
Jacobi symbols
0 references
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. NEWLINENEWLINENEWLINEFor 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).
0 references
0.8326718807220459
0 references
0.8054323792457581
0 references
0.7988291382789612
0 references
