Numeric CAS Part 6: Euclid Algorithm to find GCD (Greatest Common Divisor)

Euclid Algorithm

Goal: To find the greatest common divisor of two integers U and V.

The Algorithm in Brief:

Let U ≥ V. Then U = A * V + R where A is the quotient and R is the remainder. If R≠0, then V becomes the new U, and R becomes the new V. The process repeats until you R=0. When that happens, V_last = GCD(U,V).

The program allows for you two enter integers in any order. Each program uses the home screen to display the steps, but the HP 39gii displays all the steps on one screen.

Example: gcd(166, 78)

166 = 2 * 78 + 10
78 = 7 * 10 + 8
10 = 1 * 8 + 2
8 = 4 * 2 + 0
GCD = 2

gcd(169,39)

169 = 4 * 39 + 13
39 = 3 * 13 + 0
GCD = 13

---

Casio Prizm:

EUCLID
GCD Program - 12/3/12
212 bytes

"X"?→ X
"Y"?→ Y
If X ≥ Y
Then X → M
Y → N
Else X → N
Y → M
IfEnd
Lbl 1
Int(M ÷ N) → A
M - A × N → R
ClrText
Locate 1,2,M
Locate 1,3,"="
Locate 2,3,A
Locate 13,3,"×"
Locate 14,3,N
Locate 1,4,"+"
Locate 2,4,R ◢
If R=0
Then Goto 2
Else N → M
R → N
Goto 1
IfEnd
Lbl 2
Locate 1,6,"GCD="
Locate 6,6,N

---

TI-84+:

GCD by Euclidian Algorithm
11/25/2012 - 160 bytes

Program EUCLID

Prompt X,Y
min(X,Y) → N
max(X,Y) → M
Lbl 1
iPart(M/N) → A
M - A * N → R
ClrHome
Output(2,1,M)
Output(3,1,"=")
Output(3,2,A)
Output(3,8,"*")
Output(3,9,N)
Output(4,1,"+")
Output(4,2,R)
Pause
If R=0
Then
Goto 2
Else
N → M
R → N
Goto 1
End
Lbl 2
ClrHome
Disp "GCD=", N

---

HP 39gii:

Program EUCLID
Finding the GCD by the Euclid algorithm
10/16/2012

Input: EUCLID(X,Y)

EXPORT EUCLID(X,Y)
BEGIN
LOCAL M,N,R,A;
MAX(X,Y)→ N;
MIN(X,Y)→M;
PRINT();
REPEAT
INT(N/M)→ A;
N - A*M→ R;
PRINT(A + "*" + M + "+" + R);
WAIT(1);
M→ N;
R→ M;
UNTIL R==0;
RETURN N;
END;

---

This blog is property of Edward Shore. 2012