Programs: 
BESTFRAC 

Version: 
2.0, 1 August 2001 

Description: 
This program finds the best fraction approximation of a specified number where the denominator of the fraction has at most a specified number of digits. 

Compatibility: 


Other programs 
None 
A rational number is the quotient of two integers. An irrational number is a number that is not rational. The rational numbers are dense in the real numbers. This means that for any real number, there are rational numbers that are arbitrarily close to the real number. Therefore, any number of interest can be approximated by some rational number.
For example, the best approximation to the number π with a single digit in the denominator is 22/7; this matches π to three digits. A much better approximation is 355/113. This latter value is the best approximation to π with up to three digits in the denominator, and matches π to seven digits. There is no better approximation to π where the denominator has up to four digits.
This program finds the rational number closest to a specified number, where the denominator of the rational number has at most a specified number of digits.
Karl Ove Hufthammer’s APPFRAC program, which has a somewhat similar function, is available on Roy Maclean’s Casio Graphic Calculator Programming Guide and Other Info site. APPFRAC quickly generates high accuracy fractional approximations, but I do not know of any guarantee that it will generate the best approximation where the denominator has at most a specified number of digits. However, if you are looking for good quality fractional approximations, as opposed to “best” with a given denominator (and hence numerator) size, you likely want APPFRAC rather than this program.
Load and run the program BESTFRAC. The program displays the prompts:
Number? Denom digits?
Enter the number to be approximated and the maximum number of digits in the denominator of the approximating rational. The program will compute the best approximating fraction and will reply:
Numerator:
followed by the numerator of the rational number, and:
Denominator:
followed by the denominator of the rational number.
As the program tests all possible denominators between 1 and 10^{n} (where n is the maximum number of digits in the denominator), finding the best rational approximation with a large number of digits in the denominator may take a long time. Approximate timings are 10 seconds for two digits, 90 seconds for three digits, and 15 minutes for four digits.
The programs are available as a text file with .CAT contents, or may be entered as shown below. A semicolon (“;”) marks the beginning of a comment, which is not to be entered into the calculator. Remember that these programs are copyrighted; see the copyright issues page for limitations on redistribution.
Program BESTFRAC (184 bytes):
; Program BESTFRAC ; ; Description: ; Finds the minimumerror rational approximation n/m to a given ; value where the denominator m has at most a specified number of ; digits. ; ; Variables: ; A: the number to be approximated ; B: the numerator of the best fraction found so far ; C: the denominator of the best fraction found so far ; D: the error of the best fraction found so far ; E: the numerator of the fraction currently being tested ; F: the denominator of the fraction currently being tested ; G: the error of the fraction currently being tested ; H: the upper limit on the denominator of the fraction ; ; Calling sequence: ; None; main program ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; None. ; ; Side effects: ; None. ; ; Symbols: ; > is assignment arrow ; 10^x is ten to the xth power operator ; < is less than relational ; _ is display triangle "Number"?>A ; Get number to approximate Abs A>A ; Make it positive "Denom digits"?>H ; Get number of digits in denominator 10^xAbs Int H>H ; Get maximum denominator value 1>D ; Initialize the error to be something bigger than ; any possible error For 1>F To H ; Loop through all possible denominators Int FA>E ; Try numerator that is too small Abs (AE/F)>G ; Find error of fraction If G<D ; Test if fraction error better than current best Then E>B ; If so, save current numerator, F>C ; denominator, and G>D ; error IfEnd ; [End of test of fraction error] E+1>E ; Try numerator that is too big Abs (AE/F)>G ; Find error of fraction If G<D ; Test if fraction error better than current best Then E>B ; If so, save current numerator, F>C ; denominator, and G>D ; error IfEnd ; [End of test of fraction error] Next ; [End of loop through all possible denominators] "Numerator" ; Label numerator report B_ ; Report numerator of best fraction "Denominator" ; Label denominator report C ; Report denominator of best fraction
[ Previous page  Top of page  Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.