[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

real to rational

Does anyone have an algorithm that returns a rational approximation for a
real number?

Many years ago, I saw a very simple iterative algorithm that ran on a HP
desktop calculator.  For example, with an input of pi, the first iteration
might have given a numerator of 22 and a denominator of 7.  The next
iteration might give 157/50, etc.  Each iteration gave a more accurate
approximation of the real, with larger and larger numerators and
denominators.  The approximations were better than just chopping off
digits:  3/1, 31/10, 314/100  etc.

My use for the algorithm would be to avoid floats in repetitive
calculations.  For coordinate transformations, for example, it is
convenient to calculate the rotation matrix using trig functions.  But
then, I would like to convert the results to rationals (with the numerator
and denominator separated) so that many points can be scaled and plotted
quickly using integer arithmetic. {A good example of the integer arithmetic
is the muldiv function (a*b/c) in thermometer.lisp, MCL2 examples folder. -
Thanks to Bill St. Clair.}

David S. Bright                        bright@enh.nist.gov  
Microanalysis Research Group                                   
National Institute of Standards & Technology (NIST, formerly NBS)
Gaithersburg, MD 20899