Editing Euclidean algorithm (section)

=== Number of steps ===
The number of steps to calculate the GCD of two natural numbers, ''a'' and ''b'', may be denoted by ''T''(''a'',&nbsp;''b'').<ref name="Knuth, p. 344">{{harvnb|Knuth|1997}}, p. 344</ref> If ''g'' is the GCD of ''a'' and ''b'', then ''a''&nbsp;=&nbsp;''mg'' and ''b''&nbsp;=&nbsp;''ng'' for two coprime numbers ''m'' and ''n''. Then
: {{math|1=''T''(''a'', ''b'') = ''T''(''m'', ''n'')}}
as may be seen by dividing all the steps in the Euclidean algorithm by ''g''.<ref>{{Harvnb|Ore|1948|p=45}}</ref> By the same argument, the number of steps remains the same if ''a'' and ''b'' are multiplied by a common factor ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb''). Therefore, the number of steps ''T'' may vary dramatically between neighboring pairs of numbers, such as T(''a'', ''b'') and T(''a'',&nbsp;''b''&nbsp;+&nbsp;1), depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation
: {{math|1=''T''(''a'', ''b'') = 1 + ''T''(''b'', ''r''<sub>0</sub>) = 2 + ''T''(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = ''N'' + ''T''(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''N'' + 1}}
where ''T''(''x'', 0)&nbsp;=&nbsp;0 by assumption.<ref name="Knuth, p. 344"/>

==== Worst-case ====

If the Euclidean algorithm requires ''N'' steps for a pair of natural numbers ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0, the smallest values of ''a'' and ''b'' for which this is true are the [[Fibonacci number]]s ''F''<sub>''N''+2</sub> and ''F''<sub>''N''+1</sub>, respectively.<ref name="Knuth, p. 343">{{harvnb|Knuth|1997}}, p. 343</ref> More precisely, if the Euclidean algorithm requires ''N'' steps for the pair ''a''&nbsp;>&nbsp;''b'', then one has ''a''&nbsp;≥&nbsp;''F''<sub>''N''+2</sub> and ''b''&nbsp;≥&nbsp;''F''<sub>''N''+1</sub>. This can be shown by [[mathematical induction|induction]].<ref>{{Harvnb|Mollin|2008|p=21}}</ref> If ''N''&nbsp;=&nbsp;1, ''b'' divides ''a'' with no remainder; the smallest natural numbers for which this is true is ''b''&nbsp;=&nbsp;1 and ''a''&nbsp;=&nbsp;2, which are ''F''<sub>2</sub> and ''F''<sub>3</sub>, respectively. Now assume that the result holds for all values of ''N'' up to ''M''&nbsp;−&nbsp;1. The first step of the ''M''-step algorithm is ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>, and the Euclidean algorithm requires ''M''&nbsp;−&nbsp;1 steps for the pair ''b''&nbsp;>&nbsp;''r''<sub>0</sub>. By induction hypothesis, one has ''b''&nbsp;≥&nbsp;''F''<sub>''M''+1</sub> and ''r''<sub>0</sub>&nbsp;≥&nbsp;''F''<sub>''M''</sub>. Therefore, ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;≥&nbsp;''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;≥&nbsp;''F''<sub>''M''+1</sub>&nbsp;+&nbsp;''F''<sub>''M''</sub>&nbsp;=&nbsp;''F''<sub>''M''+2</sub>,
which is the desired inequality.
This proof, published by [[Gabriel Lamé]] in 1844, represents the beginning of [[computational complexity theory]],<ref>{{Harvnb|LeVeque|1996|p=35}}</ref> and also the first practical application of the Fibonacci numbers.<ref name="Knuth, p. 343"/>

This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).<ref>{{Harvnb|Mollin|2008|pp=21–22}}</ref> For if the algorithm requires ''N'' steps, then ''b'' is greater than or equal to ''F''<sub>''N''+1</sub> which in turn is greater than or equal to ''φ''<sup>''N''−1</sup>, where ''φ'' is the [[golden ratio]]. Since ''b''&nbsp;≥&nbsp;''φ''<sup>''N''−1</sup>, then ''N''&nbsp;−&nbsp;1&nbsp;≤&nbsp;log<sub>''φ''</sub>''b''. Since log<sub>10</sub>''φ''&nbsp;>&nbsp;1/5, (''N''&nbsp;−&nbsp;1)/5&nbsp;<&nbsp;log<sub>10</sub>''φ''&nbsp;log<sub>''φ''</sub>''b''&nbsp;=&nbsp;log<sub>10</sub>''b''. Thus, ''N''&nbsp;≤&nbsp;5&nbsp;log<sub>10</sub>''b''. Thus, the Euclidean algorithm always needs less than [[Big O notation|''O''(''h'')]] divisions, where ''h'' is the number of digits in the smaller number ''b''.

==== 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>