# decimal to fraction

Trying to find a method to convert a decimal number (<1) to its most appropriate fraction respresentation

• 0.25 = 1/4
• 0.625 = 5/8
• 0.14285714 = 1/7

etc.

my original idea had been to convert to (x/10000) and simplfy… but that didn’t work if the numerator was a prime number (as in 2/3, came back as 3333/5000)
the fraction does not need to be 100% exact but 99% at least, and it doesn’t have to be a super fast algorithm

the only other method that comes to mind is brute force

``````dim delta as double = 9999
for num=2 to 1000
dom=value*num
diff=abs((dom/num)-value)
if diff<delta then
tempDom=dom
tempNum = num
diff=delta
if diff=0 then exit
end if
next num
frac=str(tempDom)+"/"+str(tempnum)``````

Just consider your decimal divided by 1

0.25/1

Make the decimal whole multipling both parts, use the number of ceros as decimal places you have (Use a “MaxPlaces” limiter, truncate to that many places, )

(0.25100)/(1100)
25/100

Get a function to find the Greatest Common Factor and divide the top and bottom by it . (you can use the Euclidean algorithm)

25/100
Greatest Common Factor = 25
(25/25)/(100/25)
1/4

a method that DOES NOT WORK for fractions who’s numerator is a PRIME #

1/7 comes back 357/2500

I live for these sort of challenges!

Try this:

[code]Public Function CalcFraction(value as Double, accuracy as Double = .001) as string
dim numeratorOf100 as Double=100/(value*100)
dim numerator,denominator,error as double

do

``````numerator=numerator+1
denominator=numeratorOf100*numerator
error=abs(numerator/round(denominator)-value)
``````

loop until error<=accuracy

Return str(round(numerator))+"/"+str(round(denominator))
End Function
[/code]

Let me know if it fails anywhere. You can adjust accuracy to your liking.

You are not Calculating the Greatest Common Factor:

1 and 7:

The factors of 1 are: 1
The factors of 7 are: 1, 7
Then the greatest common factor is 1.

(1/1)/(7/1) = 1/7

Before Jim responded, I played with this problem. I went to StackOverflow where a Python solution was provided. I translated this into Xojo and present it here. I do not know if has any advantage over Jim’s solution and it seems slightly more complex. During my limited testing, the results were the same. Anyway, since I went to the bother, I decided to post my solution here should anyone find it better under some circumstance. You can pass by reference numerator and denominator as integers variables to the function which will determine their value.

[code]Public Sub FloatToFraction(ByRef numerator As Integer, ByRef denominator As Integer, x As Double, accuracy As Double = .001)
Dim n As Integer = Xojo.Math.Floor(x)
x = x - n
If x < accuracy Then
numerator = n
denominator = 1
ElseIf (1 - accuracy) < x Then
numerator = n + 1
denominator = 1
Else
// The lower fraction is 0/1
Dim lower_n As Integer = 0
Dim lower_d As Integer = 1
// The upper fraction is 1/1
Dim upper_n As Integer = 1
Dim upper_d As Integer = 1

``````Dim middle_n As Integer
Dim middle_d As Integer

Do
//  The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
middle_n = lower_n + upper_n
middle_d = lower_d + upper_d

If (middle_d * (x + accuracy)) < middle_n Then
//  middle is our new upper
upper_n = middle_n
upper_d = middle_d
ElseIf middle_n < ((x - accuracy) * middle_d) Then
//  middle is our new lower
lower_n = middle_n
lower_d = middle_d
Else
numerator = n * middle_d + middle_n
denominator = middle_d
Exit
End If
Loop
``````

End If

End Sub[/code]

My fraction calculator project that I linked to in your other thread already had this function in it. It uses the continued fraction algorithm, which is guaranteed to use the fewest possible iterations to produce either the exact fraction, or the most accurate fraction with a denominator no larger than a specified value.

```Public Function Dec2Fraction(decNum As Double, maxDenom As integer, fType As Boolean) as String 'Converts decimal number decNum to fraction 'with denominator no larger than maxDenom 'Returns either a simple (improper) or compound fraction according to value of fType 'Eg., 3.125 will return either "25/8" for fType = false, and "3 1/8" for fType = true dim p0 As Double = abs(decNum) dim sgn As string = mid("- ",Sign(decNum)+2,1) dim n As Double = p0 - floor(p0) 'fractional part of decNum dim p As Double = 1 dim deltaBest As Double = p0+p0 dim nBest,pBest,delta As Double = 0 dim whole,frac As String = "" if n=0 then return sgn+format(p0,"##################") while round(p/n)<=maxDenom n=1/n p=p*n n=n-Floor(n) delta=abs(round(p0*p)/round(p)-p0) if delta<deltaBest Then deltaBest=delta nBest=n pBest=p end if wend n=round(p0*pBest) p=round(pBest) 'Save the numerical value of the final result (for display or diagnostics) tempDouble=n/p if (fType and n>=p) or p=1 then whole=trim(format(floor(n/p),"##################"))+" " n=n mod p end if if n>0 then frac = trim(Format(n,"##################"))+"/"+trim(Format(p,"##################")) end if return sgn+whole+frac End Function ```

Actually this last alogrithm is “more” correct than the one Jim posted (sorry Jim)

as I test, I used 237/543 (0.4365641)

Jims method return a fraction of 55/126 [0.4365079)
Roberts method (per his app) returns 79/181 [0.4364641) …
which is in fact what 237/543 reduces to (divide by 3)

Robert, might I have your permission to include that method from your app into mine (credit give of course)

I like Weaver solution because providing a maximum denominator seems more straight forward in use than an “accuracy”. And I take his word for it that it is efficient.

tempDouble needs to be commented out or declared. It is there only for debugging

``tempDouble = n / p``

[quote=431358:@Robert Livingston]I like Weaver solution because providing a maximum denominator seems more straight forward in use than an “accuracy”. And I take his word for it that it is efficient.

tempDouble needs to be commented out or declared. It is there only for debugging

``tempDouble = n / p``

and nBest is never used either but those not withstanding it does meet my needs better (sorry Jim )

Yes, I forgot to remove that line. Thanks for catching it.

Dave you’re welcome to use the code.

This is an algorithm that I dug up from somewhere many years ago, and I can no longer remember the source. It is guaranteed to be exact, with the proviso that your input value and math operations have sufficient precision. I found that even with double precision, it’s possible due to round off error that the routine may overshoot by one iteration producing a less than optimum fraction. So I added code to save the best so far. This appears to solve the problem, and only requires one extra iteration.

In fairness to Jim (and Robert the Other: i.e. Me) The output of Jim’s algorithm will vary depending on the “accuracy” parameter. This “needs” to be the case, it is inevitable in the structure of the problem proposed. The more accuracy you demand, the more likely the fracture answer will have a large denominator.

In my own testing using 0.4365641 and varying degrees of “accuracy”:
.000001 -> 437/1001
.00001 -> 117/268
.0001 -> 31/71
.001 -> 7/16
.01 -> 3/7

Actually, I could never get Jim’s method to return 55/126 with the accuracy parameters I provided, but that is not the real issue.
The real issue is that Dave’s 0.4365641 is not a completely accurate representation of 237/543.

236/543 is not 0.43656410000 which is what Jim’s algorithm is struggling to achieve as the accuracy demand is increased.

A more accurate representation is: 0.43646408839
Now try that with an “accuracy” of .00001 with Jim’s algorithm and you will get the desired 79/181

But you are asking Jim’s algorithm to approximate 0.4365641 which is some distance from the actual value of 79/181
Note that 117/268 is a more accurate approximation of 0.4365641 than is 79/181
Note that 55/126 is a more accurate approximation of 0.4365641 than is 79/181

[quote=431356:@Dave S]Actually this last alogrithm is “more” correct than the one Jim posted (sorry Jim)

[/quote]
It does return the same 79/181 if accuracy is .000001, but after some more playing I did a revision. Now it’s pretty darn efficient and takes Numerator and Denominator byref so you can use them independently.

Give it a spin…
test app

Ok… to be fair… for my desired purpose Robert Weavers algoritim provides the results I desire…

Thanks to all for your input

Not wanting to beat a dead horse, but to address Robert Livingston’s comments, while the continued fraction algorithm is the fastest for converging to an exact value, it is possible that it may not give the most accurate value for a given maximum denominator value. This is because the size of the calculated denominator can grow rapidly, and therefore skip over a suitable fraction. There is another algorithm based on the Farey Sequence which doesn’t converge as fast, but will give a result with the smallest denominator for a given precision spec. That may be the algorithm that Robert Livingston found. I have another version of the Farey Sequence algorithm which allows you to specify both a precision value and a maximum denominator value. It gives the same results as in Robert’s last post. I have NOT tested this exhaustively.

```Public Function FareyFrac(dec As Double, dMax As Integer, prec As Double) as String 'Convert decimal to fraction using Farey Sequence method 'Input value is assumed to be positive dim whole As Integer = floor(dec) dim frac As Double = dec - whole dim k,xn As Integer = 0 dim xd,yn,yd As Integer = 1 dim ws As String = "" dim dmx As Integer = dMax if whole<>0 then ws=str(whole)+" " while true k = ceil((yn - frac*yd)/(frac*xd - xn)) dmx = dmx- k*xd if (dmx < 0) then k = k+ dmx\\xd yn = yn + k*xn yd = yd + k*xd else yn = yn+ k*xn yd = yd+k*xd xn = yn - xn xd = yd - xd end if dim xerr as double = xn/xd - frac dim yerr as double = yn/yd - frac if (dmx < 0) then 'Test for maximum denominator if (abs(xerr) < abs(yerr))then return ws+str(xn)+"/"+str(xd) else return ws+str(yn)+"/"+str(yd) end if end if 'Test for precision if (abs(xerr) <= prec) then return ws+str(xn)+"/"+str(xd) elseif (abs(yerr) <= prec) then return ws+str(yn)+"/"+str(yd) end if wend End Function ```

This is my function:

[code]Dim x As Double = Val(TextField1.Text)

dim tolerance as Double = 1.0E-6
dim h1 as Double = 1
dim h2 as Double = 0
dim k1 as Double = 0
dim k2 as Double = 1
dim b as Double = x

do
dim a as Double = floor(b)
dim aux as Double = h1
h1 = ah1+h2
h2 = aux
aux = k1
k1 = a
k1+k2
k2 = aux
b = 1/(b-a)
loop until abs(x-h1/k1) <= x*tolerance

Msgbox str(h1)+"/"+str(k1)
[/code]

Ciao!

``` if (dmx < 0) then 'Test for maximum denominator```
I am not sure why you would only test for maximum denominator when dmx<0
In any case:
In my implementation for an example case: 2/677 ~= 0.00295421
When I provide this Decimal and Max Denominator of 1000 and Precision of .000001

I get 3/1015. This misses the more accurate answer of 2/677 and it is returning a denominator larger than the designated 1000.

Marciano’s submission works in my testing and seems remarkably efficient. In my testing implementation, I made it into a function with the “tolerance” as a separate and thus adjustable parameter and returning a string.

Jim McKay’s second submission works well in my hands and also seems remarkably efficient. Fractions like 5/1 (whole numbers) result in NaN which I would take to be a bug.

The best way to convert a decimal number in a fraction is to use the continued fractions (take a look to the Wikipedia page ‘Continued fraction’).

My math is fairly weak but the Wikipedia page that Marciano points to is fascinating.
It seems that the Marciano algorithm uses continued fractions and is extremely quick in generating candidates for fractional approximations of decimal numbers.

If you modify his algorithm to show the intermediate results, it is fascinating (to me) and you can see how efficient it all is.

As an example use .123

Results each time his Do  Loop completes

0/1 1/8 7/57 8/65 23/187 123/1000

The first Weaver submission apparently also uses continued fractions, but it was not as transparent to me in terms of seeing intermediate results.
The second Weaver submission (Farley Sequence) is described as being a little slower, but more complete in terms of finding the smallest denominator fraction that meets the provided constraints. I could not get this one to work properly. Weaver points to a Wikipedia page on this topic which is also interesting.