Previous page Next page Navigation bar

Programs

Mathematics Programs

Best Fraction Approximation

Summary

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:

Is compatible CFX-9850G

Compatible with CFX-9850G

Is compatible FX-7400G

Compatible with FX-7400G

Other programs
required:

None

Detailed Description

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.

Other Programs

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.

Usage

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 10n (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.

Program Source

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 minimum-error 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 x-th 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 (A-E/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 (A-E/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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Index

Linkage Conventions

Mathematics

Index

Factorization

Bisection

Newton’s Method

Complex Zeroes

Best Fraction Approximation

Pseudorandom Numbers

Romberg Integration

First Degree ODE

Rounding

Permutations

Finance

Physics

Utility

Tutorial

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data