decimal to fraction

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]

Robert, I did notice ,that in the Farey sequence routine I posted, the max denominator test failed, but otherwise the method was giving me the same results as the other routines. I converted the Farey sequence routine from some Python code that I found, and may have made an error in the conversion. As I previously mentioned, I didn’t test it exhaustively. I’ll have another look at it.

The reason why I originally adopted the continued fraction method was that it appeared to work better than other methods when the input value is known to have an exact fractional value, and I was working with those kinds of numbers. For arbitrary numbers the other methods may work better.

A good way to test efficiency of decimal to fraction conversion routines is to use irrational numbers, which by definition cannot be represented exactly by a fraction. These tend to require a lot more iterations.

Examples:
? = 3.154159265358979…
e = 2.718281828459…
?2 = 1.414213562373…
?3 = 1.732050807569…
golden ratio = (1+?5)/2 = 1.618033988750…

Weaver, I will be interested if you can get a working algorithm using Farey that does not miss some “better” solutions.

I found two sites on the web that claimed to be able to pull this off using Farey Sequences to avoid having to do an exhaustive search.

Ultimately the author of this site admitted that his algorithm was faulty:
https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/

This is from the Python Cookbook. I took this code and translated the Python into Xojo but I found problems here as well.
There was one bug in the code that I corrected. But I still could not get this to always get the best approximation under some particular denominator size. There is some possibility that I screwed up the translation from Python so take my conclusions with a grain of salt. Currently, I think that if you really want the best fraction with a denominator under a given size, you should use exhaustive search.

In my testing, I have found no errors in the “improved” Jim McKay code. I would prefer an algorithm that uses the size of the denominator as a stopping point rather than “accuracy”. But I could not get the Jim McKay code to fail. It is not super efficient, but it is more efficient than the exhaustive search. The original Weaver algorithm is very efficient but it will miss some “best” solutions. The code below from the Python Cookbook is very efficient but again it will miss some “best” solutions.

Currently, I think that if you really want the best fraction with a denominator under a given size, you should use exhaustive search.

https://www.oreilly.com/library/view/python-cookbook/0596001673/ch17s17.html

Here is my translation into Xojo of the code from Python Cookbook

[code]Public Function FareyFraction(decimal As Double, maxDenominator As Integer = 10000) as String

// DESCRIPTION: Adapted from Python code: Python Cookbook by David Ascher, Alex Martelli

Dim numerator, denominator As Integer
Dim lower0, lower1 As Integer
Dim upper0, upper1 As Integer
If maxDenominator < 2 Or maxDenominator > 100000 Then maxDenominator = 10000 // keep things reasonable

Dim sgn As String = Mid ("- ", Sign (decimal) + 2, 1) // either a space or a minus
decimal = Abs (decimal)

Dim mediant0, mediant1 As Integer

lower0 = 0
lower1 = 1
upper0 = 1
upper1 = 0

Do

mediant0 = lower0 + upper0
mediant1 = lower1 + upper1

If decimal * mediant1 > mediant0 Then
  
  If maxDenominator < mediant1 Then
    Return sgn + Str (upper0) + "/" + Str (upper1)
    Exit
  End If
  
  lower0 = mediant0
  lower1 = mediant1
  
ElseIf decimal * mediant1 = mediant0 Then
  
  If maxDenominator >= mediant1 Then
    Return sgn + Str (mediant0) + "/" + Str (mediant1)
    Exit
  End If
  
  If lower1 < upper1 Then
    Return sgn + Str (lower0) + "/" + Str (lower1)  // debug 04/05/19 1833 * * * * * * * * *
    Exit 
  Else
    Return sgn + Str (upper0) + "/" + Str (upper1) // debug 04/05/19 1833 * * * * * * * * *
    Exit
  End If
  
Else 
  
  If maxDenominator < mediant1 Then
    // I believe an error in code from Python Cookbook which always returned lower0/lower1 here
    // it is possible that upper is within the selected bounds
    // of of these two has to be true I believe. In this algorithm, upper need not be greater than lower rrl
    If upper1 <= maxDenominator And upper1 > lower1 Then
      Return sgn + Str (upper0) + "/" + Str (upper1)
    End If
    If lower1 <= maxDenominator And lower1 > upper1 Then
      Return sgn + Str (lower0) + "/" + Str (lower1)
    End If
    
    MsgBox ("Error") // As I understand code, this should never happen
    Exit
    
  End If
  
  upper0 = mediant0
  upper1 = mediant1
  
End If

Loop

End Function[/code]