[DM16] Euclidean algorithm in stack

Contributed software for the DM10, DM11, DM12, DM15 and DM16 goes here.

Please prefix the subject of your post with the model of the calculator that your program is for.
Post Reply
IainGray
Posts: 6
Joined: Sat Mar 07, 2020 9:55 am

[DM16] Euclidean algorithm in stack

Post by IainGray » Wed Mar 25, 2020 12:23 pm

The Euclidean algorithm https://en.wikipedia.org/wiki/Euclidean_algorithm is an efficient method of finding the GCD (greatest common divisor) of two integers. It proceeds by finding successive remainders of the larger by the smaller and swapping the smaller with the remainder until the remainder equals zero, returning the divisor as the GCD.

The code
Screenshot 2020-03-24 at 11.35.21.png
Screenshot 2020-03-24 at 11.35.21.png (19.29 KiB) Viewed 1316 times
was developed on an HP16C emulator and so works on the DM16 but will run on any DM calculator.

Line 4 LBL E for Euclid is the normal entry point after entering your two numbers, i.e. <number 1> ENTER <number 2> GSB E, the GCD is returned. The re-entrant loop at line 1 LBL F is only for non-zero remainders. Only stack variables x, y and LST X are used and no Registers.

whuyse
Posts: 57
Joined: Thu Dec 21, 2017 12:23 pm

Re: [DM16] Euclidean algorithm in stack

Post by whuyse » Mon Apr 27, 2020 8:34 am

You can do it with just LBL E:

Code: Select all

LBL E
RMD
LASTX
X<>Y
X!=0?
GTO E
+
RTN
Cheers, Werner
42S #3249S01123
DM42 #00345

IainGray
Posts: 6
Joined: Sat Mar 07, 2020 9:55 am

Re: [DM16] Euclidean algorithm in stack

Post by IainGray » Tue Apr 28, 2020 10:24 am

thanks you are correct. The DM16 code was intended to illustrate what was possible using the stack rather than optimal. thanks again Iain

Post Reply