MoHPThe 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

References

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)

GTOGo back to the software library
GTOGo back to the main exhibit hall