closestFraction.frink

View or download 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]
}


View or download 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 17649 days, 5 hours, 36 minutes ago.