# closestFraction.frink

``` // 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] } ```

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 18868 days, 2 hours, 14 minutes ago.