Algorithm for simplifying decimal to fractions
C#.NetAlgorithmMathC# Problem Overview
I tried writing an algorithm to simplify a decimal to a fraction and realized it wasn't too simple.
Write 0.333333... as 1/3 for example.
Or 0.1666667, which is 1/6.
Surprisingly I looked online and all the codes I found where either too long, or wouldn't work in some cases. What was even more annoying was that they didn't work for recurring decimals. I was wondering however whether there would be a mathematician/programmer here who understands all the involved processes in simplifying a decimal to a fraction. Anyone?
C# Solutions
Solution 1 - C#
The algorithm that the other people have given you gets the answer by calculating the http://en.wikipedia.org/wiki/Continued_fraction">Continued Fraction of the number. This gives a fractional sequence which is guaranteed to converge very, very rapidly. However it is not guaranteed to give you the smallest fraction that is within a distance epsilon of a real number. To find that you have to walk the http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree">Stern-Brocot tree.
To do that you subtract off the floor to get the number in the range [0, 1), then your lower estimate is 0, and your upper estimate is 1. Now do a binary search until you are close enough. At each iteration if your lower is a/b and your upper is c/d your middle is (a+c)/(b+d). Test your middle against x, and either make the middle the upper, the lower, or return your final answer.
Here is some very non-idiomatic (and hence, hopefully, readable even if you don't know the language) Python that implements this algorithm.
def float_to_fraction (x, error=0.000001):
n = int(math.floor(x))
x -= n
if x < error:
return (n, 1)
elif 1 - error < x:
return (n+1, 1)
# The lower fraction is 0/1
lower_n = 0
lower_d = 1
# The upper fraction is 1/1
upper_n = 1
upper_d = 1
while True:
# 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 x + error < middle
if middle_d * (x + error) < middle_n:
# middle is our new upper
upper_n = middle_n
upper_d = middle_d
# Else If middle < x - error
elif middle_n < (x - error) * middle_d:
# middle is our new lower
lower_n = middle_n
lower_d = middle_d
# Else middle is our best fraction
else:
return (n * middle_d + middle_n, middle_d)
Solution 2 - C#
(code improved Feb 2017 - scroll down to 'optimization'...)
(algorithm comparison table at the end of this answer)
I implemented btilly's answer in C# and...
- added support for negative numbers
- provide an
accuracyparameter to specify the max. relative error, not the max. absolute error;0.01would find a fraction within 1% of the value. - provide an optimization
Double.NaNandDouble.Infinityare not supported; you might want to handle those (example here).
public Fraction RealToFraction(double value, double accuracy)
{
if (accuracy <= 0.0 || accuracy >= 1.0)
{
throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1.");
}
int sign = Math.Sign(value);
if (sign == -1)
{
value = Math.Abs(value);
}
// Accuracy is the maximum relative error; convert to absolute maxError
double maxError = sign == 0 ? accuracy : value * accuracy;
int n = (int) Math.Floor(value);
value -= n;
if (value < maxError)
{
return new Fraction(sign * n, 1);
}
if (1 - maxError < value)
{
return new Fraction(sign * (n + 1), 1);
}
// The lower fraction is 0/1
int lower_n = 0;
int lower_d = 1;
// The upper fraction is 1/1
int upper_n = 1;
int upper_d = 1;
while (true)
{
// The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
int middle_n = lower_n + upper_n;
int middle_d = lower_d + upper_d;
if (middle_d * (value + maxError) < middle_n)
{
// real + error < middle : middle is our new upper
upper_n = middle_n;
upper_d = middle_d;
}
else if (middle_n < (value - maxError) * middle_d)
{
// middle < real - error : middle is our new lower
lower_n = middle_n;
lower_d = middle_d;
}
else
{
// Middle is our best fraction
return new Fraction((n * middle_d + middle_n) * sign, middle_d);
}
}
}
The Fraction type is just a simple struct. Of course, use your own preferred type... (I like this one by Rick Davin.)
public struct Fraction
{
public Fraction(int n, int d)
{
N = n;
D = d;
}
public int N { get; private set; }
public int D { get; private set; }
}
Feb 2017 optimization
For certain values, like 0.01, 0.001, etc. the algorithm goes through hundreds or thousands of linear iterations. To fix this, I implemented a binary way of finding the final value -- thanks to btilly for this idea. Inside the if-statement substitute the following:
// real + error < middle : middle is our new upper
Seek(ref upper_n, ref upper_d, lower_n, lower_d, (un, ud) => (lower_d + ud) * (value + maxError) < (lower_n + un));
and
// middle < real - error : middle is our new lower
Seek(ref lower_n, ref lower_d, upper_n, upper_d, (ln, ld) => (ln + upper_n) < (value - maxError) * (ld + upper_d));
Here is the Seek method implementation:
/// <summary>
/// Binary seek for the value where f() becomes false.
/// </summary>
void Seek(ref int a, ref int b, int ainc, int binc, Func<int, int, bool> f)
{
a += ainc;
b += binc;
if (f(a, b))
{
int weight = 1;
do
{
weight *= 2;
a += ainc * weight;
b += binc * weight;
}
while (f(a, b));
do
{
weight /= 2;
int adec = ainc * weight;
int bdec = binc * weight;
if (!f(a - adec, b - bdec))
{
a -= adec;
b -= bdec;
}
}
while (weight > 1);
}
}
Algorithm comparison table
You may want to copy the table to your text editor for full screen viewing.
Accuracy: 1.0E-3 | Stern-Brocot OPTIMIZED | Eppstein | Richards
Input | Result Error Iterations Iterations | Result Error Iterations | Result Error Iterations
======================| =====================================================| =========================================| =========================================
0 | 0/1 (zero) 0 0 0 | 0/1 (zero) 0 0 | 0/1 (zero) 0 0
1 | 1/1 0 0 0 | 1001/1000 1.0E-3 1 | 1/1 0 0
3 | 3/1 0 0 0 | 1003/334 1.0E-3 1 | 3/1 0 0
-1 | -1/1 0 0 0 | -1001/1000 1.0E-3 1 | -1/1 0 0
-3 | -3/1 0 0 0 | -1003/334 1.0E-3 1 | -3/1 0 0
0.999999 | 1/1 1.0E-6 0 0 | 1000/1001 -1.0E-3 2 | 1/1 1.0E-6 0
-0.999999 | -1/1 1.0E-6 0 0 | -1000/1001 -1.0E-3 2 | -1/1 1.0E-6 0
1.000001 | 1/1 -1.0E-6 0 0 | 1001/1000 1.0E-3 1 | 1/1 -1.0E-6 0
-1.000001 | -1/1 -1.0E-6 0 0 | -1001/1000 1.0E-3 1 | -1/1 -1.0E-6 0
0.50 (1/2) | 1/2 0 1 1 | 999/1999 -5.0E-4 2 | 1/2 0 1
0.33... (1/3) | 1/3 0 2 2 | 999/2998 -3.3E-4 2 | 1/3 0 1
0.67... (2/3) | 2/3 0 2 2 | 999/1498 3.3E-4 3 | 2/3 0 2
0.25 (1/4) | 1/4 0 3 3 | 999/3997 -2.5E-4 2 | 1/4 0 1
0.11... (1/9) | 1/9 0 8 4 | 999/8992 -1.1E-4 2 | 1/9 0 1
0.09... (1/11) | 1/11 0 10 5 | 999/10990 -9.1E-5 2 | 1/11 0 1
0.62... (307/499) | 8/13 2.5E-4 5 5 | 913/1484 -2.2E-6 8 | 8/13 2.5E-4 5
0.14... (33/229) | 15/104 8.7E-4 20 9 | 974/6759 -4.5E-6 6 | 16/111 2.7E-4 3
0.05... (33/683) | 7/145 -8.4E-4 24 10 | 980/20283 1.5E-6 7 | 10/207 -1.5E-4 4
0.18... (100/541) | 17/92 -3.3E-4 11 10 | 939/5080 -2.0E-6 8 | 17/92 -3.3E-4 4
0.06... (33/541) | 5/82 -3.7E-4 19 8 | 995/16312 -1.9E-6 6 | 5/82 -3.7E-4 4
0.1 | 1/10 0 9 5 | 999/9991 -1.0E-4 2 | 1/10 0 1
0.2 | 1/5 0 4 3 | 999/4996 -2.0E-4 2 | 1/5 0 1
0.3 | 3/10 0 5 5 | 998/3327 -1.0E-4 4 | 3/10 0 3
0.4 | 2/5 0 3 3 | 999/2497 2.0E-4 3 | 2/5 0 2
0.5 | 1/2 0 1 1 | 999/1999 -5.0E-4 2 | 1/2 0 1
0.6 | 3/5 0 3 3 | 1000/1667 -2.0E-4 4 | 3/5 0 3
0.7 | 7/10 0 5 5 | 996/1423 -1.0E-4 4 | 7/10 0 3
0.8 | 4/5 0 4 3 | 997/1246 2.0E-4 3 | 4/5 0 2
0.9 | 9/10 0 9 5 | 998/1109 -1.0E-4 4 | 9/10 0 3
0.01 | 1/100 0 99 8 | 999/99901 -1.0E-5 2 | 1/100 0 1
0.001 | 1/1000 0 999 11 | 999/999001 -1.0E-6 2 | 1/1000 0 1
0.0001 | 1/9991 9.0E-4 9990 15 | 999/9990001 -1.0E-7 2 | 1/10000 0 1
1E-05 | 1/99901 9.9E-4 99900 18 | 1000/99999999 1.0E-8 3 | 1/99999 1.0E-5 1
0.33333333333 | 1/3 1.0E-11 2 2 | 1000/3001 -3.3E-4 2 | 1/3 1.0E-11 1
0.3 | 3/10 0 5 5 | 998/3327 -1.0E-4 4 | 3/10 0 3
0.33 | 30/91 -1.0E-3 32 8 | 991/3003 1.0E-5 3 | 33/100 0 2
0.333 | 167/502 -9.9E-4 169 11 | 1000/3003 1.0E-6 3 | 333/1000 0 2
0.7777 | 7/9 1.0E-4 5 4 | 997/1282 -1.1E-5 4 | 7/9 1.0E-4 3
0.101 | 10/99 1.0E-4 18 10 | 919/9099 1.1E-6 5 | 10/99 1.0E-4 3
0.10001 | 1/10 -1.0E-4 9 5 | 1/10 -1.0E-4 4 | 1/10 -1.0E-4 2
0.100000001 | 1/10 -1.0E-8 9 5 | 1000/9999 1.0E-4 3 | 1/10 -1.0E-8 2
0.001001 | 1/999 1.0E-6 998 11 | 1/999 1.0E-6 3 | 1/999 1.0E-6 1
0.0010000001 | 1/1000 -1.0E-7 999 11 | 1000/999999 9.0E-7 3 | 1/1000 -1.0E-7 2
0.11 | 10/91 -1.0E-3 18 9 | 1000/9091 -1.0E-5 4 | 10/91 -1.0E-3 2
0.1111 | 1/9 1.0E-4 8 4 | 1000/9001 -1.1E-5 2 | 1/9 1.0E-4 1
0.111111111111 | 1/9 1.0E-12 8 4 | 1000/9001 -1.1E-4 2 | 1/9 1.0E-12 1
1 | 1/1 0 0 0 | 1001/1000 1.0E-3 1 | 1/1 0 0
-1 | -1/1 0 0 0 | -1001/1000 1.0E-3 1 | -1/1 0 0
-0.5 | -1/2 0 1 1 | -999/1999 -5.0E-4 2 | -1/2 0 1
3.14 | 22/7 9.1E-4 6 4 | 964/307 2.1E-5 3 | 22/7 9.1E-4 1
3.1416 | 22/7 4.0E-4 6 4 | 732/233 9.8E-6 3 | 22/7 4.0E-4 1
3.14... (pi) | 22/7 4.0E-4 6 4 | 688/219 -1.3E-5 4 | 22/7 4.0E-4 1
0.14 | 7/50 0 13 7 | 995/7107 2.0E-5 3 | 7/50 0 2
0.1416 | 15/106 -6.4E-4 21 8 | 869/6137 9.2E-7 5 | 16/113 -5.0E-5 2
2.72... (e) | 68/25 6.3E-4 7 7 | 878/323 -5.7E-6 8 | 87/32 1.7E-4 5
0.141592653589793 | 15/106 -5.9E-4 21 8 | 991/6999 -7.0E-6 4 | 15/106 -5.9E-4 2
-1.33333333333333 | -4/3 2.5E-15 2 2 | -1001/751 -3.3E-4 2 | -4/3 2.5E-15 1
-1.3 | -13/10 0 5 5 | -992/763 1.0E-4 3 | -13/10 0 2
-1.33 | -97/73 -9.3E-4 26 8 | -935/703 1.1E-5 3 | -133/100 0 2
-1.333 | -4/3 2.5E-4 2 2 | -1001/751 -8.3E-5 2 | -4/3 2.5E-4 1
-1.33333337 | -4/3 -2.7E-8 2 2 | -999/749 3.3E-4 3 | -4/3 -2.7E-8 2
-1.7 | -17/10 0 5 5 | -991/583 -1.0E-4 4 | -17/10 0 3
-1.37 | -37/27 2.7E-4 7 7 | -996/727 1.0E-5 7 | -37/27 2.7E-4 5
-1.33337 | -4/3 -2.7E-5 2 2 | -999/749 3.1E-4 3 | -4/3 -2.7E-5 2
0.047619 | 1/21 1.0E-6 20 6 | 1000/21001 -4.7E-5 2 | 1/21 1.0E-6 1
12.125 | 97/8 0 7 4 | 982/81 -1.3E-4 2 | 97/8 0 1
5.5 | 11/2 0 1 1 | 995/181 -5.0E-4 2 | 11/2 0 1
0.1233333333333 | 9/73 -3.7E-4 16 8 | 971/7873 -3.4E-6 4 | 9/73 -3.7E-4 2
0.7454545454545 | 38/51 -4.8E-4 15 8 | 981/1316 -1.9E-5 6 | 38/51 -4.8E-4 4
0.01024801004 | 2/195 8.2E-4 98 9 | 488/47619 2.0E-8 13 | 2/195 8.2E-4 3
0.99011 | 91/92 -9.9E-4 91 8 | 801/809 1.3E-6 5 | 100/101 -1.1E-5 2
0.9901134545 | 91/92 -9.9E-4 91 8 | 601/607 1.9E-6 5 | 100/101 -1.5E-5 2
0.19999999 | 1/5 5.0E-8 4 3 | 1000/5001 -2.0E-4 2 | 1/5 5.0E-8 1
0.20000001 | 1/5 -5.0E-8 4 3 | 1000/4999 2.0E-4 3 | 1/5 -5.0E-8 2
5.0183168565E-05 | 1/19908 9.5E-4 19907 16 | 1000/19927001 -5.0E-8 2 | 1/19927 5.2E-12 1
3.909E-07 | 1/2555644 1.0E-3 2555643 23 | 1/1 2.6E6 (!) 1 | 1/2558199 1.1E-8 1
88900003.001 |88900003/1 -1.1E-11 0 0 |88900004/1 1.1E-8 1 |88900003/1 -1.1E-11 0
0.26... (5/19) | 5/19 0 7 6 | 996/3785 -5.3E-5 4 | 5/19 0 3
0.61... (37/61) | 17/28 9.7E-4 8 7 | 982/1619 -1.7E-5 8 | 17/28 9.7E-4 5
| | |
Accuracy: 1.0E-4 | Stern-Brocot OPTIMIZED | Eppstein | Richards
Input | Result Error Iterations Iterations | Result Error Iterations | Result Error Iterations
======================| =====================================================| =========================================| =========================================
0.62... (307/499) | 227/369 -8.8E-5 33 11 | 9816/15955 -2.0E-7 8 | 299/486 -6.7E-6 6
0.05... (33/683) | 23/476 6.4E-5 27 12 | 9989/206742 1.5E-7 7 | 23/476 6.4E-5 5
0.06... (33/541) | 28/459 6.6E-5 24 12 | 9971/163464 -1.9E-7 6 | 33/541 0 5
1E-05 | 1/99991 9.0E-5 99990 18 | 10000/999999999 1.0E-9 3 | 1/99999 1.0E-5 1
0.333 | 303/910 -9.9E-5 305 12 | 9991/30003 1.0E-7 3 | 333/1000 0 2
0.7777 | 556/715 -1.0E-4 84 12 | 7777/10000 0 8 | 1109/1426 -1.8E-7 4
3.14... (pi) | 289/92 -9.2E-5 19 8 | 9918/3157 -8.1E-7 4 | 333/106 -2.6E-5 2
2.72... (e) | 193/71 1.0E-5 10 9 | 9620/3539 6.3E-8 11 | 193/71 1.0E-5 7
0.7454545454545 | 41/55 6.1E-14 16 8 | 9960/13361 -1.8E-6 6 | 41/55 6.1E-14 5
0.01024801004 | 7/683 8.7E-5 101 12 | 9253/902907 -1.3E-10 16 | 7/683 8.7E-5 5
0.99011 | 100/101 -1.1E-5 100 8 | 901/910 -1.1E-7 6 | 100/101 -1.1E-5 2
0.9901134545 | 100/101 -1.5E-5 100 8 | 8813/8901 1.6E-8 7 | 100/101 -1.5E-5 2
0.26... (5/19) | 5/19 0 7 6 | 9996/37985 -5.3E-6 4 | 5/19 0 3
0.61... (37/61) | 37/61 0 10 8 | 9973/16442 -1.6E-6 8 | 37/61 0 7
Performance comparison
I performed detailed speed tests and plotted the results. Not looking at quality and only speed:
- The Stern-Brocot optimization slows it down by at most a factor 2, but the original Stern-Brocot can be hundreds or thousands times slower when it hits the unlucky values mentioned. That's still only a couple of microseconds though per call.
- Richards is consistently fast.
- Eppstein is around 3 times slower than the others.
Stern-Brocot and Richards compared:
- Both return nice fractions.
- Richards often results in a smaller error. It is also a bit faster.
- Stern-Brocot walks down the S-B tree. It finds the fraction of the lowest denominator that meets the required accuracy, then stops.
If you do not require the lowest denominator fraction, Richards is a good choice.
Solution 3 - C#
I know you said you searched online, but if you missed the following paper it might be of some help. It includes a code example in Pascal.
Algorithm To Convert A Decimal To A Fraction*
Alternatively, as part of it's standard library, Ruby has code that deals with rational numbers. It can convert from floats to rationals and vice versa. I believe you can look through the code as well. The documentation is found here. I know you're not using Ruby, but it might help to look at the algorithms.
Additionally, you can call Ruby code from C# (or even write Ruby code inside a C# code file) if you use IronRuby, which runs on top of the .net framework.
*Updated to a new link as it appears the original URL is broken (http://homepage.smc.edu/kennedy_john/DEC2FRAC.pdf)</sub>
Solution 4 - C#
I found the same paper that Matt referenced, and I took a second and implemented it in Python. Maybe seeing the same idea in code will make it clearer. Granted, you requested an answer in C# and I'm giving it to you in Python, but it's a fairly trivial program, and I'm sure it would be easy to translate. The parameters are num (the decimal number you'd like to convert to a rational) and epsilon (the maximum allowed difference between num and the calculated rational). Some quick test runs find that it usually only takes two or three iterations to converge when epsilon is around 1e-4.
def dec2frac(num, epsilon, max_iter=20):
d = [0, 1] + ([0] * max_iter)
z = num
n = 1
t = 1
while num and t < max_iter and abs(n/d[t] - num) > epsilon:
t += 1
z = 1/(z - int(z))
d[t] = d[t-1] * int(z) + d[t-2]
# int(x + 0.5) is equivalent to rounding x.
n = int(num * d[t] + 0.5)
return n, d[t]
Edit: I just noticed your note about wanting them to work with recurring decimals. I don't know any languages that have syntax to support recurring decimals, so I'm not sure how one would go about handling them, but running 0.6666666 and 0.166666 through this method return the correct results (2/3 and 1/6, respectively).
Another Edit (I didn't think this would be so interesting!): If you want to know more about the theory behind this algorithm, Wikipedia has an excellent page on the Euclidian algorithm
Solution 5 - C#
The most populair solutions to this problem are Richards’ algorithm and the Stern-Brocot algorithm, implemented by btilly with speed optimalization by btilly and Jay Zed. Richards’ algorithm is the fastest, but does not guarantee to return the best fraction.
I have an solution to this problem which always gives the best fraction and is also faster than all of the algorithms above. Here is the algorithm in C# (explanation and speed test below).
This is a short algorithm without comments. An complete version is provided in the source code at the end.
public static Fraction DoubleToFractionSjaak(double value, double accuracy)
{
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
int a = 0;
int b = 1;
int c = 1;
int d = (int)(1 / maximumvalue);
while (true)
{
int n = (int)((b * minimalvalue - a) / (c - d * minimalvalue));
if (n == 0) break;
a += n * c;
b += n * d;
n = (int)((c - d * maximumvalue) / (b * maximumvalue - a));
if (n == 0) break;
c += n * a;
d += n * b;
}
int denominator = b + d;
return new Fraction(sign * (integerpart * denominator + (a + c)), denominator);
}
Where Fraction is a simple class to store a fraction, like the following:
public class Fraction
{
public int Numerator { get; private set; }
public int Denominator { get; private set; }
public Fraction(int numerator, int denominator)
{
Numerator = numerator;
Denominator = denominator;
}
}
How it works
Like the other solutions mentioned, my solution is based on continued fraction. Other solutions like the one from Eppstein or solutions based on repeating decimals proved to be slower and/or give suboptimal results.
Continued fraction
Solutions based on continued fraction are mostly based on two algorithms, both described in an article by Ian Richards published here in 1981. He called them the “slow continued fraction algorithm” and the “fast continued fraction algorithm”. The first is known as the the Stern-Brocot algorithm while the latter is known as Richards’ algorithm.
My algorithm (short explanation)
To fully understand my algorithm, you need to have read the article by Ian Richards or at least understand what a Farey pair is. Furthermore, read the algorithm with comments at the end of this article.
The algorithm is using a Farey pair, containing a left and a right fraction. By repeatedly taking the mediant it is closing in on the target value. This is just like the slow algorithm but there are two major differences:
- Multiple iterations are performed at once as long as the mediant stay on one side of the target value.
- The left and right fraction cannot come closer to the target value than the given accuracy.
Alternately the right and left side of the target value are checked. If the algorithm cannot produce a result closer to the target value, the process ends. The resulting mediant is the optimal solution.
Speed test
I did some speed tests on my laptop with the following algorithms:
- Improved slow algorithm by Kay Zed and btilly
- John Kennedy’s implementation of the Fast algorithm, converted to C# by Kay Zed
- My implementation of the Fast algorithm (close to the original by Ian Richards)
- Jeremy Herrman’s implementation of the Fast algorithm
- My algorithm above
I omitted the original slow algorithm by btilly, because of its bad worst-case performance.
Test set
I choose a set of target values (very arbitrary) and calculated the fraction 100000 times with 5 different accuracies. Because possible some (future) algorithms couldn't handle improper fractions, only target values from 0.0 to 1.0 were tested. The accuracy was taken from the range from 2 to 6 decimal places (0.005 to 0.0000005). The following set was used:
0.999999, 0.000001, 0.25
0.33, 0.333, 0.3333, 0.33333, 0.333333, 0.333333333333,
0.666666666666, 0.777777777777, 0.090909090909, 0.263157894737,
0.606557377049, 0.745454545454, 0.000050183168565,
pi - 3, e - 2.0, sqrt(2) - 1
Results
I did 13 test runs. The result is in milliseconds needed for the whole data set.
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Run 11 Run 12 Run 13
1. 9091 9222 9070 9111 9091 9108 9293 9118 9115 9113 9102 9143 9121
2. 7071 7125 7077 6987 7126 6985 7037 6964 7023 6980 7053 7050 6999
3. 6903 7059 7062 6891 6942 6880 6882 6918 6853 6918 6893 6993 6966
4. 7546 7554 7564 7504 7483 7529 7510 7512 7517 7719 7513 7520 7514
5. 6839 6951 6882 6836 6854 6880 6846 7017 6874 6867 6828 6848 6864
Conclusion (skipping the analysis)
Even without a statistical analysis, it's easy to see that my algorithm is faster than the other tested algorithms. The difference with the fastest variant of “fast algorithm” however is less than 1 percent. The Improved slow algorithm is 30%-35% slower than the fastest algorithm”.
On the other hand, even the slowest algorithm performs a calculation on average in less than a microsecond. So under normal circumstances speed is not really an issue. In my opinion the best algorithm is mainly a matter of taste, so choose any of the tested algorithms on other criteria.
- Does the algorithm gives the best result?
- Is the algorithm available in my favorite language?
- What is the code size of the algorithm?
- Is the algorithm readable, understandable?
Source code
The source code below contains all used algorithms. It includes:
- My original algorithm (with comments)
- A even faster version of my algorithm (but less readable)
- The original slow algorithm
- All tested algorithms
public class DoubleToFraction
{
// ===================================================
// Sjaak algorithm - original version
//
public static Fraction SjaakOriginal(double value, double accuracy)
{
// Split value in a sign, an integer part, a fractional part
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
// check if the fractional part is near 0
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
// check if the fractional part is near 1
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
// The left fraction (a/b) is initially (0/1), the right fraction (c/d) is initially (1/1)
// Together they form a Farey pair.
// We will keep the left fraction below the minimumvalue and the right fraction above the maximumvalue
int a = 0;
int b = 1;
int c = 1;
int d = (int)(1 / maximumvalue);
// The first interation is performed above. Calculate maximum n where (n*a+c)/(n*b+d) >= maximumvalue
// This is the same as n <= 1/maximumvalue - 1, d will become n+1 = floor(1/maximumvalue)
// repeat forever (at least until we cannot close in anymore)
while (true)
{
// Close in from the left n times.
// Calculate maximum n where (a+n*c)/(b+n*d) <= minimalvalue
// This is the same as n <= (b * minimalvalue - a) / (c-d*minimalvalue)
int n = (int)((b * minimalvalue - a) / (c - d * minimalvalue));
// If we cannot close in from the left (and also not from the right anymore) the loop ends
if (n == 0) break;
// Update left fraction
a += n * c;
b += n * d;
// Close in from the right n times.
// Calculate maximum n where (n*a+c)/(n*b+d) >= maximumvalue
// This is the same as n <= (c - d * maximumvalue) / (b * maximumvalue - a)
n = (int)((c - d * maximumvalue) / (b * maximumvalue - a));
// If we cannot close in from the right (and also not from the left anymore) the loop ends
if (n == 0) break;
// Update right fraction
c += n * a;
d += n * b;
}
// We cannot close in anymore
// The best fraction will be the mediant of the left and right fraction = (a+c)/(b+d)
int denominator = b + d;
return new Fraction(sign * (integerpart * denominator + (a + c)), denominator);
}
// ===================================================
// Sjaak algorithm - faster version
//
public static Fraction SjaakFaster(double value, double accuracy)
{
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
//int a = 0;
int b = 1;
//int c = 1;
int d = (int)(1 / maximumvalue);
double left_n = minimalvalue; // b * minimalvalue - a
double left_d = 1.0 - d * minimalvalue; // c - d * minimalvalue
double right_n = 1.0 - d * maximumvalue; // c - d * maximumvalue
double right_d = maximumvalue; // b * maximumvalue - a
while (true)
{
if (left_n < left_d) break;
int n = (int)(left_n / left_d);
//a += n * c;
b += n * d;
left_n -= n * left_d;
right_d -= n * right_n;
if (right_n < right_d) break;
n = (int)(right_n / right_d);
//c += n * a;
d += n * b;
left_d -= n * left_n;
right_n -= n * right_d;
}
int denominator = b + d;
int numerator = (int)(value * denominator + 0.5);
return new Fraction(sign * (integerpart * denominator + numerator), denominator);
}
// ===================================================
// Original Farley - Implemented by btilly
//
public static Fraction OriginalFarley(double value, double accuracy)
{
// Split value in a sign, an integer part, a fractional part
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
// check if the fractional part is near 0
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
// check if the fractional part is near 1
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
// The lower fraction is 0/1
int lower_numerator = 0;
int lower_denominator = 1;
// The upper fraction is 1/1
int upper_numerator = 1;
int upper_denominator = 1;
while (true)
{
// The middle fraction is (lower_numerator + upper_numerator) / (lower_denominator + upper_denominator)
int middle_numerator = lower_numerator + upper_numerator;
int middle_denominator = lower_denominator + upper_denominator;
if (middle_denominator * maximumvalue < middle_numerator)
{
// real + error < middle : middle is our new upper
upper_numerator = middle_numerator;
upper_denominator = middle_denominator;
}
else if (middle_numerator < minimalvalue * middle_denominator)
{
// middle < real - error : middle is our new lower
lower_numerator = middle_numerator;
lower_denominator = middle_denominator;
}
else
{
return new Fraction(sign * (integerpart * middle_denominator + middle_numerator), middle_denominator);
}
}
}
// ===================================================
// Modified Farley - Implemented by btilly, Kay Zed
//
public static Fraction ModifiedFarley(double value, double accuracy)
{
// Split value in a sign, an integer part, a fractional part
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
// check if the fractional part is near 0
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
// check if the fractional part is near 1
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
// The lower fraction is 0/1
int lower_numerator = 0;
int lower_denominator = 1;
// The upper fraction is 1/1
int upper_numerator = 1;
int upper_denominator = 1;
while (true)
{
// The middle fraction is (lower_numerator + upper_numerator) / (lower_denominator + upper_denominator)
int middle_numerator = lower_numerator + upper_numerator;
int middle_denominator = lower_denominator + upper_denominator;
if (middle_denominator * maximumvalue < middle_numerator)
{
// real + error < middle : middle is our new upper
ModifiedFarleySeek(ref upper_numerator, ref upper_denominator, lower_numerator, lower_denominator, (un, ud) => (lower_denominator + ud) * maximumvalue < (lower_numerator + un));
}
else if (middle_numerator < minimalvalue * middle_denominator)
{
// middle < real - error : middle is our new lower
ModifiedFarleySeek(ref lower_numerator, ref lower_denominator, upper_numerator, upper_denominator, (ln, ld) => (ln + upper_numerator) < minimalvalue * (ld + upper_denominator));
}
else
{
return new Fraction(sign * (integerpart * middle_denominator + middle_numerator), middle_denominator);
}
}
}
private static void ModifiedFarleySeek(ref int a, ref int b, int ainc, int binc, Func<int, int, bool> f)
{
// Binary seek for the value where f() becomes false
a += ainc;
b += binc;
if (f(a, b))
{
int weight = 1;
do
{
weight *= 2;
a += ainc * weight;
b += binc * weight;
}
while (f(a, b));
do
{
weight /= 2;
int adec = ainc * weight;
int bdec = binc * weight;
if (!f(a - adec, b - bdec))
{
a -= adec;
b -= bdec;
}
}
while (weight > 1);
}
}
// ===================================================
// Richards implementation by Jemery Hermann
//
public static Fraction RichardsJemeryHermann(double value, double accuracy, int maxIterations = 20)
{
// Split value in a sign, an integer part, a fractional part
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
// check if the fractional part is near 0
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
// check if the fractional part is near 1
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
// Richards - Implemented by Jemery Hermann
double[] d = new double[maxIterations + 2];
d[1] = 1;
double z = value;
double n = 1;
int t = 1;
while (t < maxIterations && Math.Abs(n / d[t] - value) > accuracy)
{
t++;
z = 1 / (z - (int)z);
d[t] = d[t - 1] * (int)z + d[t - 2];
n = (int)(value * d[t] + 0.5);
}
return new Fraction(sign * (integerpart * (int)d[t] + (int)n), (int)d[t]);
}
// ===================================================
// Richards implementation by Kennedy
//
public static Fraction RichardsKennedy(double value, double accuracy)
{
// Split value in a sign, an integer part, a fractional part
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
// check if the fractional part is near 0
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
// check if the fractional part is near 1
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
// Richards
double z = value;
int previousDenominator = 0;
int denominator = 1;
int numerator;
do
{
z = 1.0 / (z - (int)z);
int temp = denominator;
denominator = denominator * (int)z + previousDenominator;
previousDenominator = temp;
numerator = (int)(value * denominator + 0.5);
}
while (Math.Abs(value - (double)numerator / denominator) > accuracy && z != (int)z);
return new Fraction(sign * (integerpart * denominator + numerator), denominator);
}
// ===================================================
// Richards implementation by Sjaak
//
public static Fraction RichardsOriginal(double value, double accuracy)
{
// Split value in a sign, an integer part, a fractional part
int sign = value < 0 ? -1 : 1;
value = value < 0 ? -value : value;
int integerpart = (int)value;
value -= integerpart;
// check if the fractional part is near 0
double minimalvalue = value - accuracy;
if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
// check if the fractional part is near 1
double maximumvalue = value + accuracy;
if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
// Richards
double z = value;
int denominator0 = 0;
int denominator1 = 1;
int numerator0 = 1;
int numerator1 = 0;
int n = (int)z;
while (true)
{
z = 1.0 / (z - n);
n = (int)z;
int temp = denominator1;
denominator1 = denominator1 * n + denominator0;
denominator0 = temp;
temp = numerator1;
numerator1 = numerator1 * n + numerator0;
numerator0 = temp;
double d = (double)numerator1 / denominator1;
if (d > minimalvalue && d < maximumvalue) break;
}
return new Fraction(sign * (integerpart * denominator1 + numerator1), denominator1);
}
}
Solution 6 - C#
You can't represent a recurring decimal in .net so I'll ignore that part of your question.
You can only represent a finite and relatively small number of digits.
There's an extremely simple algorithm:
- take decimal
x - count the number of digits after the decimal point; call this
n - create a fraction
(10^n * x) / 10^n - remove common factors from the numerator and denominator.
so if you have 0.44, you would count 2 places are the decimal point - n = 2, and then write
(0.44 * 10^2) / 10^2- =
44 / 100 - factorising (removing common factor of 4) gives
11 / 25
Solution 7 - C#
Here's a C# version of Will Brown's python example. I've also changed it to handle separate whole numbers (e.g. "2 1/8" instead of "17/8").
public static string DoubleToFraction(double num, double epsilon = 0.0001, int maxIterations = 20)
{
double[] d = new double[maxIterations + 2];
d[1] = 1;
double z = num;
double n = 1;
int t = 1;
int wholeNumberPart = (int)num;
double decimalNumberPart = num - Convert.ToDouble(wholeNumberPart);
while (t < maxIterations && Math.Abs(n / d[t] - num) > epsilon)
{
t++;
z = 1 / (z - (int)z);
d[t] = d[t - 1] * (int)z + d[t - 2];
n = (int)(decimalNumberPart * d[t] + 0.5);
}
return string.Format((wholeNumberPart > 0 ? wholeNumberPart.ToString() + " " : "") + "{0}/{1}",
n.ToString(),
d[t].ToString()
);
}
Solution 8 - C#
I wrote a quick class that runs fairly quick and gives the results I would expect. You can choose your Precision as well. It is much simpler from any code I seen and runs quick as well.
//Written By Brian Dobony
public static class Fraction
{
public static string ConvertDecimal(Double NumberToConvert, int DenominatorPercision = 32)
{
int WholeNumber = (int)NumberToConvert;
double DecimalValue = NumberToConvert - WholeNumber;
double difference = 1;
int numerator = 1;
int denominator = 1;
// find closest value that matches percision
// Automatically finds Fraction in simplified form
for (int y = 2; y < DenominatorPercision + 1; y++)
{
for (int x = 1; x < y; x++)
{
double tempdif = Math.Abs(DecimalValue - (double)x / (double)y);
if (tempdif < difference)
{
numerator = x;
denominator = y;
difference = tempdif;
// if exact match is found return it
if (difference == 0)
{
return FractionBuilder(WholeNumber, numerator, denominator);
}
}
}
}
return FractionBuilder(WholeNumber, numerator, denominator);
}
private static string FractionBuilder(int WholeNumber, int Numerator, int Denominator)
{
if (WholeNumber == 0)
{
return Numerator + @"/" + Denominator;
}
else
{
return WholeNumber + " " + Numerator + @"/" + Denominator;
}
}
}
Solution 9 - C#
This is the C# version of the algorithm by Ian Richards / John Kennedy. Other answers here using this same algorithm:
- Matt (links to the Kennedy paper only)
- Haldean Brown (Python)
- Jeremy Herrman (C#)
- PinkFloyd (C)
It does not handle infinities and NaN.
This algorithm is fast.
For example values and a comparison with other algorithms, see my other answer
public Fraction RealToFraction(double value, double accuracy)
{
if (accuracy <= 0.0 || accuracy >= 1.0)
{
throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1.");
}
int sign = Math.Sign(value);
if (sign == -1)
{
value = Math.Abs(value);
}
// Accuracy is the maximum relative error; convert to absolute maxError
double maxError = sign == 0 ? accuracy : value * accuracy;
int n = (int) Math.Floor(value);
value -= n;
if (value < maxError)
{
return new Fraction(sign * n, 1);
}
if (1 - maxError < value)
{
return new Fraction(sign * (n + 1), 1);
}
double z = value;
int previousDenominator = 0;
int denominator = 1;
int numerator;
do
{
z = 1.0 / (z - (int) z);
int temp = denominator;
denominator = denominator * (int) z + previousDenominator;
previousDenominator = temp;
numerator = Convert.ToInt32(value * denominator);
}
while (Math.Abs(value - (double) numerator / denominator) > maxError && z != (int) z);
return new Fraction((n * denominator + numerator) * sign, denominator);
}
Solution 10 - C#
I come up with a very late answer. The code is taken from an article from
Richards published in 1981 and written in c.
inline unsigned int richards_solution(double const& x0, unsigned long long& num, unsigned long long& den, double& sign, double const& err = 1e-10){
sign = my::sign(x0);
double g(std::abs(x0));
unsigned long long a(0);
unsigned long long b(1);
unsigned long long c(1);
unsigned long long d(0);
unsigned long long s;
unsigned int iter(0);
do {
s = std::floor(g);
num = a + s*c;
den = b + s*d;
a = c;
b = d;
c = num;
d = den;
g = 1.0/(g-s);
if(err>std::abs(sign*num/den-x0)){ return iter; }
} while(iter++<1e6);
std::cerr<<__PRETTY_FUNCTION__<<" : failed to find a fraction for "<<x0<<std::endl;
return 0;
}
I rewrite here my implementation of btilly_solution :
inline unsigned int btilly_solution(double x, unsigned long long& num, unsigned long long& den, double& sign, double const& err = 1e-10){
sign = my::sign(x);
num = std::floor(std::abs(x));
x = std::abs(x)-num;
unsigned long long lower_n(0);
unsigned long long lower_d(1);
unsigned long long upper_n(1);
unsigned long long upper_d(1);
unsigned long long middle_n;
unsigned long long middle_d;
unsigned int iter(0);
do {
middle_n = lower_n + upper_n;
middle_d = lower_d + upper_d;
if(middle_d*(x+err)<middle_n){
upper_n = middle_n;
upper_d = middle_d;
} else if(middle_d*(x-err)>middle_n) {
lower_n = middle_n;
lower_d = middle_d;
} else {
num = num*middle_d+middle_n;
den = middle_d;
return iter;
}
} while(iter++<1e6);
den = 1;
std::cerr<<__PRETTY_FUNCTION__<<" : failed to find a fraction for "<<x+num<<std::endl;
return 0;
}
And here I propose some tests with an error of 1e-10 :
------------------------------------------------------ |
btilly 0.166667 0.166667=1/6 in 5 iterations | 1/6
richard 0.166667 0.166667=1/6 in 1 iterations |
------------------------------------------------------ |
btilly 0.333333 0.333333=1/3 in 2 iterations | 1/3
richard 0.333333 0.333333=1/3 in 1 iterations |
------------------------------------------------------ |
btilly 0.142857 0.142857=1/7 in 6 iterations | 1/7
richard 0.142857 0.142857=1/7 in 1 iterations |
------------------------------------------------------ |
btilly 0.714286 0.714286=5/7 in 4 iterations | 5/7
richard 0.714286 0.714286=5/7 in 4 iterations |
------------------------------------------------------ |
btilly 1e-07 1.001e-07=1/9990010 in 9990009 iteration | 0.0000001
richard 1e-07 1e-07=1/10000000 in 1 iterations |
------------------------------------------------------ |
btilly 3.66667 3.66667=11/3 in 2 iterations | 11/3
richard 3.66667 3.66667=11/3 in 3 iterations |
------------------------------------------------------ |
btilly 1.41421 1.41421=114243/80782 in 25 iterations | sqrt(2)
richard 1.41421 1.41421=114243/80782 in 13 iterations |
------------------------------------------------------ |
btilly 3.14159 3.14159=312689/99532 in 317 iterations | pi
richard 3.14159 3.14159=312689/99532 in 7 iterations |
------------------------------------------------------ |
btilly 2.71828 2.71828=419314/154257 in 36 iterations | e
richard 2.71828 2.71828=517656/190435 in 14 iterations |
------------------------------------------------------ |
btilly 0.390885 0.390885=38236/97819 in 60 iterations | random
richard 0.390885 0.390885=38236/97819 in 13 iterations |
As you can see, the two methods give more or less the same results but the richards' one is way more efficient and easier to implement.
Edit
To compile my code you need a difinition for my::sign which is simply a
function that returns the sign of a variable. Here is my implementation
namespace my{
template<typename Type> inline constexpr
int sign_unsigned(Type x){ return Type(0)<x; }
template<typename Type> inline constexpr
int sign_signed(Type x){ return (Type(0)<x)-(x<Type(0)); }
template<typename Type> inline constexpr
int sign(Type x) { return std::is_signed<Type>()?sign_signed(x):sign_unsigned(x); }
}
Sorry
I guess this answer refers to the same algorithm. I didn't see that before...
Solution 11 - C#
This algorithm by David Eppstein, UC Irvine, based on the theory of continued fractions and originally in C, was translated to C# by me. The fractions it generates satisfy the error margin but mostly do not look as good as the solutions in my other answers. E.g. 0.5 becomes 999/1999 while 1/2 would be preferred when displayed to a user (if you need that, see my other answers).
There is an overload to specify the error margin as a double (relative to the value, not the absolute error). For the Fraction type, see my other answer.
By the way, if your fractions can get large, change the relevant ints to long. Compared to the other algorithms this one is prone to overflow.
For example values and a comparison with other algorithms, see my other answer
public Fraction RealToFraction(double value, int maxDenominator)
{
// http://www.ics.uci.edu/~eppstein/numth/frap.c
// Find rational approximation to given real number
// David Eppstein / UC Irvine / 8 Aug 1993
// With corrections from Arno Formella, May 2008
if (value == 0.0)
{
return new Fraction(0, 1);
}
int sign = Math.Sign(value);
if (sign == -1)
{
value = Math.Abs(value);
}
int[,] m = { { 1, 0 }, { 0, 1 } };
int ai = (int) value;
// Find terms until denominator gets too big
while (m[1, 0] * ai + m[1, 1] <= maxDenominator)
{
int t = m[0, 0] * ai + m[0, 1];
m[0, 1] = m[0, 0];
m[0, 0] = t;
t = m[1, 0] * ai + m[1, 1];
m[1, 1] = m[1, 0];
m[1, 0] = t;
value = 1.0 / (value - ai);
// 0x7FFFFFFF = Assumes 32 bit floating point just like in the C implementation.
// This check includes Double.IsInfinity(). Even though C# double is 64 bits,
// the algorithm sometimes fails when trying to increase this value too much. So
// I kept it. Anyway, it works.
if (value > 0x7FFFFFFF)
{
break;
}
ai = (int) value;
}
// Two approximations are calculated: one on each side of the input
// The result of the first one is the current value. Below the other one
// is calculated and it is returned.
ai = (maxDenominator - m[1, 1]) / m[1, 0];
m[0, 0] = m[0, 0] * ai + m[0, 1];
m[1, 0] = m[1, 0] * ai + m[1, 1];
return new Fraction(sign * m[0, 0], m[1, 0]);
}
public Fraction RealToFraction(double value, double accuracy)
{
if (accuracy <= 0.0 || accuracy >= 1.0)
{
throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1.");
}
int maxDenominator = (int) Math.Ceiling(Math.Abs(1.0 / (value * accuracy)));
if (maxDenominator < 1)
{
maxDenominator = 1;
}
return RealToFraction(value, maxDenominator);
}
Solution 12 - C#
A recurring decimal can be represented by two finite decimals: the leftward part before the repeat, and the repeating part. E.g. 1.6181818... = 1.6 + 0.1*(0.18...). Think of this as a + b * sum(c * 10**-(d*k) for k in range(1, infinity)) (in Python notation here). In my example, a=1.6, b=0.1, c=18, d=2 (the number of digits in c). The infinite sum can be simplified (sum(r**k for r in range(1, infinity)) == r / (1 - r) if I recall rightly), yielding a + b * (c * 10**-d) / (1 - c * 10**-d)), a finite ratio. That is, start with a, b, c, and d as rational numbers, and you end up with another.
(This elaborates Kirk Broadhurst's answer, which is right as far as it goes, but doesn't cover repeating decimals. I don't promise I made no mistakes above, though I'm confident the general approach works.)
Solution 13 - C#
Well, seems I finally had to do it myself. I just had to create a program simulating the natural way I would solve it myself. I just submitted the code to codeproject as writing out the whole code here won't be suitable. You can download the project from here Fraction_Conversion, or look at the codeproject page here.
Here's how it works:
- Find out whether given decimal is negative
- Convert decimal to absolute value
- Get integer part of given decimal
- Get the decimal part
- Check whether decimal is recurring. If decimal is recurring, we then return the exact recurring decimal
- If decimal is not recurring, start reduction by changing numerator to 10^no. of decimal, else we subtract 1 from numerator
- Then reduce fraction
Code Preview:
private static string dec2frac(double dbl)
{
char neg = ' ';
double dblDecimal = dbl;
if (dblDecimal == (int) dblDecimal) return dblDecimal.ToString(); //return no if it's not a decimal
if (dblDecimal < 0)
{
dblDecimal = Math.Abs(dblDecimal);
neg = '-';
}
var whole = (int) Math.Truncate(dblDecimal);
string decpart = dblDecimal.ToString().Replace(Math.Truncate(dblDecimal) + ".", "");
double rN = Convert.ToDouble(decpart);
double rD = Math.Pow(10, decpart.Length);
string rd = recur(decpart);
int rel = Convert.ToInt32(rd);
if (rel != 0)
{
rN = rel;
rD = (int) Math.Pow(10, rd.Length) - 1;
}
//just a few prime factors for testing purposes
var primes = new[] {41, 43, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2};
foreach (int i in primes) reduceNo(i, ref rD, ref rN);
rN = rN + (whole*rD);
return string.Format("{0}{1}/{2}", neg, rN, rD);
}
Thanks @ Darius for given me an idea of how to solve the recurring decimals :)
Solution 14 - C#
I recently had to perform this very task of working with a Decimal Data Type which is stored in our SQL Server database. At the Presentation Layer this value was edited as a fractional value in a TextBox. The complexity here was working with the Decimal Data Type which holds some pretty large values in comparison to int or long. So to reduce the opportunity for data overrun, I stuck with the Decimal Data Type throughout the conversion.
Before I begin, I want to comment on Kirk's previous answer. He is absolutely correct as long as there are no assumptions made. However, if the developer only looks for repeating patterns within the confines of the Decimal Data Type .3333333... can be represented as 1/3. An example of the algorithm can be found at basic-mathematics.com. Again, this means you have to make assumptions based on the information available and using this method only captures a very small subset of repeating decimals. However for small numbers should be okay.
Moving forward, let me give you a snapshot of my solution. If you want to read a complete example with additional code I created a blog post with much more detail.
Convert Decimal Data Type to a String Fraction
public static void DecimalToFraction(decimal value, ref decimal sign, ref decimal numerator, ref decimal denominator)
{
const decimal maxValue = decimal.MaxValue / 10.0M;
// e.g. .25/1 = (.25 * 100)/(1 * 100) = 25/100 = 1/4
var tmpSign = value < decimal.Zero ? -1 : 1;
var tmpNumerator = Math.Abs(value);
var tmpDenominator = decimal.One;
// While numerator has a decimal value
while ((tmpNumerator - Math.Truncate(tmpNumerator)) > 0 &&
tmpNumerator < maxValue && tmpDenominator < maxValue)
{
tmpNumerator = tmpNumerator * 10;
tmpDenominator = tmpDenominator * 10;
}
tmpNumerator = Math.Truncate(tmpNumerator); // Just in case maxValue boundary was reached.
ReduceFraction(ref tmpNumerator, ref tmpDenominator);
sign = tmpSign;
numerator = tmpNumerator;
denominator = tmpDenominator;
}
public static string DecimalToFraction(decimal value)
{
var sign = decimal.One;
var numerator = decimal.One;
var denominator = decimal.One;
DecimalToFraction(value, ref sign, ref numerator, ref denominator);
return string.Format("{0}/{1}", (sign * numerator).ToString().TruncateDecimal(),
denominator.ToString().TruncateDecimal());
}
This is pretty straight forward where the DecimalToFraction(decimal value) is nothing more than a simplified entry point for the first method which provides access to all the components which compose a fraction. If you have a decimal of .325 then divide it by 10 to the power of number of decimal places. Lastly reduce the fraction. And, in this example .325 = 325/10^3 = 325/1000 = 13/40.
Next, going the other direction.
Convert String Fraction to Decimal Data Type
static readonly Regex FractionalExpression = new Regex(@"^(?<sign>[-])?(?<numerator>\d+)(/(?<denominator>\d+))?$");
public static decimal? FractionToDecimal(string fraction)
{
var match = FractionalExpression.Match(fraction);
if (match.Success)
{
// var sign = Int32.Parse(match.Groups["sign"].Value + "1");
var numerator = Int32.Parse(match.Groups["sign"].Value + match.Groups["numerator"].Value);
int denominator;
if (Int32.TryParse(match.Groups["denominator"].Value, out denominator))
return denominator == 0 ? (decimal?)null : (decimal)numerator / denominator;
if (numerator == 0 || numerator == 1)
return numerator;
}
return null;
}
Converting back to a decimal is quite simple as well. Here we parse out the fractional components, store them in something we can work with (here decimal values) and perform our division.
Solution 15 - C#
My 2 cents. Here's VB.NET version of btilly's excellent algorithm:
Public Shared Sub float_to_fraction(x As Decimal, ByRef Numerator As Long, ByRef Denom As Long, Optional ErrMargin As Decimal = 0.001)
Dim n As Long = Int(Math.Floor(x))
x -= n
If x < ErrMargin Then
Numerator = n
Denom = 1
Return
ElseIf x >= 1 - ErrMargin Then
Numerator = n + 1
Denom = 1
Return
End If
' 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, middle_d As Decimal
While True
' 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 x + error < middle
If middle_d * (x + ErrMargin) < middle_n Then
' middle is our new upper
upper_n = middle_n
upper_d = middle_d
' Else If middle < x - error
ElseIf middle_n < (x - ErrMargin) * middle_d Then
' middle is our new lower
lower_n = middle_n
lower_d = middle_d
' Else middle is our best fraction
Else
Numerator = n * middle_d + middle_n
Denom = middle_d
Return
End If
End While
End Sub
Solution 16 - C#
Here's an algorithm implemented in VB that converts Floating Point Decimal to Integer Fraction that I wrote many years ago.
Basically you start with a numerator = 0 and a denominator = 1, then if the quotient is less than the decimal input, add 1 to the numerator and if the quotient is greater than the decimal input, add 1 to the denominator. Repeat until you get within your desired precision.
Solution 17 - C#
If I were you I'd handle the "no repeating decimals in .NET" problem by having it convert strings with the recurrence marked somehow.
E.g. 1/3 could be represented "0.R3" 1/60 could be represented "0.01R6"
I'd require an explicit cast from double or decimal because such values could only be converted into a fraction that was close. Implicit cast from int is ok.
You could use a struct and store your fraction (f) in two longs p and q such that f=p/q, q!=0, and gcd(p, q) == 1.
Solution 18 - C#
Here, you can have the method for converting Decimal into Fractions:
/// <summary>
/// Converts Decimals into Fractions.
/// </summary>
/// <param name="value">Decimal value</param>
/// <returns>Fraction in string type</returns>
public string DecimalToFraction(double value)
{
string result;
double numerator, realValue = value;
int num, den, decimals, length;
num = (int)value;
value = value - num;
value = Math.Round(value, 5);
length = value.ToString().Length;
decimals = length - 2;
numerator = value;
for (int i = 0; i < decimals; i++)
{
if (realValue < 1)
{
numerator = numerator * 10;
}
else
{
realValue = realValue * 10;
numerator = realValue;
}
}
den = length - 2;
string ten = "1";
for (int i = 0; i < den; i++)
{
ten = ten + "0";
}
den = int.Parse(ten);
num = (int)numerator;
result = SimplifiedFractions(num, den);
return result;
}
/// <summary>
/// Converts Fractions into Simplest form.
/// </summary>
/// <param name="num">Numerator</param>
/// <param name="den">Denominator</param>
/// <returns>Simplest Fractions in string type</returns>
string SimplifiedFractions(int num, int den)
{
int remNum, remDen, counter;
if (num > den)
{
counter = den;
}
else
{
counter = num;
}
for (int i = 2; i <= counter; i++)
{
remNum = num % i;
if (remNum == 0)
{
remDen = den % i;
if (remDen == 0)
{
num = num / i;
den = den / i;
i--;
}
}
}
return num.ToString() + "/" + den.ToString();
}
}
Solution 19 - C#
Here's an algorithm I wrote for a project not too long ago. It takes a different approach, which is more akin to something you would do by hand. I can't guarantee its efficiency, but it gets the job done.
public static string toFraction(string exp) {
double x = Convert.ToDouble(exp);
int sign = (Math.Abs(x) == x) ? 1 : -1;
x = Math.Abs(x);
int n = (int)x; // integer part
x -= n; // fractional part
int mult, nm, dm;
int decCount = 0;
Match m = Regex.Match(Convert.ToString(x), @"([0-9]+?)\1+.?$");
// repeating fraction
if (m.Success) {
m = Regex.Match(m.Value, @"([0-9]+?)(?=\1)");
mult = (int)Math.Pow(10, m.Length);
// We have our basic fraction
nm = (int)Math.Round(((x * mult) - x));
dm = mult - 1;
}
// get the number of decimal places
else {
double t = x;
while (t != 0) {
decCount++;
t *= 10;
t -= (int)t;
}
mult = (int)Math.Pow(10, decCount);
// We have our basic fraction
nm = (int)((x * mult));
dm = mult;
}
// can't be simplified
if (nm < 0 || dm < 0) return exp;
//Simplify
Stack factors = new Stack();
for (int i = 2; i < nm + 1; i++) {
if (nm % i == 0) factors.Push(i); // i is a factor of the numerator
}
// check against the denominator, stopping at the highest match
while(factors.Count != 0) {
// we have a common factor
if (dm % (int)factors.Peek() == 0) {
int f = (int)factors.Pop();
nm /= f;
dm /= f;
break;
}
else factors.Pop();
}
nm += (n * dm);
nm *= sign;
if (dm == 1) return Convert.ToString(nm);
else return Convert.ToString(nm) + "/" + Convert.ToString(dm);
}
Solution 20 - C#
Simple solution/breakdown of repeating decimal.
I took the logic that the numbers 1-9 divided by 9 are repeating. AKA 7/9 = .77777
My solution would be to multiply the whole number by 9, add the repeating number, and then divide by 9 again.
Ex: 28.66666
28*9=252
252+6=258
258/9=28.66666
This method is rather easy to program as well. Truncate decimal digit, multiply by 9, add first decimal, then divide by 9.
The only thing missing is that the fraction may need to be simplified if the left number is dividable by 3.
Solution 21 - C#
Here are two Swift 4 conversions of popular answers to this problem:
public func decimalToFraction(_ d: Double) -> (Int, Int) {
var df: Double = 1
var top: Int = 1
var bot: Int = 1
while df != d {
if df < d {
top += 1
} else {
bot += 1
top = Int(d * bot)
}
df = top / bot
}
return (top, bot)
}
public func realToFraction(_ value: Double, accuracy: Double = 0.00005) -> (Int, Int)? {
var value = value
guard accuracy >= 0 && accuracy <= 1 else {
Swift.print(accuracy, "Must be > 0 and < 1.")
return nil
}
let theSign = sign(value)
if theSign == -1 {
value = abs(value)
}
// Accuracy is the maximum relative error; convert to absolute maxError
let maxError = theSign == 0 ? accuracy : value * accuracy
let n = floor(value)
value -= n
if value < maxError {
return (Int(theSign * n), 1)
}
if 1 - maxError < value {
return (Int(theSign * (n + 1)), 1)
}
// The lower fraction is 0/1
var lowerN: Double = 0
var lowerD: Double = 1
// The upper fraction is 1/1
var upperN: Double = 1
var upperD: Double = 1
while true {
// The middle fraction is (lowerN + upperN) / (lowerD + upperD)
let middleN = lowerN + upperN
let middleD = lowerD + upperD
if middleD * (value + maxError) < middleN {
// real + error < middle : middle is our new upper
upperN = middleN
upperD = middleD
} else if middleN < (value - maxError) * middleD {
// middle < real - error : middle is our new lower
lowerN = middleN
lowerD = middleD
} else {
// Middle is our best fraction
return (Int(n * middleD + middleN * theSign), Int(middleD))
}
}
}
Solution 22 - C#
first function get fraction string format "1/2", second find gcd(Greatest common divisor) for up and down parts.
public static string DoubleToFraction(double num)
{
if (Math.Round(num, 6) == Math.Round(num, 0))
return Math.Round(num, 0).ToString();
bool minus = (num < 0) ? true : false;
int up;
if (minus)
up = (int)((Math.Round(num, 6) - 0.000001) * 362880);
else
up = (int)((Math.Round(num, 6) + 0.000001) * 362880);
int down = 362880;
int div = gcd(up, down);
up /= div;
down /= div;
return up + "/" + down;
}
public static int gcd(int a, int b)
{
if (b == 0)
return Math.Abs(a);
return gcd(b, a % b);
}
Solution 23 - C#
I've tried to expand on btilly's answer
The changes are:
If you want to display it in fration format then change the last else part of btilly's answer. So the modified code becomes:
def float_to_fraction (x, error=0.000001):
n = int(math.floor(x))
x -= n
if x < error:
return (n, 1)
elif 1 - error < x:
return (n+1, 1)
# The lower fraction is 0/1
lower_n = 0
lower_d = 1
# The upper fraction is 1/1
upper_n = 1
upper_d = 1
while True:
# 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 x + error < middle
if middle_d * (x + error) < middle_n:
# middle is our new upper
upper_n = middle_n
upper_d = middle_d
# Else If middle < x - error
elif middle_n < (x - error) * middle_d:
# middle is our new lower
lower_n = middle_n
lower_d = middle_d
# Else middle is our best fraction
else:
#return (n * middle_d + middle_n, middle_d)
frac = Fraction(n * middle_d + middle_n, middle_d)
if (frac.numerator // frac.denominator) == 0:
return(f"{frac.numerator % frac.denominator}/{frac.denominator}")
elif ((frac.numerator % frac.denominator)/frac.denominator) == 0/1:
return(f"{frac.numerator // frac.denominator}")
else:
return(f"{frac.numerator // frac.denominator} "f"{frac.numerator % frac.denominator}/{frac.denominator}")```
Solution 24 - C#
Here is a javascript version of btilly's answer. I just wanted to display a float as a fraction so I return a string;
function float_to_fraction(x, error = 0.00001) {
const n = Math.floor(x);
x -= n;
if (x < error) {
return `${n}`;
} else if (1 - error < x) {
return `${n + 1}`;
}
// The lower fraction is 0/1
let lower_n = 0;
let lower_d = 1;
// The upper fraction is 1/1
let upper_n = 1;
let upper_d = 1;
while (true) {
// The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
let middle_n = lower_n + upper_n;
let middle_d = lower_d + upper_d;
// If x + error < middle
if (middle_d * (x + error) < middle_n) {
// middle is our new upper
upper_n = middle_n;
upper_d = middle_d;
// Else If middle < x - error
} else if (middle_n < (x - error) * middle_d) {
// middle is our new lower
lower_n = middle_n;
lower_d = middle_d;
//Else middle is our best fraction
} else {
return `${n * middle_d + middle_n}/${middle_d}`;
}
}
}
Solution 25 - C#
I know this is an old post but wanted to share what I came up with.
public static string ToFraction(this decimal value)
{
decimal numerator = value;
int denominator = 0;
while (numerator % 1 != 0)
{
denominator++;
numerator = value * denominator;
}
return decimal.ToInt32( numerator).ToString() + "/" + denominator.ToString();
}