# 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 18114 days, 12 hours, 46 minutes ago.