Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators |
| |
Authors: | B Vallée |
| |
Affiliation: | (1) GREYC, Université de Caen, 14032 Caen Cedex, France. Brigitte.Vallee@info.unicaen.fr., FR |
| |
Abstract: | We provide here a complete average-case analysis of the binary continued fraction representation of a random rational whose
numerator and denominator are odd and less than N . We analyze the three main parameters of the binary continued fraction expansion, namely, the height, the number of steps
of the binary Euclidean algorithm, and finally the sum of the exponents of powers of 2 contained in the numerators of the
binary continued fraction. The average values of these parameters are shown to be asymptotic to A
i
log N , and the three constants A
i
are related to the invariant measure of the Perron—Frobenius operator linked to this dynamical system. The binary Euclidean
algorithm was previously studied in 1976 by Brent who provided a partial analysis of the number of steps, based on a heuristic
model and some unproven conjecture. Our methods are quite different, not relying on unproven assumptions, and more general,
since they allow us to study all the parameters of the binary continued fraction expansion.
Received February 9, 1998; revised March 15, 1998. |
| |
Keywords: | , Analysis of algorithms, Generating functions, Continued fractions, Dynamical systems, Ruelle operator, Hardy spaces,,,,,,Tauberian theorems, |
本文献已被 SpringerLink 等数据库收录! |
|