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 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.
[DM16] Euclidean algorithm in stack
Re: [DM16] Euclidean algorithm in stack
You can do it with just LBL E:
Cheers, Werner
Code: Select all
LBL E
RMD
LASTX
X<>Y
X!=0?
GTO E
+
RTN
41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE, DM15L
Re: [DM16] Euclidean algorithm in stack
thanks you are correct. The DM16 code was intended to illustrate what was possible using the stack rather than optimal. thanks again Iain