Euclidean algorithm
Average

The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time T (a) required to calculate the GCD of a given number a and a smaller natural number b chosen with equal probability from the integers 0 to a − 1

However, since T (a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T (a) is likewise "noisy".

To reduce this noise, a second average τ (a) is taken over all numbers coprime with a

There are φ (a) coprime integers less than a, where φ is Euler's totient function. This tau average grows smoothly with a

with the residual error being of order a, where ε is infinitesimal. The constant C in this formula is called Porter's constant and equals

where γ is the Euler–Mascheroni constant and ζ' is the derivative of the Riemann zeta function. The leading coefficient (12/π) ln 2 was determined by two independent methods.

Since the first average can be calculated from the tau average by summing over the divisors d of a

it can be approximated by the formula

where Λ(d) is the Mangoldt function.

A third average Y (n) is defined as the mean number of steps required when both a and b are chosen randomly (with uniform distribution) from 1 to n

Substituting the approximate formula for T (a) into this equation yields an estimate for Y (n)
detectable_content:number_placeholders[7]