Extended Euclidean algorithm

Question

I have programmed the extended euclidean algorithm. Is this a good approach?

def ext_ggT(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

Answer 1

Not being familiar with the algorithm in question, it was very non-obvious to me what the code did, and in general I think it's good to write code in such a way that it's comprehensible with minimal reasonable effort even if the reader isn't a domain expert (i.e. they should be able to look up documentation, look at your code, and see how the two relate). The main hindrances I faced were:

1. It wasn't immediately obvious that x, y, u, v represented two distinct series (where u was always a prior value of x, etc). In general there are a lot of variables in this code to keep track of, and not a lot of explanation of what they're all for.
2. Dependencies between the different values likewise were not obvious. Having all the assignments smushed onto one line made it hard to discern this visually; it's nice to use compact tuple assignments when the relationships are obvious, but it doesn't necessarily always improve readability.
3. There're no doc/comments explaining what's going on.
4. The name ext_ggT doesn't follow Python's snake_case naming convention and is a bit cryptic.

After reading the wiki link (thx Peilon) I was able to sort of reverse-engineer it and then I made some changes so that the code matches up more with my understanding based on the wiki article (and is commented so that anyone looking at this code side by side with the wiki article will immediately see what goes with what).

from collections import deque
from typing import Tuple

def extended_euclidean(a: int, b: int) -> Tuple[int, int, int]:
    """
    Returns (gcd, x, y) such that:
       gcd  = greatest common divisor of (a, b)
       x, y = coefficients such that ax + by = gcd
    """
    # We only need to keep the last two elements of each series.
    r = deque([b, a], 2)
    s = deque([0, 1], 2)
    t = deque([1, 0], 2)

    # The next element of each series is a function of the previous two.
    # We stop building these series once r (the remainder) is zero; 
    # the final result comes from the iteration prior to that one.
    while r[-1] != 0:
        q = r[-2] // r[-1]
        r.append(r[-2] % r[-1])
        s.append(s[-2] - s[-1] * q)
        t.append(t[-2] - t[-1] * q)

    return r[-2], s[-2], t[-2]

assert extended_euclidean(240, 46) == (2, -9, 47)

The biggest change is that I've represented the various series described in the wiki article as iterables, rather than representing each as two scalars; this doesn't make much difference to the way the code actually runs, but the fact that these six values (previously a, b, x, y, u, and v) represent three distinct series is now very obvious to the reader. The three series are initialized and extended in such a way as to "make alike look alike" -- you can see at a glance how each successive element is computed from the prior two, and easily discern where there are and aren't dependencies between these values.

You could initialize these series as simply:

r = [b, a]
s = [0, 1]
t = [1, 0]

and the code would return the correct result, but to preserve the behavior of only keeping the last two elements (which I agree is a good space optimization) I've converted them to deques with maxlen=2. The deque abstracts away the business of automatically popping the unneeded values off of the left side, which helps declutter the "interesting" part of the implementation while still preserving the property of having it use constant space.

Answer 2

Give your variables meaningful names reflecting their role in the algorithm.