+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (42S) GCD (/thread-6528.html)
(42S) GCD - Eddie W. Shore - 07-10-2016 01:39 AM
HP 42S: GCD (Greatest Common Divisor) by Euclid Division
Enter the two integers on the Y stack and X stack. Order doesn’t matter.
Code:
00 {42-Byte Prgm}
01 LBL “GCD”
02 X<Y?
03 X<>Y
04 STO 01 \\ store maximum in R01
05 X<>Y
06 STO 00 \\ store minimum in R00
07 LBL 00 \\ main loop
08 RCL 01
09 ENTER
10 RCL÷ 00
11 IP
12 RCL* 00
13 –
14 X=0? \\ is max – IP(min/max)*min = 0?
15 GTO 01
16 X<>Y
17 STO 01
18 X<>Y
19 STO 00
20 GTO 00
21 LBL 01 \\ display GCD
22 RCL 00
23 “GCD:”
24 ARCL ST X
25 AVIEW
26 ENDTest: Find the GCD of 485 and 175.
485 [ENTER] 175 [XEQ] {GCD} Result: 5
Alternatively:
175 [ENTER] 485 [XEQ] {GCD} Result: 5
RE: (42) GCD - Joe Horn - 07-12-2016 03:48 AM
As others have recently posted in parallel discussions, the GCD routine in the PPC ROM is probably the shortest and fastest possible:
LBL c
MOD
LASTX
X<>Y
X\=0? ("not equal to zero?")
GTO c
+
RTN
Instructions: Same.
Output: GCD is returned in X.
RE: (42) GCD - Dieter - 07-12-2016 06:23 AM
(07-12-2016 03:48 AM)Joe Horn Wrote: As others have recently posted in parallel discussions, the GCD routine in the PPC ROM is probably the shortest and fastest possible:
Also posted in the other GCD thread:
You can get it one step shorter (but with the same byte count):
Code:
LBL d
STO Z
MOD
X≠0?
GTO d
+
ENDNote to HP42 users: STO Z is STO ST Z.
Dieter
RE: (42) GCD - Paul Dale - 07-12-2016 06:40 AM
Of the 34S you can do even better:
Code:
01 GCD
- Pauli
RE: (42) GCD - Dieter - 07-13-2016 09:59 AM
(07-12-2016 06:40 AM)Paul Dale Wrote: Of the 34S you can do even better:
Code:
01 GCD
You do not even need this single line as GCD can be executed directly in run mode. ;-)
So the shortest possible code is
Code:
8-)
Dieter
RE: (42S) GCD - Csaba Tizedes - 08-17-2017 02:23 PM
(07-10-2016 01:39 AM)Eddie W. Shore Wrote: GCD (Greatest Common Divisor) by Euclid
There is a 15C version as per Marcus du Sautoy explanation (in TV show 'Secrets Of Modern Living: Algorithms')
Code:
LBL E
x=y / there are the two numbers are equal?
RTN / yes, stop here and the GCD on the display
x>y / no, check there are the smaller number in x?
x<>y / no, chsnge x and y
- / let's substract it
LSTx / and get back the number of x
GTO E / and again until numbers are equalDeatiled discussion is here: Calculator Google Group - GCD (Euclid's Algorithm)
In that thread another version is available for SENCOR SEC103, which is a perfect clone of CASIO fx-3650P (but much cheaper, much faster and most precise
)Csaba
RE: (42S) GCD - Logan - 02-13-2018 09:57 PM
(07-12-2016 06:23 AM)Dieter Wrote: Also posted in the other GCD thread:
You can get it one step shorter (but with the same byte count):
Code:
LBL d
STO Z
MOD
X≠0?
GTO d
+
END
I tried to come up with my own method to do this (after reading about Euclid's Algorithm), and once I had did a search to see what others had come up with. I was proud to see that the one I'd come up with was identical to this with the exception that I swapped X<>Y at the end instead of the addition.