Analysis of the binary Euclidean algorithm
Richard P. Brent · ACM SIGSAM Bulletin · 1976
The binary Euclidean algorithm finds the GCD of two integers u and v using subtraction, shifting and parity testing. Unlike the classical Euclidean algorithm, no divisions are required. We analyse a continuous model of the binary algorithm, and find the expected number of iterations.