 The Museum of HP Calculators

# Greatest Common Divisor, Least Common Multiple, Decimal To Fraction for the HP-67

This program is Copyright © 1976 by Hewlett-Packard and is used here by permission. This program was originally published in the HP-67 Math Pac 1.

This program is supplied without representation or warranty of any kind. Hewlett-Packard Company 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.

 Factors and Primes Shift Label a^b->GCD a^b->LCM Dec->Frc ->Lst Frc Auto? Key A B C D E

## Overview

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). Optional outputs of this routine are the values of the integers s and t which satisfy the equation GCD(a,b) = sa + tb. 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 both share a common subroutine, LBL e.

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 l.

The algorithm is actually extended somewhat to allow calculation of s and t. Full details may be found in the reference below.

LCM(a,b) is found by

```                   ab
LCM(a,b) = --------
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 subtracting the original value, 0.33, from the value of this approximation. At this step the error is 3.333333300-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 after this step displaying 0.000000000. The last fraction generated can be recalled by pressing D.

## Equations

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

```                          1
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, and D0 = 0 by definition. The values for the ai may be found by the following algorithm:

Let Dec be the original decimal keyed in. Then a1 = INT(Dec). Let x1 = 1 and let y1 = FRAC(Dec). Then

```              ai+1 = INT (xi/yi)

xi+1 = yi

yi+1 = xi - ai+1yi
```

## Remarks

AUTO mode is available on the Decimal to Fraction routine.

## References

(GCD,LCM) D. E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, 1969.

(Decimal to fraction) Charles G. Moore, An Introduction to Continued Fractions, National Council of Teachers of Mathematics, 1964.

## Instructions

 Step Instructions Input Data/Units Keys Output Data/Units 1 Load side 1 and side 2. 2 For greatest common divisor, go to step 3; for least common multiple, go to step 5; for decimal to fraction, go to step 6. GCD 3 Key in integers a and b and find their greatest common divisor. a ENTER b A GCD(a,b) 4 (optional) Compute coefficients s and t such that GCD (a,b) = sa + tb. R/S s t LCM 5 Key in integers a and b and find their least common multiple. a ENTER b B LCM(a,b) DECIMAL->FRACTION 6 To allow automatic output of results, set AUTO mode. E 1.00 7 To cancel AUTO Mode later. E 0.00 8 Key in a decimal value and find successive fractional approximations (i = 1, 2, ...). Dec C Numi Deni Numi/Deni Errori 9 To re-output last fractional approximation (Errorn shown in display only). D Numn Denn Numn/Denn Errorn

## Example 1

Find the greatest common divisor of 406 and 266. Find also the constants s and t.

```Keystrokes                     Outputs
406 ENTER 266 A                14.00 *** (GCD)
R/S                             2.00 *** (s)
-3.00 *** (t)
```

That is (2 x 406) + (-3 x 266) = 14.

## Example 2

Find the least common multiple of 406 and 266.

```Keystrokes                     Outputs
406 ENTER 266 B              7714.00 *** (LCM)
```

## Example 3

A gear designer wants to reduce the angular speed of a rotating shaft by a factor of 0.45647. He will do this by having a gear on the driven shaft mesh with a smaller gear called a pinion, on the drive shaft. If Ng and Np are the number of teeth on the gear and pinion respectively, then the reduction in speed is by a factor of Np/Ng. Find the best values for Np and Ng subject to the constraint that neither value exceed 100. Do not use AUTO mode.

```Keystrokes                     Outputs
.45647 C                           1.  (Num1)
R/S                                2.  (Den1)
R/S                       0.500000000  (Frac1)
R/S                    4.353000000-02  (Error1)

R/S                                5.  (Num2)
R/S                               11.  (Den2)
R/S                       0.454545455  (Frac2)
R/S                   -1.924545500-03  (Error2)

R/S                               21.  (Num3)
R/S                               46.  (Den3)
R/S                       0.456521739  (Frac3)
R/S                   5.1739100000-05  (Error3)

R/S                              173.  (Num4 > 100, so stop)
```

The best values are thus Np = 21, Ng = 46.

## Example 4

Generate the series of fractional approximations to . Use AUTO mode.

```Keystrokes                     Outputs
E                                  1.00   (AUTO set) C                                 3. ***
1. ***
3.000000000 ***
-1.415926540-01 ***

22. ***
7. ***
3.142857143 ***
1.264489000-03 ***

333. ***
106. ***
3.141509434 ***
-8.322000000-05 ***

355. ***
113. ***
3.141592920 ***
2.660000000-07 ***

104348. ***
33215. ***
3.141592654 ***
0.000000000 ***
```

## The Program

```LINE  KEYS
001  *LBL A     GCD
002   STO B     b
003   X<>Y
004   STO A     a
005   1
006   STO C
007   CLX
008   STO D
009   X=Y?      if b=0, list a as GCD
010   GTO 0
011   STO C
012   STO E     s<-x<-0
013   1
014   STO D
015   STO I     t<-y<-1
016  *LBL 9     Main loop.
017   GSB e
018   X=0?      If b = 0, list a as GCD
019   GTO 0
020   RCL I
021   RCL C     u<-s+yq
022   STO I     y<-s
023   RCL 9
024   x
025   +
026   STO C     s<-p
027   RCL E
028   RCL D
029   STO E     p<-t+xq
030   RCL 9
031   x         x<-t
032   +
033   STO D     t<-p
034   GTO 9     Loop again.
035  *LBL 0
036   RCL A     At end, a is GCD
037   X>0?
038   GTO 1     (a<0)
039   CLX       Load stack with
040   RCL D
041   CHS       t->Z
042   RCL C
043   CHS
044   RCL A     s->Y
045   CHS
046   GTO 2     GCD->X
047  *LBL 1
048   CLX
049   RCL D     (a>0)
050   RCL C
051   RCL A     t
052  *LBL 2     s
053   PRTX      GCD
054   R/S       Output Routine
055   roll dn
056   PRTX      (optional) print s, t.
057   roll dn
058   PRTX
059   PRT SPC
060   roll dn
061   roll dn
062   R/S
063  *LBL B     LCM
064   STO B     b
065   X<>Y
066   STO A     a
067   x
068   STO C     c = a x b
069   X=0?      IF c = 0 then LCM = 0
070   GTO 3
071  *LBL 8     Find LCM through iteration
072   GSB e
073   X!=0?
074   GTO 8     At end, a = GCD
075   RCL C
076   RCL A
077   ÷
078   ABS       LCM = | c / GCD |
079  *LBL 3
080   PRTX
081   PRT SPC
082   RTN
083  *LBL e     Common subroutine which finds GCD if iterated
084   RCL A     until b = 0
085   RCL A
086   RCL B
087   STO A
088   ÷
089   INT       g<- -INT(a/b)
090   CHS
091   STO 9     p<-a+bq = a mod b
092   RCL B     a<-b
093   x
094   +
095   STO B     b<-p
096   RTN
097  *LBL C     Decimal to fraction.
098   0         Initialize
099   STO A
100   STO D
101   roll dn
102   ENTER
103   STO E     RE<-Original Value.
104   1
105   STO B
106   STO C
107   SF 1
108  *LBL 7
109   FIX
110   DSP 0
111   ÷
112   LST X
113   ENTER
114   roll dn
115   X<>Y       ai
116   INT
117   STO I
118   x
119   -
120   RCL I
121   RCL C
122   x
123   RCL A
124   +         If Numi = 0, clear flag 1.
125   X=0?
126   CF 1
127   RCL C
128   STO A
129   roll dn
130   STO C
131   F1?       Output Numi.
132   GSB 5
133   CLX
134   RCL I
135   RCL D
136   x
137   RCL B
138   +
139   RCL D
140   STO B
141   roll dn
142   STO D
143   F1?       Output Deni.
144   GSB 5
145   RCL C
146   X<>Y
147   ÷
148   DSP 9
149   F1?       Output Numi/Deni.
150   GSB 5
151   RCL E     Error = Calc.-orig.value.
152   -
153   X=0?
154   GSB 6     If error = 0 halt.
155   X=0?
156   RTN
157   SCI
158   F1?       Output error.
159   GSB 5
160   F1?
161   GSB 6
162   roll dn
163   SF 1      Loop again.
164   GTO 7
165  *LBL D     Recall last fraction.
166   FIX
167   DSP 0
168   RCL C
169   GSB 5     Output Numi
170   RCL D
171   GSB 5     Output Deni
172   ÷
173   DSP 9     Output Numi/Deni
174   GSB 5
175   GSB 6
176   RCL E     Halt displaying error.
177   -
178   RTN       AUTO output.
179  *LBL 5
180   F0?       If F0 set, print and rtn.
181   PRTX
182   F0?
183   RTN       Else halt.
184   R/S
185   RTN
186  *LBL 6     Space if F0 set.
187   F0?
188   PRT SPC
189   RTN
190  *LBL E     AUTO toggle.
191   F0?
192   GTO 0
193   SF 0
194   1
195   RTN
196  *LBL 0
197   CF 0
198   0
199   RTN

```

```R9  q
A   a; Numi-1
B   b; Deni-1
C   s; Numi
D   t; Deni
E   x; Value
I   y; Temp
```