# ETOOBUSY đ minimal blogging for the impatient

# The extended Euclid's algorithm

**TL;DR**

Sometimes you need to find out the Greatest Common Divisor of two integers.. Euclidâs algorithm is your friend. Sometimes you need slightly moreâŠ the extended Euclidâs algorithm can help too!

A few days ago Julia Evans posted a tweet about Euclidâs algorithm, linking to a video about it. While I highly appreciate her work, and wholeheartedly encourage everyone to look at it, in this specific case I didnât go through the whole 15 minutes explanation in the video becauseâŠ well, I already know Euclidâs algorithm for finding the greatest common divisor of two integers. OK Iâm cheating, I know what it is for and where to find about it.

So that should be the end of the story, right? Wrong.

## Six Lines of Code

The first thing that popped to my eyes is that the implementation was going
to be *six lines of code* long. It seemed a bit too much (didnât know the
language to be honest), considering that it can be as low as five when done
in Perl without signatures and with the sub closing brace on its own line.
See the implementation at the end if you donât believe me.

Then I looked at the code:

```
1 def gcf(a, b):
2 print(f"gcf({a},{b})")
3 if a < b:
4 return gcf(b, a)
5 if a % b == 0:
6 return b
7 return gcf(b, a % b)
```

Well, first observation is that itâs seven lines đ. To be fair, the `print`

at line 2 is actually only there to show whatâs going on and can be removed
in âthe real worldâ.

Jokes apart, lines 3 and 4 are not really necessary. Sure, the algorithm
âworksâ by taking the remainder of the greater number in a division by the
smaller one, but if `a`

is smaller than `b`

:

`a % b`

is just`a`

;- if
`a`

is zero then the greater common divisor is indeed`b`

and lines 5-6 work fine; - otherwise, line 7 becomes the same as
`return gcf(b, a)`

i.e. line 4.

Iâm not particularly fond of recursion-based solutions in general, but itâs totally my bias because I usually program in Perl and thereâs no tail-recursion optimization there (that I know of, at least). No clue about Python.

In this case, though, I think that the recursive solution is perfect to explain the algorithm.

## The extended Euclidâs algorithm

Juliaâs video touches upon a generalization of the algorithm that is applied over polynomials, so you should definitely watch the video to get the gist of it. Here, Iâd like to elaborate a bit more on an evolution towards a different direction.

The extended Euclidâs algoritm computes the greater common
divisor *and* something more within the same complexity bounds. Yes, it has
a bigger multiplicative constant đ
. In particular, it is capable of
calculating the coefficients $x$ and $y$ of the BĂ©zoutâs identity:

Why should we care?

Sometimes we might want to do operations modulo some prime $a$ and find the inverse of $b < a$ in the field $\mathbb{Z}_a$. The greatest commond divisor between them is 1 by definition ($a$ is prime!) so the identity becomes:

\[a \cdot x + b \cdot y = 1\]Going modulo $a$ simply yields:

\[b \cdot y = 1\ (mod\ a)\]i.e. $y$ from the algorithm is the inverse of $b$ in $\mathbb{Z}_a$. Yay!

## The two algorithms, in Perl

The two algorithms above, written in Perl:

In case GitLab does not work, you can find also a local version.

As promised, the basic algorithm is 5 lines long, including the input parameters unwrapping line and the closing brace - otherwise it would be 2 đ.

The extended algorithm is more or less a direct implementation of what explained in the Wikipedia page, apart from taking the stylistic choice to change some variablesâ names. Translating the code to lesser programming languages should be easy đ.

Both implementations are iterative, which helps keeping the number of
function calls to a minimum and avoid bloating `perl`

âs stack.

These functions are part of cglib-perl, my library of copy-and-paste functions for CodinGame.

## So long!

Nothing much to wrap up this time, only a suggestion: if you donât know Julia Evans and her programming zines you SHOULD definitely check them out because they are amazing!