The mean number of steps in the Euclidean algorithm with least absolute value remainders
type: Item
instance of: scholarly article
title: The mean number of steps in the Euclidean algorithm with least absolute value remainders
zbMATH Open document ID: 1208.11014
DOI: 10.1134/S0001434609010179
author: Alexey Ustinov
published in: Mathematical Notes
publication date: 2009-11-10T00:00:00Z
review text: It is well known that the Euclidean algorithm in which the remainders \[ a=bq+r, \qquad q=\left[\frac{a}{b}+\frac{1}{2} \right], \qquad -\frac{q}{2} \leq r < \frac{q}{2} \] with least absolute values are chosen leads to the decomposition in a continued fraction \[ \frac{a}{b}=t_0+\cfrac{{\varepsilon_1}}{ t_1+\cfrac{{\varepsilon_2}}{ t_2+ \ddots + \cfrac{{\varepsilon_l}}{{t_l}}}} \] of length \(l=l(a/b)\), where \(t_0\) is an integer, \(t_1,t_2,\dots,t_l\) are positive integers, and \[ \varepsilon_k=\pm 1, t_k \geq 2, k=1,\dots,l, \; t_k+\varepsilon_{k+1}\geq 2, k=1,\dots,l-1. \] Two estimations for the mean number of steps in the Euclidean algorithm with the choice of least absolute value remainders are obtained in the paper. The bibliography contains 5 sources.
reviewed by: Mykhaylo Pahirya
Mathematics Subject Classification ID: 11A55
Mathematics Subject Classification ID: 11A05
Mathematics Subject Classification ID: 11J70
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 5628141
zbMATH Keywords: Euclidean algorithm
zbMATH Keywords: Euclidean algorithm with least absolute value remainder
zbMATH Keywords: continued fraction
zbMATH Keywords: Gauss--Kuzmin statistics
MaRDI profile type: Publication
cites work: Q5828139
cites work: On a theorem of Heilbronn
cites work: Euclidean algorithms are Gaussian
full work available at URL: s0001434609010179
OpenAlex ID: W2055912915
description: scientific article; zbMATH DE number 5628141