The Museum of HP Calculators

# GCD, LCM, Decimal To Fraction for the HP-29C

This program is Copyright © 1979 by Hewlett-Packard & Philippe Legros and is used here by permission. This program was originally published in the "MATH PAC FOR HP-67/97" (program MA-02A) in 199 steps and was adapted by Philippe Legros for his personal HP-29c library. This program was transcribed by Philippe Legros.

This program is supplied without representation or warranty of any kind. Hewlett-Packard, Philippe Legros and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

## Description

This program contains three different routines: greatest common divisor, least common multiple, and decimal to fraction.

Given integers a and b, the first routine finds their greatest common divisor, GCD(a,b). The second routine will calculate, for integers a and b, their least common multiple, LCM(a,b). This routine is independent of the first, although the second one calls the first one as a subroutine.

The basic algorithm used in finding GCD(a,b) is as follows:

1. If b=0, GCD(a,b)=a and the program halts;

2. If b!=0, z <- a MOD b, a <- b and b <- z. Return to 1.

LCM(a,b) is found by LCM(a,b) = ab/GCD(a,b)

The third routine in this program will find rational fractional approximations for decimal values by the method of continued fractions. Each successive approximation is closer to the decimal value than the previous one. For example, if the decimal keyed in is 0.33, the first fractional approximation computed will be 1/3. The program will output first the numerator 1, then the denominator 3, then the 10-digit value of the approximation 0.333333333, and finally the error in this approximation, displayed in scientific notation. The error is found by substracting the original value 0.33 from the value of this approximation. At this step the error is 3.3333333-03.

The program will then go on to compute a closer fractional approximation. In this example, the next approximation would be 33/100. Since this is the exact equivalent of the original decimal value, the program will halt.

The algorithm employed in this routine uses a method of continued fractions, so that the nth fractional approximation fn is computed as:

fn=a1 + 1/(a2 + 1/(a3 + 1/(a4 + ... + 1/an)...)))

Each fi is output as a numerator Ni and a denominator Di which are computed as follows:

Ni=aiNi-1 + Ni-2

Di=aiDi-1 + Di-2

Where N-1=0, D-1=1, N0=1, D0=0 by definition.

The values for the ai may be found by the following algorithm:

If Dec is the original decimal keyed in, then ai=INT(Dec). x1=1 and y1=FRAC(Dec), then: ai+1=INT(xi/yi), xi+1=yi, yi+1=xi - ai+1yi

## Remarks

• None of the input data are checked.
• If you stop the fractional approximation routine loop the last fraction generated can be recalled by pressing [GSB] [3].

## References

• "Greatest Common Divisor, Least Common Multiple, Decimal To Fraction" (MA-02A from the Math Pac for HP-67/97) by Hewlett-Packard Company, Corvallis Division, 1000 N.E. Circle Boulevard, Corvallis, OR 97330
• "The Art of Computer Programming, vol. 2" by D.E. Knuth, Addison-Wesley, 1969 (for the GCD, LCM routines)
• "An Introduction to Continued Fractions" by Charles G. Moore, National Council of Teachers of Mathematics, 1964 (for the Decimal to Fraction routine)

## Instructions

 STEP INSTRUCTIONS INPUT DATA KEYS OUTPUT DATA 1 Key in the program. 2 For greatest common divisor, go to step 3; for least common multiple, go to step 4; for decimal to fraction, go to step 5. 3 GCD Key in integers a and b and find their greatest common divisor: a ENTER^ a b GSB 0 GCD(a,b) 4 LCM Key in integers a and b and find their least coomon multiple: a ENTER^ a b GSB 1 LCM(a,b) 5 Decimal to Fraction Key in a deimal value and find successive fractional approximations (i=1, 2, ...): Dec GSB 2 ''Num[i]'' ''Den[i]'' '''Num[i]/Den[i]''' 'Error[i]' 6 To recall the last fractional approximation: GSB 3 Last Num X<>Y Last Den

## Examples

1. Find the greatest common divisor of 406 and 266.

```KEYSTROKES            OUTPUTS           COMMENTS

406 ENTER^
266 GSB 0             14.00           GCD(406,266)=14
```

2. Find the least common multiple of 406 and 266.

```KEYSTROKES            OUTPUTS           COMMENTS

406 ENTER^
266 GSB 1             7714.00         LCM(406,266)=7714
```

3. Generate the series of fractional approximations to PI.

```KEYSTROKES            OUTPUTS           COMMENTS

g PI GSB 2            '3.'            Num[1]
'1.'            Den[1]
'3.000000000'   Num[1]/Den[1]
'-1.4159265-01' Error[1]
'22.'           Num[2]
'7.'            Den[2]
'3.142857143'   Num[2]/Den[2]
'1.26448900-03' Error[2]
'333.'          Num[3]
'106.'          Den[3]
'3.141509434'   Num[3]/Den[3]
'-8.3220000-05' Error[3]
'355.'          Num[4]
'113.'          Den[4]
'3.141592920'   Num[4]/Den[4]
'2.66000000-07' Error[4]
'104348.'       Num[5]
'33215.'        Den[5]
'3.141592654'   Num[5]/Den[5]
'0.00000000 00' Error[5]
104348.         Last Num
X<>Y                  33215.          Last Den
```

## The Program

```LINE   CODE       KEYS            COMMENTS

01  15 13 00   g LBL 0          * GCD entry routine *
02        31     ENTER^         Push a to Z
03        31     ENTER^         Push a to T (stack activated)
04        34     CLX            Freeze stack
05        51     +              Get b to X
06        22     Rv             Stack is : X=a Y=b Z=b T=a
07        71     ÷              b/a
08     14 62   f INT            Integer part of b/a
09        22     Rv
10        22     Rv
11        22     Rv             Stack is: X=a Y=INT(b/a) Z=b T=a
12        61     ×              a.INT(b/a)
13        41     -              b-a.INT(b/a) = b MOD a
14     15 61   g x!=0           GCD found ?
15     13 00     GTO 0          No, loop to step 01
16        51     +              Yes, GCD is a (Y)
17     15 12   g RTN            End of routine.
18  15 13 01   g LBL 1          * LCM entry routine *
19     23 00     STO 0          Save b in R0
20        21     X<>Y
21  23 61 00     STO × 0        Save ab in R0
22     12 00     GSB 0          Compute GCD(a,b), step 01
23     24 00     RCL 0
24        21     X<>Y
25        71     ÷              LCM(a,b)=ab/GCD(a,b)
26     15 12   g RTN            End of routine
27  15 13 02   g LBL 2          * Decimal to Fraction entry routine *
28        31     ENTER^         Push Dec to Y
29     23 00     STO 0          Save Dec to R0
30        33     EEX            Push Dec to Z
31     23 02     STO 2          1 in X, R2 and R3
32     23 03     STO 3
33        73     .              Push Dec to T
34     23 01     STO 1          0 in X, R1 and R4
35     23 04     STO 4          Stack is: X=0 Y=1 Z=Dec T=Dec
36  15 13 09   g LBL 9
37  14 11 00   f FIX 0          Set decimals to 0
38        22     Rv             X=Num[i] Y=Dec
39        71     ÷              Frc=Dec/Num[i]
40     14 73   f LASTX          Recall Num[i]
41        31     ENTER^         Push it into Y
42        22     Rv             Roll it to T
43        21     X<>Y           Get Frc
44     14 62   f INT            a[i+1]=INT(Frc)
45     23 05     STO 5          Store it into R5
46        61     ×              Num[i].INT(Frc)
47        41     -              Num[i]-(Num[i].a[i+1])
48     24 05     RCL 5          Recall a[i+1]
49     24 04     RCL 4          Recall Den[i]
50        61     ×              Den[i].a[i+1]
51     24 02     RCL 2          Recall Num[i-1]
52        51     +              Den[i+1]=Num[i-1]+Den[i].a[i+1]
53     24 04     RCL 4          Recall Den[i]
54     23 02     STO 2          Store it to Num[i-1] for next iteration
55        22     Rv             Get Den[i+1]
56     23 04     STO 4          Store Den[i+1] to become Den[i] for next iteration
57        34     CLX            Freeze stack
58     24 05     RCL 5          Get a[i+1]
59     24 03     RCL 3          Recall Num[i]
60        61     ×              Num[i].a[i+1]
61     24 01     RCL 1          Recall Den[i-1]
62        51     +              Num[i+1]=Den[i-1]+Num[i].a[i+1]
63     24 03     RCL 3          Recall Num[i]
64     23 01     STO 1          Store it to Den[i-1] for next iteration
65        22     Rv             Get Num[i+1]
66     23 03     STO 3          Store Num[i+1] to become Num[i] for next iteration
67     14 74   f PAUSE          Display Num[i+1] during 2 seconds
68     14 74   f PAUSE
69     24 04     RCL 4          Get Den[i+1]
70     14 74   f PAUSE          Display Den[i+1] during 2 seconds
71     14 74   f PAUSE
72        71     ÷              Compute Num[i+1]/Den[i+1]
73  14 11 09   f FIX 9          Set decimals to 9
74     14 74   f PAUSE          Display fractional approximation during 3 seconds
75     14 74   f PAUSE
76     14 74   f PAUSE
77     24 00     RCL 0          Recall Dec
78        41     -              Error=Approximation - Dec
79  14 12 09   f SCI 9          Set decimals to SCI 9
80     14 74   f PAUSE          Display error during 1 second
81     15 61   g x!=0           No more error ?
82     13 09     GTO 9          No, loop to step 36 for next approximation
83  15 13 03   g LBL 3          * Last approximation routine entry *
84  14 11 00   f FIX 0          Set decimals to 0
85     24 04     RCL 4          Recall Den[i] to Y
86     24 03     RCL 3          Recall Num[i] to X
87     15 12   g RTN            End of routine
```

## Register Use

``` R0 = ab (LCM) | Dec
R1 = Numi-1
R2 = Deni-1 R3 = Numi
R4 = Deni
R5 = INT(Dec/Deni)
```