# Essays/Euclidean Algorithm

The Euclidean algorithm finds the greatest common divisor (GCD) of two non-negative integers by repeated remaindering, stopping when one of the numbers is 0.

```   gcda=: 4 : 'if. *y do. y gcda y|x else. x end.'
gcdb=: 3 : 'if. *{:y do. gcdb |/\|.y else. {.y end.'
gcdc=: [: {. |/\@|.^:(*@{:)^:_
```

gcda is a classical recursive statement of the algorithm; gcdb applies to a 2-element argument; and gcdc is a tacit version of same. The tacit statement facilitates inspection of the internal workings of the algorithm.

```   32 gcda 44
4
gcdb 32 44
4
gcdc 32 44
4

|/\@|.^:(i.10) 32 44
32 44
44 32
32 12
12  8
8  4
4  0
0  4
4  0
0  4
4  0
|/\@|.^:(*@{:)^:a: 32 44
32 44
44 32
32 12
12  8
8  4
4  0
```

The Euclidean algorithm can also be used to find the GCD as a linear combination of the arguments. The idea is to work with a 2-by-3 matrix of the intermediate integers together with their linear coefficients with respect to the original two integers.

```   g0  =: , ,. =@i.@2:
it  =: {: ,: {. - {: * <.@%&{./
gcd =: (}.@{.) @ (it^:(*@{.@{:)^:_) @ g0

32 gcd 44                NB. GCD as linear coefficients
_4 3
+/ _4 3 * 32 44          NB. the actual GCD
4

] a=: 32 g0 44           NB. initial argument for GCD
32 1 0
44 0 1

it a                     NB. one iteration
44 0 1
32 1 0
it it a                  NB. two iterations
32  1 0
12 _1 1

<"2 it^:(i.6) a          NB. all iterations; stop when 0= lower left corner
┌──────┬──────┬───────┬────────┬───────┬───────┐
│32 1 0│44 0 1│32  1 0│12 _1  1│8  3 _2│4 _4  3│
│44 0 1│32 1 0│12 _1 1│ 8  3 _2│4 _4  3│0 11 _8│
└──────┴──────┴───────┴────────┴───────┴───────┘
```