Editing Euclidean algorithm (section)

==== 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''&nbsp;−&nbsp;1<ref name="Knuth, p. 344"/>

<!-- 
: <math  alt="The function T of a equals one over a times the sum of the function T of a comma b over all nonnegative values of b less than a." >
--> 
: <math>T(a) = \frac 1 a \sum_{0 \leq b<a} T(a, b).
</math>

However, since ''T''(''a'',&nbsp;''b'') fluctuates dramatically with the GCD of the two numbers, the averaged function ''T''(''a'') is likewise "noisy".<ref>{{harvnb|Knuth|1997}}, p. 353</ref>

To reduce this noise, a second average ''τ''(''a'') is taken over all numbers coprime with ''a''
<!--  
: <math alt="The function tau of a equals one over the function phi of a times the sum of the function T of a comma b over all nonnegative values of b less than a, where b is coprime to a." >
--> 
: <math>\tau(a) = \frac 1 {\varphi(a)} \sum_{\begin{smallmatrix} 0 \leq b<a \\  \gcd(a, b) = 1 \end{smallmatrix}} T(a, b).
</math>

There are ''φ''(''a'') coprime integers less than ''a'', where ''φ'' is [[Euler's totient function]]. This tau average grows smoothly with ''a''<ref>{{harvnb|Knuth|1997}}, p. 357</ref><ref>{{cite journal | last = Tonkov | first= T. | year = 1974 | title = On the average length of finite continued fractions | journal = Acta Arithmetica | volume = 26 | issue= 1 | pages = 47–57| doi= 10.4064/aa-26-1-47-57 | doi-access = free }}</ref>

:<math>\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon})</math>

with the residual error being of order ''a''<sup>−(1/6)+''ε''</sup>, where ''ε'' is [[infinitesimal]]. The constant ''C'' in this formula is called [[Porter's constant]]<ref>
{{cite journal
 | last = Knuth | first = Donald E. | authorlink = Donald E. Knuth
 | doi = 10.1016/0898-1221(76)90025-0
 | issue = 2
 | journal = Computers & Mathematics with Applications
 | pages = 137–139
 | title = Evaluation of Porter's constant
 | volume = 2
 | year = 1976| doi-access = free
}}</ref> and equals
: <math>C= -\frac 1 2 + \frac{6 \ln 2}{\pi^2}\left(4\gamma -\frac{24}{\pi^2}\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467</math>
where {{math|''γ''}} is the [[Euler–Mascheroni constant]] and {{math|''ζ''{{′}}}} is the [[derivative]] of the [[Riemann zeta function]].<ref>{{cite journal | last = Porter | first = J. W. | year = 1975 | title = On a Theorem of Heilbronn | journal = [[Mathematika]] | volume = 22 | issue = 1 | pages = 20–28 | doi = 10.1112/S0025579300004459}}</ref><ref>{{cite journal | last = Knuth|first = D. E. | author-link = Donald Knuth | year = 1976 | title = Evaluation of Porter's Constant | journal = Computers and Mathematics with Applications | volume = 2 | pages = 137–139 | doi = 10.1016/0898-1221(76)90025-0 | issue = 2| doi-access = free }}</ref> The leading coefficient (12/π<sup>2</sup>) ln 2 was determined by two independent methods.<ref>{{cite journal | last = Dixon | first = J. D. | year = 1970 | title = The Number of Steps in the Euclidean Algorithm | journal = J. Number Theory | volume = 2 | pages = 414–422 | doi = 10.1016/0022-314X(70)90044-2 | issue = 4|bibcode = 1970JNT.....2..414D | doi-access = free }}</ref><ref>{{cite book | last = Heilbronn | first = H. A. | author-link = Hans Heilbronn | year = 1969 | chapter = On the Average Length of a Class of Finite Continued Fractions | title = Number Theory and Analysis | editor = Paul Turán | publisher = Plenum | location = New York | pages = 87–96 | lccn = 76016027}}</ref>

Since the first average can be calculated from the tau average by summing over the divisors ''d'' of&nbsp;''a''<ref>{{harvnb|Knuth|1997}}, p. 354</ref>

<!-- : <math alt="The function T of a equals one over a times the sum of an argument summed over all divisors d of a. The argument equals the function phi of d multiplied by the function tau of d.">
 -->
: <math> T(a) = \frac 1 a \sum_{d \mid a} \varphi(d) \tau(d)
</math>
it can be approximated by the formula<ref name="Norton_1990">{{cite journal | last = Norton | first = G. H. | year = 1990 | title = On the Asymptotic Analysis of the Euclidean Algorithm | journal = Journal of Symbolic Computation | volume = 10 | issue = 1 | pages = 53–58 | doi = 10.1016/S0747-7171(08)80036-3| doi-access = free }}</ref>
: <math>T(a) \approx C + \frac{12}{\pi^2} \ln 2\, \biggl({\ln a} - \sum_{d \mid a} \frac{\Lambda(d)} d\biggr)</math>
where Λ(''d'') is the [[von Mangoldt function|Mangoldt function]].<ref>{{harvnb|Knuth|1997}}, p. 355</ref>

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''<ref name="Norton_1990" />
<!-- :<math alt="The function Y of n equals one over n squared times the double sum of the function T of a comma b for all values of a and b ranging from 1 to n. This equals one over n times the sum of the function T of a over all values of a ranging from 1 to n.">
-->
: <math>Y(n) = \frac 1 {n^2} \sum_{a=1}^n \sum_{b=1}^n T(a, b) = \frac 1 n \sum_{a=1}^n T(a).
</math>

Substituting the approximate formula for ''T''(''a'') into this equation yields an estimate for ''Y''(''n'')<ref>{{harvnb|Knuth|1997}}, p. 356</ref>
: <math>Y(n) \approx \frac{12}{\pi^2} \ln 2 \ln n + 0.06.</math>