简化小数到分数的algorithm

我试着写一个algorithm来简化小数到小数部分，并意识到它不是太简单。 令人惊讶的是，我在网上查找，发现所有代码太长，或在某些情况下无法使用。 更令人讨厌的是，他们不适用于循环小数。 然而，我想知道是否会有一位math家/程序员理解所有涉及将小数简化为小数的过程。 任何人？

Answer 1

其他人给你的algorithm通过计算数字的连续分数得到答案。 这给出了保证非常迅速地收敛的分数序列。 但是， 不能保证给你的实际数字的距离内的最小分数。 发现你必须走斯特布鲁克特树 。

要做到这一点，你从地板上减去得到的数字在[0,1]范围内，那么你的下限估计是0，你的上限估计是1.现在做一个二进制search，直到你足够接近。 在每次迭代中，如果你的下半部分是a / b，上半部分是c / d，那么你的中间部分是（a + c）/（b + d）。 testing你的中间对x，或者让中间的上，下，或返回你的最终答案。

这是一些非惯用的（因此，即使你不知道语言，希望可读）Python实现了这个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) 

Answer 2

（代码改进2017年2月 – 向下滚动到“优化”…）

（在这个答案结尾的algorithm比较表）

我用C＃实现了Btilly的答案 …

• 增加了对负数的支持
• 提供accuracy参数来指定最大值。 相对误差，而不是最大值。 绝对错误; 0.01会发现一个分数在1％以内。
• 提供一个优化
• Double.NaN和Double.Infinity不受支持; 你可能想要处理这些（ 例子在这里 ）。

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

Fractiontypes只是一个简单的结构。 当然，使用你自己喜欢的types…（我喜欢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; } } 

2017年2月优化

对于某些值，如0.01等，该algorithm经历数百或数千次线性迭代。 为了解决这个问题，我实现了一个find最终价值的二进制方法 – 多亏了这个想法。 在if语句中replace如下：

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

和

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

这里是Seek方法的实现：

 /// <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比较表

您可能希望将表格复制到文本编辑器以进行全屏查看。

 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 

性能比较

我进行了详细的速度testing并绘制了结果。 不看质量和速度：

• 斯特恩 – 布鲁科特（Stern-Brocot） 优化最多可以减慢2倍，但当碰到不幸的数值时，斯特恩 – 布鲁科（Stern-Brocot）的速度可能会降低数百或数千倍。 尽pipe每次调用仍然只有几个微秒。
• 理查兹一贯快。
• Eppstein比其他人慢3倍左右。

斯特恩 – 布罗科特和理查兹比较：

• 都返回好分数。
• Richards经常导致一个更小的错误。 它也快一点。
• 斯特恩 – 布罗科特走下SB树。 它find满足所需精度的最低分母的分数，然后停止。

如果你不需要最小分母分数，理查兹是一个不错的select。

Answer 3

我知道你说过你在网上search，但如果你错过了下面的文章，可能会有一些帮助。 它包含了一个在Pascal中的代码示例。

algorithm将十进制转换为分数 ^*

另外，作为标准库的一部分，Ruby有处理有理数的代码。 它可以从花车转换为理智，反之亦然。 我相信你也可以查看代码。 文档在这里find。 我知道你没有使用Ruby，但是看看algorithm可能会有所帮助。

此外，如果您使用运行在.net框架之上的IronRuby ，则可以从C＃中调用Ruby代码（甚至可以在C＃代码文件中编写Ruby代码）。

* _{更新为新链接，因为它显示原始url已损坏（ http://homepage.smc.edu/kennedy_john/DEC2FRAC.pdf ）}

Answer 4

我find了Matt引用的同一篇文章，我花了一秒钟，用Python实现它。 也许在代码中看到相同的想法会使其更清晰。 当然，你在C＃中请求了一个答案，我用Python给你，但这是一个相当简单的程序，我相信这将是很容易翻译。 参数是num （您想要转换为有理数的小数）和epsilon （ num与计算的有理数之间允许的最大差值）。 一些快速testing运行发现，当epsilon在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] 

编辑：我只是注意到你想要他们与重复小数工作的笔记。 我不知道任何语言都支持循环小数的语法，所以我不知道如何处理它们，但通过此方法运行0.6666666和0.166666返回正确的结果（2/3和1/6，分别）。

另一个编辑（我不认为这将是如此有趣！）：如果你想更多地了解这个algorithm背后的理论， 维基百科有一个优秀的欧几里德algorithm

Answer 5

这是Will Brown的python示例的C＃版本。 我也改变它来处理单独的整数（例如“2 1/8”而不是“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() ); } 

Answer 6

我写了一个快速的课，运行速度相当快，给出了我期望的结果。 你也可以select你的精度。 从我看到的任何代码中，它都简单得多，而且运行速度也很快。

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

Answer 7

你不能在.net中表示一个重复的小数，所以我会忽略你的问题的一部分。

你只能表示一个有限的和相对较less的数字。

有一个非常简单的algorithm：

• 带小数点x
• 统计小数点后的位数; 打电话给这个n
• 创build一个分数(10^n * x) / 10^n
• 从分子和分母中删除共同的因素。

所以如果你有0.44，你会计数2个地方是小数点 – n = 2，然后写

• (0.44 * 10^2) / 10^2
• = 44 / 100
• 因子分解（去除4的公因子）给出11/25

Answer 8

我想出了一个很晚的答案。 代码取自Richards 1981年出版的一篇文章，并写在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/(gs); 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; } 

我在这里重写我的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; } 

在这里，我提出一些错误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 | 

正如你所看到的，这两种方法或多或less地产生了相同的结果，但理查德的效率更高，更容易实施。

编辑

为了编译我的代码，你需要为my::sign定义一个简单的函数，它返回一个variables的符号。 这是我的实现

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

抱歉

我想这个答案是指相同的algorithm。 我以前没有看到…

Answer 9

UC Irvine的David Eppstein基于连续分数的理论，最初是C语言，这个algorithm被我翻译成C＃。 它产生的分数满足误差，但大多不像我的其他答案的解决scheme。 例如0.5变为999/1999而当显示给用户时， 1/2是首选的（如果你需要的话，参见我的其他 答案 ）。

有一个重载将错误容限指定为double（相对于值，而不是绝对错误）。 对于Fractiontypes，请参阅我的其他答案。

顺便说一句，如果你的分数可以变大，把相关的int改为long 。 与其他algorithm相比，这个algorithm容易溢出。

例如值和其他algorithm的比较，请参阅我的其他答案

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

Answer 10

循环小数可以用两个有限小数表示：重复前的左边部分和重复部分。 例如1.6181818... = 1.6 + 0.1*(0.18...) 。 可以把它想象成a + b * sum(c * 10**-(d*k) for k in range(1, infinity)) （这里用Python表示法）。 在我的例子中， a=1.6 ， b=0.1 ， c=18 ， d=2 （ c的位数）。 无穷和可以简化（如果我能正确记得， sum(r**k for r in range(1, infinity)) == r / (1 - r) ），得到a + b * (c * 10**-d) / (1 - c * 10**-d)) ，一个有限的比例。 也就是说，从a ， b ， c和d有理数，最后得到另一个。

（这个阐述了Kirk Broadhurst的答案，尽pipe这是正确的，但是不包括重复小数，我不保证以上没有犯错误，尽pipe我相信这个一般方法是有效的。）

Answer 11

我最近不得不执行这个使用存储在我们的SQL Server数据库中的十进制数据types的任务。 在表示层，这个值被编辑为一个文本框中的一个小数值。 这里的复杂性是与十进制数据types一起工作的，该types与int或long相比具有相当大的值。 所以为了减less数据溢出的机会，我在整个转换过程中坚持使用十进制数据types。

在开始之前，我想对柯克先前的回答发表评论。 只要没有任何假设，他是绝对正确的。 但是，如果开发人员仅在十进制数据types的范围内查找重复模式，则可以将其表示为1/3。 这个algorithm的例子可以在basic-mathematics.comfind。 同样，这意味着您必须根据可用的信息进行假设，并且使用此方法仅捕获重复小数的非常小的子集。 但是对于小数字应该没问题。

向前走，让我给你一个我的解决scheme的快照。 如果你想阅读一个完整的例子，我创build了一个更详细的博客文章 。

将十进制数据types转换为string分数

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

Answer 12

我的2美分。 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 

Answer 13

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 .

这是如何工作的：

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 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 🙂

Answer 14

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

Answer 15

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

怎么运行的

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 

结果

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?

源代码

The source code below contains all used algorithms. 这包括：

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

Answer 16

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.

Answer 17

If I were you I'd handle the "no repeating decimals in .NET" problem by having it convert strings 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.

Answer 18

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

Answer 19

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

Answer 20

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.