The Museum of HP Calculators
The Museum of HP Calculators
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.
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 subtracting 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
| 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 common multiple: |
a | ENTER↑ | a |
| b | GSB 1 | LCM(a,b) | ||
| 5 | Decimal to Fraction Key in a decimal 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 |
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 π.
KEYSTROKES OUTPUTS COMMENTS
g π 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
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 R↓ 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 R↓ 10 22 R↓ 11 22 R↓ 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 R↓ 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 R↓ 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 R↓ 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 R↓ 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 75 14 74 f PAUSE during 3 seconds 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 approx. 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
R0 = ab (LCM) | Dec R1 = Numi-1 R2 = Deni-1 R3 = Numi R4 = Deni R5 = INT(Dec/Deni)
Go back to the software library