For a random pair of rational numbers, the average number of divisions is Here, we will analyse the binary Euclidean algorithm, which uses only subtractions and right binary shifts. Their average values on the set are respectively noted E n , P n and S n . Note that E n is also the average number of exchanges in the algorithm, and that P n is the average number of operations that are necessary to obtain the expansion.
Proof Let be the subset of for which the algorithm performs exactly l exchanges.
The Tauberian theorem applies to F with and . Indeed The last member of the equality clearly satisfies the conditions of the Tauberian theorem, and the same holds for with and . The Tauberian theorem applies to G with and . It is impossible to conclude as quickly as in lemma 1, indeed, this time we need to find an appropriate functional space on which V s is a compact operator. Thus is regular on the domain D and condition 1 of the Tauberian theorem is fulfilled.