(12C) Greatest Common Divisor

[Gamo]

Quick and Simple program to find GCD of two integers.

Code:


 -
LSTx
X<>Y
ENTER
 x
 √
X=0
GTO 10
GTO 01
X<>Y

Thanks to Dieter for the trick by make sure that Y is greater than X so ABS don't have to be use and here is the update program.

Code:


X≤Y
X<>Y
X<>Y
  -
LSTx
X<>Y
X=0
GTO 10
GTO 01
X<>Y

Example:
Test 1 GCD (256, 656) is 16 ---> 256 ENTER 656 R/S
Test 2 GCD (12345, 67890) is 15 ---> 12345 ENTER 67890 R/S

Remark: Test 2 will run faster on HP 12C+

Gamo

[Carsen]

I love your programs Gamo since I use the HP-12C all the time! Thanks for the post.

[Gamo]

Thank You Carsen

Gamo

[Gamo]

Long time no update for the GCD program.

I dig around some HP manual and found the HP-91 User's Manual on

Page 122 demostrated the manually keys in steps to find GCD with this

algorithm the slower computation speed on Original Classic HP-12C

will do really well and here I adapted this to run on the HP-12C

Code:


01 STO 1
02 R/S
03 ENTER
04 ENTER
05 RCL 1
06 ÷
07 INTG
08 RCL 1
09  x
10  -
11 X=0
12 GTO 19
13 RCL 1
14 X<>Y
15 STO 1
16 CLx
17  +
18  GTO 03
19  RCL 1
20 GTO 00

Example:
GCD (153, 351)

153 [R/S] display 153
351 [R/S] display answer 9

GCD = 9

Gamo 10/2021

[Gamo]

Long time no update this one is nothing special since program used

Euclidean algorithm. Program use four storage registers so that it can

find the LCM as well. With this algorithm I think its run much faster than

the shorter program line version.

----------------------------------------------------------

Example Usage. Find GCD and LCM of 337744, 2736

337744 [R/S] 2736 [R/S] display shown running then 304 [R/S] 3039696

GCD = 304
LCM = 3039696
---------------------------------------------------------
Program:

Quote:01 STO 1
02 R/S
03 STO 2
04 x
05 STO 0
06 RCL 1
07 RCL 2
08 ÷
09 INTG
10 RCL 2
11 x
12 RCL 1
13 -
14 CHS
15 STO 3
16 X=0
17 GTO 23
18 RCL 2
19 STO 1
20 RCL 3
21 STO 2
22 GTO 06
23 RCL 2
24 R/S
25 RCL 0
26 X<>Y
27 ÷
28 GTO 00

Remark:
This program is based on Euclidean algorithm so it run as that so this will not
be about shorter program line, no storage register in use and
using only stacks manipulations.

Gamo 1/26/2022