TI 30Xa Algorithms: Greatest Common Divisor
To find the greatest common divisor between two positive integers U and V:
Let U ≥ V. Let U = A * V + R where A is the quotient of U / V and R is the remainder. If R≠0, then V becomes the new U and R become the new V. The process repeats until R=0. At that point the value of V prior to the last calculation is the greatest common divisor (GCD) of U and V.
Example:
gcd(166, 78)
U = 166, V = 78
Algorithm Loop:
A = int(U / V)
R = U – V * int(U / V)
|
A |
R |
U |
V |
Start |
n/a |
n/a |
166 |
78 |
A = int(166 / 78) = 2 R = 166 – 2 * 78 = 10 |
2 |
10 |
78 |
10 |
A = int(78 / 10) = 7, R = 78 – 7 * 10 = 8 |
7 |
8 |
10 |
8 |
A = int(10 / 8) = 1 R = 10 – 1 * 8 = 2 |
1 |
2 |
8 |
2 |
A = int(8 / 2) = 4 R = 8 – 4 * 2 = 0 |
4 |
0 *STOP* |
|
|
Procedure
Store the greater of the two numbers in memory register 1: [ STO ] [ 1 ].
Store the lesser of the two numbers in memory register 2: [ STO ] [ 2 ].
Divide memory register 1 by memory register 2. Store the integer part (no fractional part) in memory register 3: [ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ], (integer part) [ STO ] [ 3 ]
Figure the remainder and store the result in memory 3: [ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] [ STO ] [ 3 ]
If the remainder is 0, stop. The GCD is stored in memory 2.
If the remainder is non-zero, then store memory 2 into memory 1 then memory 3 into memory 2. You need to do it in this order. [ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ]. Go back to Step 3 and repeat.
Examples
Example 1: GCD(26, 14)
M1 = 26, M2 = 14
|
M1 |
M2 |
M3 |
26 [ STO ] [ 1 ], 14 [ STO ] [ 2 ] |
26 |
14 |
|
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.857142857 1 [ STO ] [ 3 ] |
26 |
14 |
1 |
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 12 [ STO ] [ 3 ] R is not zero, so we continue. |
26 |
14 |
12 |
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ] |
14 |
12 |
12 |
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.166666667 1 [ STO ] [ 3 ] |
14 |
12 |
1 |
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 2 [ STO ] [ 3 ] R is not zero, so we continue. |
14 |
12 |
2 |
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ] |
12 |
2 |
2 |
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 6 6 [ STO ] [ 3 ] |
12 |
2 |
6 |
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 0 [ STO ] [ 3 ] R is zero, so we stop. GCD: [ RCL ] [ 2 ]: GCD(26, 14) = 2 |
12 |
2 |
0 |
Example 2: GCD(27, 15)
M1 = 27, M2 = 15
|
M1 |
M2 |
M3 |
27 [ STO ] [ 1 ], 15 [ STO ] [ 2 ] |
27 |
15 |
|
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.8 1 [ STO ] [ 3 ] |
27 |
15 |
1 |
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 12 [ STO ] [ 3 ] R is not zero, so we continue. |
27 |
15 |
12 |
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ] |
15 |
12 |
12 |
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 1.25 1 [ STO ] [ 3 ] |
15 |
12 |
1 |
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 3 [ STO ] [ 3 ] R is not zero, so we continue. |
15 |
12 |
3 |
[ RCL ] [ 2 ] [ STO ] [ 1 ], [ RCL ] [ 3 ] [ STO ] [ 2 ] |
12 |
3 |
3 |
[ RCL ] [ 1 ] [ ÷ ] [ RCL ] [ 2 ] [ = ] Result: 4 4 [ STO ] [ 3 ] |
12 |
3 |
4 |
[ RCL ] [ 1 ] [ - ] [ RCL ] [ 2 ] [ × ] [ RCL ] [ 3 ] [ = ] Result: 0 [ STO ] [ 3 ] R is zero, so we stop. GCD: [ RCL ] [ 2 ]: GCD(27, 15) = 3 |
12 |
3 |
0 |
I hope you find this useful. What I hope to do with the monthly series is to demonstrate various calculations with the TI-30Xa.
Note: For June and July 2024, I will be posting on Saturdays only. I plan to resume the Saturday-Sunday schedule in August.
Eddie
All original content copyright, © 2011-2024. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.