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   (p_k)  &  (q_k)   by  q _-1 = 0 ,  q₀ = 1 and  q_k = y_k.q_k-1 + q_k-2

   where         y_k = INT(x_k)             with  x₀ = x ,  x_k+1 = 1/FRC(x_k)     we have then   p_k = RND(x.q_k)   [ RND must be executed in FIX 0 ]

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

1°) Program#1
 

-This program displays the successive   p_k/q_k  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  q₁ & q₂
-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 = q₂
                                             R02 = q     R04 = q₁ , 1+q₁ , ..... , q₂
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 < q₁ <= q₂

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