 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")

In each step "k" of the Euclidean algorithm, the quotient "q""k" and remainder "r""k" are computed for a given pair of integers "r""k"−2 and "r""k"−1

The computational expense per step is associated chiefly with finding "q""k", since the remainder "r""k" can be calculated quickly from "r""k"−2, "r""k"−1, and "q""k"

The computational expense of dividing "h"-bit numbers scales as "O"("h"("ℓ"+1)), where "ℓ" is the length of the quotient.For comparison, Euclid's original subtraction-based algorithm can be much slower.