A new result in the average case analysis of the binary GCD algorithm

Speaker: GĂ©rard Maze


The binary Euclidean Algorithm is a variant of the classical Euclidean algorithm. It avoids divisions and multiplications, except by powers of two, so is potentially faster than the classical algorithm on a binary machine. In this talk, we will define the binary Euclidean algorithm and outline its history from 1976 to nowadays. We will present Richard Brent's heuristic model and sketch the proof of the existence of a unique limiting distribution that plays a central role in this model.