(42S) GCD
07-10-2016, 01:39 AM (This post was last modified: 06-15-2017 01:16 PM by Gene.)
Post: #1
 Eddie W. Shore Senior Member Posts: 712 Joined: Dec 2013
(42S) GCD
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 END

Test: Find the GCD of 485 and 175.
485 [ENTER] 175 [XEQ] {GCD} Result: 5
Alternatively:
175 [ENTER] 485 [XEQ] {GCD} Result: 5
07-12-2016, 03:48 AM
Post: #2
 Joe Horn Senior Member Posts: 1,249 Joined: Dec 2013
RE: (42) GCD
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.

X<> c
-Joe-
07-12-2016, 06:23 AM
Post: #3
 Dieter Senior Member Posts: 2,076 Joined: Dec 2013
RE: (42) GCD
(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 + END

Note to HP42 users: STO Z is STO ST Z.

Dieter
07-12-2016, 06:40 AM (This post was last modified: 07-12-2016 06:40 AM by Paul Dale.)
Post: #4
 Paul Dale Senior Member Posts: 1,367 Joined: Dec 2013
RE: (42) GCD
Of the 34S you can do even better:

Code:
01 GCD

- Pauli
07-13-2016, 09:59 AM
Post: #5
 Dieter Senior Member Posts: 2,076 Joined: Dec 2013
RE: (42) GCD
(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
08-17-2017, 02:23 PM
Post: #6
 Csaba Tizedes Member Posts: 255 Joined: May 2014
RE: (42S) GCD
(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 equal

Deatiled 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
02-13-2018, 09:57 PM (This post was last modified: 02-13-2018 10:00 PM by Logan.)
Post: #7
 Logan Member Posts: 118 Joined: Jul 2016
RE: (42S) GCD
(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.
 « Next Oldest | Next Newest »

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