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)
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
[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
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
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
[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.
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
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 = ak1+k2
k2 = aux
b = 1/(b-a)
loop until abs(x-h1/k1) <= x*tolerance
I have had trouble with Weaver’s dead horse Farey Fraction submission.
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.
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.
)