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 19966 days, 20 hours, 7 minutes ago.