English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The binary Euclidean algorithm is a modification of the classical Euclideanalgorithm for computation of greatest common divisors which avoids ordinaryinteger division in favour of division by powers of two only. The expectationof the number of steps taken by the binary Euclidean algorithm when applied topairs of integers of bounded size was first investigated by R. P. Brent in 1976via a heuristic model of the algorithm as a random dynamical system. Based onnumerical investigations of the expectation of the associated Ruelle transferoperator, Brent obtained a conjectural asymptotic expression for the meannumber of steps performed by the algorithm when processing pairs of oddintegers whose size is bounded by a large integer. In 1998 B. Vall\'ee modifiedBrent's model via an induction scheme to rigorously prove an asymptotic formulafor the average number of steps performed by the algorithm; however, therelationship of this result with Brent's heuristics remains conjectural. Inthis article we establish previously conjectural properties of Brent's transferoperator, showing directly that it possesses a spectral gap and preserves aunique continuous density. This density is shown to extend holomorphically tothe complex right half-plane and to have a logarithmic singularity at zero. Bycombining these results with methods from classical analytic number theory weprove the correctness of three conjectured formulae for the expected number ofsteps, resolving several open questions promoted by D. E. Knuth in The Art ofComputer Programming.

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