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 20145 days, 18 hours, 28 minutes ago.