GCD+LCM

Display

Overview
Programs GCD calculates the Greatest Common Divider of two integer values. GCD uses a very simple and short algorithm. Its big friend GCD+LCM calculates both the Greatest Common Divider and the Least Common Multiple according to the Knuth algorithm (see also the similar program for the HP-67 at the MoHPc).

Examples
Please note my default FIX 5 and European (flag 28) setting in below examples.


Keystrokes: Display: Comments:
468 [ENTER] 228 - calculate GCD(468,228)
[XEQ][ALPHA] GCD [ALPHA] 12,00000

9449 [ENTER] 4994 - calculate GCD(9449,4994)
[R/S] 11,00000

155 [ENTER] 55 - calculate GCD(155,55)
[XEQ][ALPHA] GCD+LCM [ALPHA] 5,00000 - GCD
[RDN] 5,00000 - value of s
[RDN] -15,00000 - value of t
[RDN] 1.705,00000 - LCM

406 [ENTER] 266 - calculate GCD(406,266)
[R/S] 14,00000 - GCD
[RDN] 2,00000 - value of s
[RDN] -3,00000 - value of t
[RDN] 7.714,00000 - LCM

Program Listing


01 LBL'GCD' 01 LBL'GCD+LCM' 17 MOD 33 *
02 LBL 01 02 CLRG 18 STO 02 34 INT
03 MOD 03 STO 02 19 X=0? 35 -
04 LASTX 04 STO 07 20 GTO 06 36 STO 06
05 X<>Y 05 X<>Y 21 RCL 04 37 GTO 01
06 X#0? 06 STO 01 22 RCL 05 38 LBL 06
07 GTO 01 07 ST* 07 23 STO 04 39 RCL 07
08 X<>Y 08 1 24 RCL 00 40 RCL 06
09 END 09 STO 04 25 INT 41 RCL 05
10 STO 06 26 * 42 RCL 01
(18 bytes) 11 LBL 01 27 - 43 ST/ T
12 RCL 01 28 STO 05 44 END
13 STO 00 29 RCL 03
14 RCL 02 30 RCL 06
15 STO 01 31 STO 03
16 ST/ 00 32 RCL 00 (61 bytes)

Formulae
Given two integer values A and B of which the GCD and LCM can be determined as follows:


yi+1 = si xi+1 = ti

si+1 = (ai div bi).si + yi ti+1 = (ai div bi).ti + xi

ai+1 = bi bi+1 = ai mod bi

where:


s0 = 0, y0 = 1 t0 = 1, x0 = 0

and:


a0 = A b0 = B

The GCD follows from ai+1 if the value bi+1 equals 0 (zero):


ai+1 = GCD(A,B)

The LCM follows from:


LCM(A,B) = A.B / GCD(A,B)

Registers
R00 Work register for common values
R01 ai
R02 bi
R03 xi
R04 yi
R05 si
R06 ti
R07 Product A.B

© 1999 by Auke Hoekstra

Leave a Reply