Dec-Frac

Decimal to Fraction for the HP-41

Overview

-The 3 following programs find the best approximations of a decimal number x by a fraction p/q.
-"DF" & "DF2"  are based on continued fractions:

-We define   (pk)  &  (qk)   by  q -1 = 0 ,  q0 = 1 and  qk = yk.qk-1 + qk-2

where         yk = INT(xk)             with  x0 = x ,  xk+1 = 1/FRC(xk)     we have then   pk = RND(x.qk)   [ RND must be executed in FIX 0 ]

-"DF3" uses a more direct - but much slower - approach.

1°) Program#1

-This program displays the successive   pk/qk  and stops when the fraction is exactly equal to x
-Synthetic register M may be replaced by any data register.

Data Registers: /
Flag:   F29
Subroutines: /

-Line 29 is    append   /
-If you don't have an X-Functions module, delete lines 38-39
this will change the final outputs, but not the displayed fractions.

 01  LBL "DF" 02  SIGN 03  0 04  LASTX 05  ENTER^ 06  LBL 01 07  X<> L     08  FRC 09  1/X 10  INT 11  R^ 12  ST* Y 13  X<> T 14  ST+ Y 15  X<> L     16  RDN 17  STO M    18  X<>Y 19  ST* Y 20  X<>Y 21  FIX 0 22  CF 29 23  RND 24  R^ 25  SIGN 26  X<> M     27  CLA 28  ARCL Y 29  "~/" 30  ARCL X 31  FIX 4 32  SF 29 33  AVIEW 34  ST/ Y 35  RDN 36  X#Y? 37  GTO 01     38  R^  39  ANUM  40  END

( 67 bytes / SIZE 000 )

 STACK INPUTS when AVIEWs OUTPUTS T / qk-1 qn-1 Z / x x Y / pk qn X x qk pn

Examples:

a)  PI  XEQ "DF"  the hp-41 successively displays  "22/7"  "333/106"   "355/113"   "104348/33215"

-When the program stops,  X-register = 104348  &  Y-register = 33215

b) 1  E^X  R/S  >>>  "3/1"  "8/3"  "11/4"  "19/7"  "87/32"  "106/39"  "193/71"  "1264/465"  "1457/536"
"2721/1001"  "23225/8544"  "25946/9545"  "49171/18089"  "173459/63812"

and eventually,  X = 173459  &  Y =  63812

-Some numbers produce many continued fractions:
-A famous example is the golden ratio phi = (1+sqrt(5))/2   "DF" displays 22 fractions before it stops!
-The last one is 75025/46368

-If you set flag F21, the calculator will stop at each AVIEW
-The numerators are then in Y-register and the denominators in X-register
-At the end, X = the numerator, Y = the denominator.

2°) Program#2

-The following routine stops when the rounded  difference ( x - p/q )  equals 0 in the current display format.
-Synthetic registers M N O P may be replaced by any data registers.

Data Registers: /
Flags: /
Subroutines: /

-Line 04 may be replaced by RCLFLAG
-Line 28 may be replaced by STOFLAG

 01  LBL "DF2" 02  STO M 03  STO N      04  RCL d  05  STO O 06  CLST 07  SIGN 08  ENTER^ 09  LBL 01 10  X<> N      11  FRC 12  1/X 13  STO N 14  INT 15  RCL Y 16  * 17  R^ 18  + 19  RCL M      20  RCL Y 21  * 22  FIX 0 23  RND 24  STO P 25  RCL Y 26  / 27  RCL O      28  STO d  29  CLX 30  RCL M 31  - 32  RND 33  X#0? 34  GTO 01 35  X<> M      36  X<> L 37  STO Z 38  X<> P 39  CLA 40  END

( 68 bytes / SIZE 000 )

 STACK INPUTS OUTPUTS T / qn-1 Z / pn/qn - x Y / qn X x pn L / x

Examples:

FIX 6   PI    XEQ "DF2"  >>>>   355   RDN  113   RDN   2.66 E-7   whence  PI ~ 355/113  and   355/113 - PI  =  2.66 E-7
FIX 6   1    E^X    R/S    >>>>  2721  RDN  1001  RDN  -1.10 E-7   whence  e ~  2721/1001 and  2721/1001 - e = -1.1 E-7

T = the next to last denominator
The decimal number x is saved in L-register.

3°) Program#3

-The continued fractions give the most interesting results, and moreover, very fast.
-However, occasionaly, you might need to know the best fractional approximation p/q of a ( positive ) real x where q is between 2 given integers  q1 & q2
-The program hereunder will give you the answer, but not very fast if q is "great"

Data Registers:   R00 = x   R01 = p    R03 = | x - p/q |       R05 = q2
R02 = q     R04 = q1 , 1+q1 , ..... , q2
Flags: /
Subroutines: /

 01  LBL "DF3" 02  STO 00      03  X<>Y 04  STO 05 05  1 06  STO 03 07  R^ 08  LBL 01 09  STO 04 10  RCL 00 11  * 12  INT 13  ENTER^ 14  ENTER^ 15  SIGN 16  LASTX 17  ST+ Y 18  RCL 04     19  ST/ Z 20  / 21  RCL 00 22  ST- Z 23  - 24  ABS 25  X<=Y? 26  GTO 02     27  X<>Y 28  ISG Z 29  LBL 02 30  RCL 03 31  X<=Y? 32  GTO 03 33  X<>Y 34  STO 03 35  R^ 36  STO 01 37  RCL 04     38  STO 02 39  LBL 03 40  RCL 05 41  RCL 04 42  1 43  + 44  X<=Y? 45  GTO 01 46  RCL 03     47  RCL 02 48  RCL 01 49  END

( 64 bytes / SIZE 006 )

 STACK INPUTS OUTPUTS Z q1 | x -  p/q | Y q2 q X x p

-We must have  x > 0  and  0 < q1 <= q2

Example:

50   ENTER^
100  ENTER^
PI   XEQ "DF3"  >>>>  p = 311      ( execution time = 45 seconds )
RDN   q = 99
RDN   1.79 E-4    so  311/99  approximates PI with an error of 1.79 E-4 in magnitude.

-This approximation is better than 22/7 but of course less accurate than 333/106