The Number of Steps in the Euclidean Algorithm Academic Article uri icon

abstract

  • When the Euclidean algorithm is run on a pair (a, b) of positive integers with a < b, the number of steps of the form (a, b) (b mod a, a) required to extract the gcd is known to be typically close to (12 log 2/2) log b. Here we sharpen earlier estimates of Dixon [J. Number Theory2 (1970), 414-422] and Heilbronn ["Number Theory and Analysis (Papers in Honor of Edmund Landau)," pp. 87-96] and show that among pairs (a, b) with 1 a b x as x , the number of such steps has an asymptotically normal distribution with mean close to (12 log 2/2) log x and variance close to C1 log x, where C1 = -6(12 log 2/2)3(d2/ds2) log (s)|s = 2, with (s) denoting a certain pseudo zeta function associated with continued fractions. 1994 Academic Press Inc.

published proceedings

  • Journal of Number Theory

author list (cited authors)

  • Hensley, D.

citation count

  • 33

complete list of authors

  • Hensley, D

publication date

  • January 1994