This article is cited in 8 papers

The Mean Number of Steps in the Euclidean Algorithm with Odd Incomplete Quotients

A. V. Ustinov

Institute for Applied Mathematics, Khabarovsk Division, Far-Eastern Branch of the Russian Academy of Sciences

Abstract: The length of the continued-fraction expansion of a rational number with odd incomplete quotients is expressed via the Gauss–Kuzmin statistics for the classical continued fraction. This has made it possible to prove asymptotic formulas, similar to those already known for the classical Euclidean algorithm, for the mean length of the Euclidean algorithm with odd incomplete quotients.

Keywords: Euclidean algorithm, Gauss–Kuzmin statistics, continued-fraction expansion, dual fraction, incomplete quotient.

UDC: 517.524+510.52+519.712.61

Received: 13.04.2010

DOI: 10.4213/mzm8854

 English version: Mathematical Notes, 2010, 88:4, 574–584

Bibliographic databases:

• 
• 
•