For those that enjoy flogging dead horses.
Weaver alludes to the fact that the “continued fraction” approach is efficient but skips some candidates. The “Farley Sequence” approach might be more exhaustive but is slower. I could not get Weaver’s “Farley Sequence” version to work, so I wrote the “simple man’s” algorithm.
The algorithm below is very inefficient but exhaustive. And it is “simple” in terms of its understandability without any real knowledge of mathematics beyond grade school required. If you strictly wanted to find the “best” answer for a denominator under a particular value this would give you a best answer. It basically tests every denominator in the range. I found it interesting to compare the candidates of this exhaustive search with the candidates of the “continued fraction” approach.
All the intermediate values of the “continued fraction” approach will be included in the exhaustive list. For their particular denominator, the “continued fraction” values are better than any provided by a smaller denominator. Looking at denominators less than 1000 with three examples.
The exhaustive list will contain other values, these additional values are in bold.
Consider .1234567
Continued Fraction
0/1; 1/8; 9/73; 10/81
Exhaustive
0/1; 1/5; 1/6; 1/7; 1/8; 5/41; 6/49; 7/57; 8/65; 9/73; 10/81
If you specifically wanted the “best” value for a denominator under 50, you would have to look to the exhaustive list and find 6/49
Consider .1234
Continued Fraction
0/1; 1/8; 9/73; 10/81; 19/154; 29/235; 106/859
Exhaustive
0/1; 1/5; 1/6; 1/7; 1/8; 5/41; 6/49; 7/57; 8/65; 9/73; 10/81; 19/154; 29/235; 77/624; 106/859
The best value for a denominator under 700 would be 77/624 rather than the candidate from the Continued Fraction list: 29/235
Consider .2345
Continued Fraction
0/1; 1/4; 3/13; 4/17; 15/64; 19/81; 34/145; 87/371
Exhaustive
0/1; 1/3; 1/4; 2/9; 3/13; 4/17; 11/47; 15/64; 19/81; 34/145; 53/226; 87/371
[code]Public Function Dec2FractionRRL(decimal As Double, maxDenominator As Integer, precision As Double = .001) as String
Dim floorNumerator As Integer
Dim ceilingNumerator As Integer
Dim bestNumerator As Integer
Dim bestDenominator As Integer
Dim smallestError As Double = 100
Dim floorError As Double
Dim ceilingError As Double
Dim multipleCandidate As String
Dim foundBetter As Boolean
Dim counter As Integer
For denom As Integer = 1 To maxDenominator
counter = counter + 1
floorNumerator = Floor (decimal * denom)
ceilingNumerator = floorNumerator + 1
floorError = Abs (decimal - floorNumerator / denom)
ceilingError = Abs (decimal - ceilingNumerator / denom)
If floorError < smallestError Then
smallestError = floorError
bestNumerator = floorNumerator
bestDenominator = denom
foundBetter = True
End If
If ceilingError < smallestError Then
smallestError = ceilingError
bestNumerator = ceilingNumerator
bestDenominator = denom
foundBetter = True
End If
If foundBetter Then
multipleCandidate = multipleCandidate + Str (bestNumerator) + "/" + Str (bestDenominator) + " "
foundBetter = False
End If
Next denom
// Return Str (bestNumerator) + “/” + Str (bestDenominator)
Return Str (counter) + ": " + multipleCandidate
End Function[/code]