我试着写了一个算法,将小数简化为小数,并意识到这并不是太简单。
例如,将0.333333...编写为1/3。
或者是1/6的0.1666667。
令人惊讶的是,我在网上查找了所有我发现的代码,这些代码要么太长,要么在某些情况下不能工作。更令人恼火的是,它们不适用于重复出现的小数。然而,我想知道这里是否会有一个数学家/程序员,他了解将小数简化为小数的所有相关过程。有没有人?
发布于 2015-10-02 16:57:52
(代码改进了2017年2月-向下滚动到“优化”...)
(本答案末尾的算法比较表)
我在C#中实现了btilly's answer ...
accuracy参数的支持,以指定最大值。相对误差,而不是最大值。绝对错误;如果不支持optimizationDouble.NaN和(example here).,则0.01会发现(example here).的1%以内的分数;您可能需要处理这些0.01
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);
}
}
}Fraction类型只是一个简单的结构。当然,使用您自己的首选类型...(我喜欢里克·戴文的“this one”。)
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、0.001等,算法会经历数百或数千次线性迭代。为了解决这个问题,我实现了一种查找最终值的二进制方法--这要归功于btilly的这个想法。在if-statement中,替换为以下内容:
// 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);
}
}算法对照表
您可能希望将表格复制到文本编辑器以进行全屏查看。
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 性能比较
我执行了详细的速度测试,并绘制了结果。不看质量,只看速度:
Stern-Brocot optimization的
Stern-Brocot和Richards比较:
fractions.
如果您不需要最低分母分数,Richards是一个很好的选择。
发布于 2011-02-26 11:24:05
我找到了Matt引用的同一篇论文,然后我用Python实现了它。也许在代码中看到同样的想法会让它更清晰。当然,您要求的答案是C#的,我现在用Python语言给您答案,但这是一个相当琐碎的程序,我相信它很容易翻译。参数是num (您想要转换为有理数的十进制数)和epsilon ( num和计算出的有理数之间允许的最大差值)。一些快速测试运行发现,当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 )。
另一个编辑(我没想到这会这么有趣!):如果你想更多地了解这个算法背后的理论,Wikipedia has an excellent page on the Euclidian algorithm
发布于 2017-07-26 06:03:17
这个问题最流行的解决方案是Richards’ algorithm和the Stern-Brocot algorithm,由btilly和Jay Zed用speed optimalization实现。Richards的算法是最快的,但不能保证返回最佳分数。
对于这个问题,我有一个解决方案,它总是给出最好的分数,而且比上面所有的算法都要快。这是C#中的算法(下面是解释和速度测试)。
这是一个没有注释的简短算法。在最后的源代码中提供了完整的版本。
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);
}其中,fraction是一个存储分数的简单类,如下所示:
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;
}
}它是如何工作的
像提到的其他解决方案一样,我的解决方案是基于连分式的。其他解决方案,如Eppstein的解决方案或基于重复小数的解决方案,被证明速度较慢和/或给出的结果不是最优的。
连分式
基于连分式的解决方案主要基于两种算法,这两种算法都在Ian Richards于1981年发表的here的一篇文章中进行了描述。他称它们为“慢连分数算法”和“快速连分数算法”。第一种算法被称为Stern-Brocot算法,而后者被称为Richards算法。
My algorithm (简短解释)
要完全理解我的算法,您需要阅读Ian Richards的文章,或者至少了解Farey pair是什么。此外,请阅读本文末尾带有注释的算法。
该算法使用一个Farey对,包含一个左分数和一个右分数。通过反复获取中间值,它正在接近目标值。这就像慢速算法,但有两个主要区别:
只要中值停留在目标值的一侧,
或者,检查目标值的右侧和左侧。如果算法不能产生更接近目标值的结果,则过程结束。得到的中间结果是最优解。
速度测试
我用以下算法在我的笔记本电脑上做了一些速度测试:
我省略了btilly最初的慢速算法,因为它在最坏情况下的性能很差。
测试集
我选择了一组目标值(非常随意),并以5种不同的精度计算了100000次分数。因为一些(未来)算法可能无法处理不正确的分数,所以只测试了0.0到1.0之间的目标值。精度取自小数点后2到6位(0.005到0.0000005)。使用了以下集合:
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结果
我做了13次测试。结果是整个数据集所需的毫秒数。
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结论(跳过分析)
即使没有统计分析,也很容易看出我的算法比其他测试算法更快。然而,与“快速算法”的最快变体的差异不到1%。改进的慢算法比最快算法慢30%-35%。
另一方面,即使是最慢的算法执行计算的平均时间也不到一微秒。所以在正常情况下,速度并不是真正的问题。在我看来,最好的算法主要是一个品味问题,所以根据其他标准选择任何一个经过测试的算法。
我最喜欢的算法是language?
,
源代码
下面的源代码包含了所有使用的算法。它包括:
测试我的原始算法(带注释)我的算法的一个更快的版本(但较少原始的慢速测试算法readable)
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);
}
}https://stackoverflow.com/questions/5124743
复制相似问题