Essays/Euclidean Algorithm
From J Wiki
< Essays
Jump to navigation
Jump to search
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│
└──────┴──────┴───────┴────────┴───────┴───────┘
See also
Contributed by Roger Hui.