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. 73143.

Text
Morris_I_01.pdf  Version of Record Available under License : See the attached licence file. Download (959kB)  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 halfplane 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 : 


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 
Downloads
Downloads per month over past year