The Museum of HP Calculators The Museum of HP Calculators
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 |
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:
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.
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
AUTO mode is available on the Decimal to Fraction routine.
(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.
| 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 |
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.
Find the least common multiple of 406 and 266.
Keystrokes Outputs 406 ENTER↑ 266 B 7714.00 *** (LCM)
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.
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 ***
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 × 025 + 026 STO C s←p 027 RCL E 028 RCL D 029 STO E p←t+xq 030 RCL 9 031 × 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 R↓ 056 PRTX (optional) print s, t. 057 R↓ 058 PRTX 059 PRT SPC 060 R↓ 061 R↓ 062 R/S 063 *LBL B LCM 064 STO B b 065 X⇔Y 066 STO A a 067 × 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 × 094 + 095 STO B b←p 096 RTN 097 *LBL C Decimal to fraction. 098 0 Initialize 099 STO A 100 STO D 101 R↓ 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 R↓ 115 X⇔Y ai 116 INT 117 STO I 118 × 119 - 120 RCL I 121 RCL C 122 × 123 RCL A 124 + If Numi = 0, clear flag 1. 125 X=0? 126 CF 1 127 RCL C 128 STO A 129 R↓ 130 STO C 131 F1? Output Numi. 132 GSB 5 133 CLX 134 RCL I 135 RCL D 136 × 137 RCL B 138 + 139 RCL D 140 STO B 141 R↓ 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 R↓ 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
Go back to the software library
Go back to the main exhibit hall