University of Surrey

Test tubes in the lab Research in the ATI Dance Research

A rigorous version of R.P. Brent’s model for the binary Euclidean algorithm

Morris, ID (2015) A rigorous version of R.P. Brent’s model for the binary Euclidean algorithm Advances in Mathematics, 290. pp. 73-143.

[img]
Preview
Text
Morris_I_01.pdf - Version of Record
Available under License : See the attached licence file.

Download (959kB) | Preview
[img]
Preview
PDF (licence)
SRI_deposit_agreement.pdf
Available under License : See the attached licence file.

Download (33kB) | Preview

Abstract

The binary Euclidean algorithm is a modification of the classical Euclidean algorithm for computation of greatest common divisors which avoids ordinary integer division in favour of division by powers of two only. The expectation of the number of steps taken by the binary Euclidean algorithm when applied to pairs of integers of bounded size was first investigated by R.P. Brent in 1976 via a heuristic model of the algorithm as a random dynamical system. Based on numerical investigations of the expectation of the associated Ruelle transfer operator, Brent obtained a conjectural asymptotic expression for the mean number of steps performed by the algorithm when processing pairs of odd integers whose size is bounded by a large integer. In 1998 B. Vallée modified Brent's model via an induction scheme to rigorously prove an asymptotic formula for the average number of steps performed by the algorithm; however, the relationship of this result with Brent's heuristics remains conjectural. In this article we establish previously conjectural properties of Brent's transfer operator, showing directly that it possesses a spectral gap and preserves a unique continuous density. This density is shown to extend holomorphically to the complex right half-plane and to have a logarithmic singularity at zero. By combining these results with methods from classical analytic number theory we prove the correctness of three conjectured formulae for the expected number of steps, resolving several open questions promoted by D.E. Knuth in The Art of Computer Programming.

Item Type: Article
Subjects : Mathematics
Divisions : Faculty of Engineering and Physical Sciences > Mathematics
Authors :
AuthorsEmailORCID
Morris, IDUNSPECIFIEDUNSPECIFIED
Date : 22 December 2015
Identification Number : 10.1016/j.aim.2015.12.008
Copyright Disclaimer : Published under a Creative Commons license
Uncontrolled Keywords : Euclidean algorithm; Greatest common divisor; Analysis of algorithms; Transfer operator; Random dynamical system
Depositing User : Symplectic Elements
Date Deposited : 29 Jul 2016 15:49
Last Modified : 29 Jul 2016 15:49
URI: http://epubs.surrey.ac.uk/id/eprint/811278

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year


Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800