View source for User:Jarhill/Euclidan algorithm

===Implementations===
Implementations of the algorithm may be expressed in [[pseudocode]]. For example, the division-based version may be [[computer programming|programmed]] as<ref>{{harvnb|Knuth|1997|pp=319–320}}</ref>

 '''function''' gcd(a, b)
     '''while''' b ≠ 0
         t := b
         b := a '''mod''' b
         a := t
     '''return''' a

At the beginning of the ''k''th iteration, the variable ''b'' holds the latest remainder ''r''<sub>''k''−1</sub>, whereas the variable ''a'' holds its predecessor, ''r''<sub>''k''−2</sub>. The step ''b'' := ''a'' mod ''b'' is equivalent to the above recursion formula ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>. The [[temporary variable]] ''t'' holds the value of ''r''<sub>''k''−1</sub> while the next remainder ''r''<sub>''k''</sub> is being calculated. At the end of the loop iteration, the variable ''b'' holds the remainder ''r''<sub>''k''</sub>, whereas the variable ''a'' holds its predecessor, ''r''<sub>''k''−1</sub>.

In the subtraction-based version which was Euclid's original version, the remainder calculation (<code>b&nbsp;:=&nbsp;a '''mod''' b</code>) is replaced by repeated subtraction.<ref>{{harvnb|Knuth|1997|pp=318–319}}</ref> Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when ''a'' = ''b'':

 '''function''' gcd(a, b)
     '''while''' a ≠ b 
         '''if''' a > b
             a := a − b
         '''else'''
             b := b − a
     '''return''' a

The variables ''a'' and ''b'' alternate holding the previous remainders ''r''<sub>''k''−1</sub> and ''r''<sub>''k''−2</sub>. Assume that ''a'' is larger than ''b'' at the beginning of an iteration; then ''a'' equals ''r''<sub>''k''−2</sub>, since ''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>. During the loop iteration, ''a'' is reduced by multiples of the previous remainder ''b'' until ''a'' is smaller than ''b''. Then ''a'' is the next remainder ''r''<sub>''k''</sub>. Then ''b'' is reduced by multiples of ''a'' until it is again smaller than ''a'', giving the next remainder ''r''<sub>''k''+1</sub>, and so on.

The recursive version<ref>{{Harvnb|Stillwell|1997|p=14}}</ref> is based on the equality of the GCDs of successive remainders and the stopping condition gcd(''r''<sub>''N''−1</sub>,&nbsp;0)&nbsp;=&nbsp;''r''<sub>''N''−1</sub>.

 '''function''' gcd(a, b)
     '''if''' b = 0
         '''return''' a
     '''else'''
         '''return''' gcd(b, a '''mod''' b)

For illustration, the gcd(1071,&nbsp;462) is calculated from the equivalent gcd(462,&nbsp;1071&nbsp;mod&nbsp;462)&nbsp;=&nbsp;gcd(462,&nbsp;147). The latter GCD is calculated from the gcd(147,&nbsp;462&nbsp;mod&nbsp;147)&nbsp;=&nbsp;gcd(147,&nbsp;21), which in turn is calculated from the gcd(21,&nbsp;147&nbsp;mod&nbsp;21)&nbsp;=&nbsp;gcd(21,&nbsp;0)&nbsp;=&nbsp;21.