(11C) GCD and LCM

[Dieter]

(01-07-2018 08:26 AM)wawa Wrote:  it is because I use the rule gcd(a,b)=gcd(b,a mod b) which decreases faster than gcd(a,b)=gcd(b,a-b).
Unfortunatly, there is no modulo function on the hp11, so extra steps are needed.

@Gamo: That's the same algorithm as proposed in my reply to your 12C program.

@wawa: I would recommend changing the last steps to avoid results ≥ 1 E+10 when a*b is calculated:

Code:

22 R↓
23 ENTER
24 R↓
25 /
26 *
27 R↑

Yes, it's really sad that a MOD function was not implemented on the Voyagers, not even on the 15C. A better way than coding a mod b as  b*frac(a/b) is a–b*int(a/b). This avoids roundoff errors that have to be corrected by the RND command in your program. But it is a bit more tricky to implement, especially if only the stack is used.

However, with direct stack access and a MOD function a GCD routine can be done in merely six steps, e.g. on the HP41:

Code:

01 LBL 01
02 STO Z
03 MOD
04 X≠0?
05 GTO 01
06 +

:-)

Dieter