**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

Great Eddie. You are having good knowledge of online percentage calculator . Thanks for sharing.

ReplyDelete