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│
└──────┴──────┴───────┴────────┴───────┴───────┘

Essays/Euclidean Algorithm

See also