Discussing the Extended Euclidean Algorithm

❖Extended Euclidean Algorithm

The Euclidean Algorithm is an algorithm in number theory used to find the greatest common divisor $c=(a,b)$ of two integers $a$ and $b$. I have previously explained that the correctness of this algorithm comes from $(a,b)=(a-k b), k\in \Z$. The Extended Euclidean Algorithm is an algorithm that can obtain the coefficients $s$ and $t$ in

The first time I saw the implementation of this algorithm was from a classmate who was proficient in algorithm competitions. His implementation was similar to

1int exgcd(int a,int b,int &x,int &y)
2{
3    if(b==0)
4    {
5        x = 1; y = 0; return a;
6    }
7    int r = exgcd(b, a % b, x, y);
8    int t = y;
9    y = x - (a / b) * y;
10    x = t;
11    return r;
12}

This implementation uses the parameters x and y as registers to pass the result, which has a strong imperative style.

A more understandable functional style implementation is as follows:

1let rec ext_gcd a b = 
2  if b = 0 then (1, 0, a)
3  else 
4    let quo = a / b
5    let r = a % b
6    let (s, t, gcd) = ext_gcd b r
7    (t, s - quo * t, gcd)

In fact, both of the above implementations are based on a manual substitution process. Take the following Euclidean algorithm process as an example:

Change each division formula into an addition and subtraction formula of the previous division:

Consider the penultimate formula

Replace the $\textcolor{red}{6}$ in this formula with $20 - 2 \times 7 = \textcolor{red}{6}$, we get:

More generally, the two formulas are

Then, if we merge and substitute them, it will become:

Obviously, this process can be abstracted into an operation on a triplet, represented here by $*$, that is:

Looking at the functional program again, we will be much clearer:

ext_gcd b r gets the triplet $(s, t, gcd)$ of $s b + tr = gcd$, and this triplet can perform the $*$ operation with the triplet $(1, -quo, r)$ of $1 \times a + (-quo) \times b = r$ defined by this division, and

This is exactly the return value (t, s - quo * t, gcd) in the code.

We can give a program that directly uses this operation:

1let F x1 x2 = 
2  let s1, t1, c1 = x1
3  let s2, t2, c2 = x2 
4  (s1 * t2, s2 + t1 * t2, c2)
5
6let rec ext_gcd2 a b =
7  if b = 0 then (1, 0, a)
8  else 
9    let quo = a / b
10    let r = a % b
11    F (1, -quo, r) (ext_gcd2 b r)

❖From recursion to loop

❖Wand’s pattern

More than 40 years ago, MITCHELL WAND published a paper called Continuation-Based Program Transformation Strategies, in which he summarized many general methods for transforming recursive programs into loop programs.

Of course, the real meaning of loop and recursion here needs further specification, for example,

1(define (factor n)
2  (let loop ([n n] [cont (lambda (x) x)])
3    (if (= n 0)
4        (cont 1)
5        (loop (- n 1) (lambda (x) (cont (* n x)))))))

This kind of loop is not the loop studied here, the loop we are talking about must be something with fixed space, space complexity of $O(1)$.

By studying two ways of writing functions similar to factor:

1(define (factor n)
2  (if (= n 0)
3      1
4      (* n (factor (- n 1)))))

1(define (factor n)
2  (let loop ([n n][acc 1])
3    (if (= n 0)
4        acc
5        (loop (- n 1) (* acc now)))))

WAND summarized the first pattern:

The requirement is that $b$ is an operation of $A \rightarrow A \rightarrow A$ and has associativity, where $l_b$ is the right unit element (meaning $b(x, l_b)=x$).

Can we use this pattern to transform the above program? It seems possible, because here $p(x)$, $a(x)$, $b$, $F$, $c(x)$, $d(x)$ can be clearly given.

However, there is a problem: is the operation $*$ defined above associative?

❖Associativity?

The associativity of an operation essentially describes whether this operation can change its operation order when it is self-combined. Consider an operation $f$, it has associativity, that is to say

However, our operation seems to be non-associative:

What’s going on? Let’s study a specific example:

Take the first three as examples, if you do it in the correct order:

This will result in a very surprising result, because

And our combined operation should theoretically yield

Where is the problem?

Consider $(1, -3, 7) * (1, -2, 2)=(-2, 7, 2)$, the meaning of the triplet on the right side of the equation is:

This equation cannot be operated with

using $\*$. Because the equation that can be operated with $-2 \times 55 + 7 \times 16 = 2$ using $*$ must be in the form of

As you can see, this is not just a problem of lack of associativity. For the $\*$ operation we defined, $(a\*b)\*c$ has no meaning at all.

In this way, it is impossible to transform this recursion into a loop simply by using Wang’s method.

❖How to implement in a loop?

Observe the equation above again

We seem to have discovered a new pattern:

If the above relationship can be established, then $s_n$ and $t_n$ can be calculated:

The headache is the establishment of the first two equations. In fact, if the reader has carefully studied the recursive version of the algorithm, the establishment of the last equation uses an interesting technique. We can also use the same technique here, but why this technique works is left to the reader to study:

The implementation is as follows:

1let rec ext_gcd_loop a b =
2  if b = 0 then (1, 0, a)
3  else 
4    let rec loop a b s_n1 t_n1 s_n2 t_n2 = 
5      let quo = a / b 
6      let r = a % b
7      let s = 1
8      let t = -quo
9      if r = 0 then (s_n1, t_n1, b)
10      else 
11        loop b r (s * s_n2 + t * s_n1) (s * t_n2 + t * t_n1) s_n1 t_n1
12    loop a b 0 1 1 0