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