(12C) Greatest Common Divisor
01-06-2018, 12:29 AM (This post was last modified: 01-07-2018 02:35 AM by Gamo.)
Post: #1
 Gamo Senior Member Posts: 713 Joined: Dec 2016
(12C) Greatest Common Divisor
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
01-06-2018, 01:10 AM
Post: #2
 Carsen Member Posts: 204 Joined: Jan 2017
RE: (12C) Greatest Common Divisor
I love your programs Gamo since I use the HP-12C all the time! Thanks for the post.
01-06-2018, 04:23 AM
Post: #3
 Gamo Senior Member Posts: 713 Joined: Dec 2016
RE: (12C) Greatest Common Divisor
Thank You Carsen

Gamo
10-08-2021, 08:08 AM (This post was last modified: 10-08-2021 08:15 AM by Gamo.)
Post: #4
 Gamo Senior Member Posts: 713 Joined: Dec 2016
RE: (12C) Greatest Common Divisor
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

GCD = 9

Gamo 10/2021
01-26-2022, 07:35 AM
Post: #5
 Gamo Senior Member Posts: 713 Joined: Dec 2016
RE: (12C) Greatest Common Divisor
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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)