How to Find the Best Rational Approximation to a Real Number (01/2007)
A common request I (Dave Ashley) receive is for a utility to calculate best rational approximations using the continued fraction algorithm explained in a paper I wrote and also in the book I'm working on. Best rational approximations of this type are sometimes useful in microcontroller work.
The console-mode utility supplied on this page will perform the necessary calculations. The underlying mathematics are described in the documents linked to from this page.
The utility was created using Microsoft Visual C++ 6.0, and has no external dependencies (no .DLL dependencies, for example). It should run on any Windows 95 or later system.
The screen snapshot below shows the utility being used to find the best rational approximation to p (or actually, to 3.14159265359, since p is irrational) with numerator not exceeding 65,535 and denominator not exceeding 32,767. The screen snapshot shows that this best rational approximation is 65,298/20,785.
The underlying algorithms are O(log N) and an arbitrary-precision integer library is used, so they should work for any practical case.
This standalone utility and other supporting documents can be downloaded from the links in the table below.
| Download Link | Description | File Size And MD5 |
| cfbrapab.exe | Windows utility to calculate best rational approximations. | Size: 81,920 MD-5 02c8738054c23445a69bd0d675ceca0a |
| paper_brap_detailed.pdf | Detailed paper explaining the mathematical basis of best rational approximation. (Note: this paper was never published, and copyrights do not apply.) | Size: 273,133 MD-5: fea545ffe55e1c1ef639f93eb844e0bb |
| paper_brap_reduced.pdf | Less detailed paper explaining how to calculate best rational approximations. (Note: this paper was never published, and copyrights do not apply.) | Size: 152,959 MD-5: cdd7b25e94c4c304315002eb858a125d |
| book_c4_c5.pdf | Chapters 4 (Farey Series) and 5 (Continued Fractions) of book, under construction. This document gives much more detail about the mathematical basis of best rational approximation. (Note: the copyright status of the book is uncertain. For the present time, no copyrights apply.) | Size: 631,559 MD-5: 87e410eb524ad5dd0e8011f5567f9e30 |
Other notes:
This web page is maintained by webmaster@dtashley.com. Sound credit: The Austin Powers series of films. This sound is #31, randomly selected from the 76 sounds that are suitable for this page. A list of all 113 sounds in the database (some unsuitable for this page) can be found here. Local time on this server (at the time the page was served) is 6:58:19 am on September 9, 2010.