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
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It only takes a minute to sign up.Sign up to join this community
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:
x, y, u, vrepresented 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.
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
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.