Differences between revisions 8 and 9
 ⇤ ← Revision 8 as of 2007-09-05 21:27:03 → Size: 2241 Editor: RogerHui Comment: ← Revision 9 as of 2008-12-08 10:45:32 → ⇥ Size: 2243 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 81: Line 81: [[BR]] <
> Line 85: Line 85: * [:../Binary GCD Algorithm:Binary GCD Algorithm] * [:../Gaussian Integers:Gaussian Integers] * [[../Binary GCD Algorithm|Binary GCD Algorithm]] * [[../Gaussian Integers|Gaussian Integers]] Line 88: Line 88: [[BR]] <
>

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