closestFraction.frink

Download or view closestFraction.frink in plain text format


// This program uses the Farey series to calculate the closest fraction
// to a given floating-point number.
//
// See p. 152, Conway and Guy, _The Book of Numbers_
//
// A Farey series consists of the proper fractions in order of magnitude, such
// as:
//
//  First Farey series:
//  0/1,                1/1
//
//  Second Farey series:
//  0/1,      1/2,      1/1
//
//  Third Farey series:
//  0/1, 1/3, 1/2, 2/3, 1/1
//
// As you can see, one Farey series (or a part of it) can be constructed
// by knowing the previous Farey series and inserting the next set of fractions
// into the series.

// It successively finds the next closest term between a/c and b/d by forming
// the mediant, (a+b)/(c+d).  This is known to give the next fraction between
// the two numbers.  This basically results in an efficient binary search for
// the closest fraction.  This search procedure, however, is probably not as
// efficient as the process in continuedFraction.frink for finding
// successively-better closest fractions.

closestFraction[n, maxDenom] :=
{
   lower = floor[n]
   upper = ceil[n]

   do
   {
      mediant = (numerator[lower] + numerator[upper])/(denominator[lower] + denominator[upper])

      // Would this cause the denominator to be too large?
      if denominator[mediant] > maxDenom
      {
         elow =  n-lower
         ehigh = upper-n
         if ehigh > elow
            closer = lower
         else
            closer = upper
         return [lower, upper, closer]
      }
      
      if (n > mediant)
         lower = mediant
      else
         upper = mediant

   } while (n != lower and n != upper)

   // This is a sign that either we found an exact fraction that matches
   // the desired number, or if n is transcendental, that we're not working
   // with enough precision to distinguish the fraction from the floating-point
   // approximation.
   println["Fell through."]
   elow =  n-lower
   ehigh = upper-n
   if ehigh > elow
      closer = lower
   else
      closer = upper
   return [lower, upper, closer]
}


Download or view closestFraction.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 19944 days, 13 hours, 45 minutes ago.