Editing Extended Euclidean algorithm (section)

== Pseudocode==
{{hatnote|In this section and the following ones, '''''div''''' is an auxiliary function that computes the quotient of the [[Euclidean division]] of its left argument by its right argument.}} 
To implement the algorithm that is described above, one should first remark that only the two last values of the indexed variables are needed at each step. Thus, for saving memory, each indexed variable must be replaced by just two variables.

For simplicity, the following algorithm (and the other algorithms in this article) uses [[parallel assignment]]s. In a programming language which does not have this feature, the parallel assignments need to be simulated with an auxiliary variable. For example, the first one,
 (old_r, r) := (r, old_r - quotient * r)
is equivalent to
 prov := r;
 r := old_r - quotient × prov;
 old_r := prov;
and similarly for the other parallel assignments.
This leads to the following code:

 '''function''' extended_gcd(a, b)
     (old_r, r) := (a, b)
     (old_s, s) := (1, 0)
     (old_t, t) := (0, 1)
     
     '''while''' r ≠ 0 '''do'''
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r − quotient × r)
         (old_s, s) := (s, old_s − quotient × s)
         (old_t, t) := (t, old_t − quotient × t)
     
     '''output''' "Bézout coefficients:", (old_s, old_t)
     '''output''' "greatest common divisor:", old_r
     '''output''' "quotients by the gcd:", (t, s)

The quotients of ''a'' and ''b'' by their greatest common divisor, which is output, may have an incorrect sign. This is easy to correct at the end of the computation but has not been done here for simplifying the code. Similarly, if either ''a'' or ''b'' is zero and the other is negative, the greatest common divisor that is output is negative, and all the signs of the output must be changed.

Finally, notice that in Bézout's identity, <math>ax + by = \gcd(a, b)</math>, one can solve for <math>y</math> given <math>a, b, x, \gcd(a, b)</math>. Thus, an optimization to the above algorithm is to compute only the <math>s_k</math> sequence (which yields the Bézout coefficient <math>x</math>), and then compute <math>y</math> at the end:

 '''function''' extended_gcd(a, b)
     s := 0;    old_s := 1
     r := b;    old_r := a
          
     '''while''' r ≠ 0 '''do'''
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r − quotient × r)
         (old_s, s) := (s, old_s − quotient × s)
     
     '''if''' b ≠ 0 '''then'''
         bezout_t := (old_r − old_s × a) '''div''' b
     '''else'''
         bezout_t := 0
     
     '''output''' "Bézout coefficients:", (old_s, bezout_t)
     '''output''' "greatest common divisor:", old_r

However, in many cases this is not really an optimization: whereas the former algorithm is not susceptible to overflow when used with machine integers (that is, integers with a fixed upper bound of digits), the multiplication of ''old_s * a'' in computation of ''bezout_t'' can overflow, limiting this optimization to inputs which can be represented in less than half the maximal size. When using integers of unbounded size, the time needed for multiplication and division grows quadratically with the size of the integers. This implies that the "optimisation" replaces a sequence of multiplications/divisions of small integers by a single multiplication/division, which requires more computing time than the operations that it replaces, taken together.