Cet algorithme de David Eppstein, UC Irvine, basé sur la théorie des fractions continues et originellement en C, a été traduit en C # par moi. Les fractions qu’il génère satisfont à la marge d’erreur mais ne semblent généralement pas aussi bonnes que les solutions de mes autres réponses. Par exemple, 0.5 devient 999/1999 alors que 1/2 serait préférable lorsqu’il est affiché à un utilisateur (si vous en avez besoin, consultez mes autres réponses ).

Il existe une surcharge pour spécifier la marge d’erreur sous forme de double (par rapport à la valeur, pas à l’erreur absolue). Pour le type de Fraction , voir mon autre réponse.

En passant, si vos fractions peuvent devenir volumineuses, changez les int pertinents pertinents en long . Comparé aux autres algorithmes, celui-ci est sujet au débordement.

Par exemple, les valeurs et une comparaison avec d’autres algorithmes, voir mon autre réponse

 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); } 

Une décimale récurrente peut être représentée par deux décimales finies: la partie gauche avant la répétition et la partie répétée. Par exemple 1.6181818... = 1.6 + 0.1*(0.18...) . Pensez à cela comme a + b * sum(c * 10**-(d*k) for k in range(1, infinity)) (en notation Python ici). Dans mon exemple, a=1.6 , b=0.1 , c=18 , d=2 (le nombre de chiffres dans c ). La sum infinie peut être simplifiée ( sum(r**k for r in range(1, infinity)) == r / (1 - r) si je me souviens bien), donnant a + b * (c * 10**-d) / (1 - c * 10**-d)) , un rapport fini. C’est-à-dire, commençons par a , b , c et d tant que nombres rationnels, et vous vous retrouvez avec un autre.

(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.)

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 Ssortingng Fraction

 public static void DecimalToFraction(decimal value, ref decimal sign, ref decimal numerator, ref decimal denominator) { const decimal maxValue = decimal.MaxValue / 10.0M; // eg .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 Ssortingng Fraction to Decimal Data Type

 static readonly Regex FractionalExpression = new Regex(@"^(?[-])?(?\d+)(/(?\d+))?$"); public static decimal? FractionToDecimal(ssortingng 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.

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 

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 .

Voici comment ça fonctionne:

1. Find out whether given decimal is negative
2. Convert decimal to absolute value
3. Get integer part of given decimal
4. Get the decimal part
5. Check whether decimal is recurring. If decimal is recurring, we then return the exact recurring decimal
6. If decimal is not recurring, start reduction by changing numerator to 10^no. of decimal, else we subtract 1 from numerator
7. Then reduce fraction

Code Preview:

  private static ssortingng dec2frac(double dbl) { char neg = ' '; double dblDecimal = dbl; if (dblDecimal == (int) dblDecimal) return dblDecimal.ToSsortingng(); //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 🙂

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:

1. Multiple iterations are performed at once as long as the mediant stay on one side of the target value.
2. 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:

1. Improved slow algorithm by Kay Zed and btilly
2. John Kennedy’s implementation of the Fast algorithm, converted to C# by Kay Zed
3. My implementation of the Fast algorithm (close to the original by Ian Richards)
4. Jeremy Herrman’s implementation of the Fast algorithm
5. 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 

Résultats

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) / (cd*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 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); } } 

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.

If I were you I’d handle the “no repeating decimals in .NET” problem by having it convert ssortingngs with the recurrence marked somehow.

Eg 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.

Here, you can have the method for converting Decimal into Fractions:

 /// 
 /// Converts Decimals into Fractions. /// 
 /// Decimal value /// Fraction in ssortingng type public ssortingng DecimalToFraction(double value) { ssortingng result; double numerator, realValue = value; int num, den, decimals, length; num = (int)value; value = value - num; value = Math.Round(value, 5); length = value.ToSsortingng().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; } /// 
 /// Converts Fractions into Simplest form. /// 
 /// Numerator /// Denominator /// Simplest Fractions in ssortingng type ssortingng 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(); } } 

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 ssortingng toFraction(ssortingng 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.ToSsortingng(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); } 

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.

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)) } } }