Essays/Euclidean Algorithm
< 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.