首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >将小数简化为小数的算法

问将小数简化为小数的算法
EN

Stack Overflow用户
提问于 2011-02-26 10:55:54
回答 23查看 41.3K关注 0票数 60

我试着写了一个算法,将小数简化为小数,并意识到这并不是太简单。

例如,将0.333333...编写为1/3。

或者是1/6的0.1666667。

令人惊讶的是,我在网上查找了所有我发现的代码,这些代码要么太长,要么在某些情况下不能工作。更令人恼火的是,它们不适用于重复出现的小数。然而,我想知道这里是否会有一个数学家/程序员,他了解将小数简化为小数的所有相关过程。有没有人?

EN

回答 23

Stack Overflow用户

发布于 2015-10-02 16:57:52

(代码改进了2017年2月-向下滚动到“优化”...)

(本答案末尾的算法比较表)

我在C#中实现了btilly's answer ...

  • 添加了对负accuracy参数的支持,以指定最大值。相对误差,而不是最大值。绝对错误;如果不支持optimization
  • Double.NaN和(example here).

,则0.01会发现(example here).的1%以内的分数;您可能需要处理这些0.01

代码语言:javascript
复制
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”。)

代码语言:javascript
复制
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中,替换为以下内容:

代码语言:javascript
复制
// 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));

和

代码语言:javascript
复制
// 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方法的实现:

代码语言:javascript
复制
/// <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);
    }
}

算法对照表

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

代码语言:javascript
复制
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的

  • 最多只能减慢2倍,但当达到上述不幸数值时,原始的Stern-Brocot可能会慢数百倍或数千倍。这仍然只有几微秒,尽管每个call.
  • Richards的速度都是一致的,fast.
  • Eppstein比其他的慢了大约3倍。

Stern-Brocot和Richards比较:

fractions.

  • Richards和
  • 都会返回较好的结果,通常会导致较小的错误。这也有点像faster.
  • Stern-Brocot沿着S-B树往下走。它会找到满足所需精度的最低分母分数,然后停止。

如果您不需要最低分母分数,Richards是一个很好的选择。

票数 33
EN

Stack Overflow用户

发布于 2011-02-26 11:24:05

我找到了Matt引用的同一篇论文,然后我用Python实现了它。也许在代码中看到同样的想法会让它更清晰。当然,您要求的答案是C#的,我现在用Python语言给您答案,但这是一个相当琐碎的程序,我相信它很容易翻译。参数是num (您想要转换为有理数的十进制数)和epsilon ( num和计算出的有理数之间允许的最大差值)。一些快速测试运行发现,当epsilon约为1e-4时,通常只需两到三次迭代即可收敛。

代码语言:javascript
复制
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

票数 12
EN

Stack Overflow用户

发布于 2017-07-26 06:03:17

这个问题最流行的解决方案是Richards’ algorithm和the Stern-Brocot algorithm,由btilly和Jay Zed用speed optimalization实现。Richards的算法是最快的,但不能保证返回最佳分数。

对于这个问题,我有一个解决方案,它总是给出最好的分数,而且比上面所有的算法都要快。这是C#中的算法(下面是解释和速度测试)。

这是一个没有注释的简短算法。在最后的源代码中提供了完整的版本。

代码语言:javascript
复制
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是一个存储分数的简单类,如下所示:

代码语言:javascript
复制
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对,包含一个左分数和一个右分数。通过反复获取中间值,它正在接近目标值。这就像慢速算法,但有两个主要区别:

只要中值停留在目标值的一侧,

  1. 就会一次执行多次迭代。
  2. 左右分数不能比给定的精度更接近目标值。

或者,检查目标值的右侧和左侧。如果算法不能产生更接近目标值的结果,则过程结束。得到的中间结果是最优解。

速度测试

我用以下算法在我的笔记本电脑上做了一些速度测试:

由Kay Zed and btilly

  • John肯尼迪改进的慢速算法实现的快速算法,由Kay Zed

  • My实现的转换为C#的快速算法(接近原来由Ian Richards)

  • My algorithm above

我省略了btilly最初的慢速算法,因为它在最坏情况下的性能很差。

测试集

我选择了一组目标值(非常随意),并以5种不同的精度计算了100000次分数。因为一些(未来)算法可能无法处理不正确的分数,所以只测试了0.0到1.0之间的目标值。精度取自小数点后2到6位(0.005到0.0000005)。使用了以下集合:

代码语言:javascript
复制
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次测试。结果是整个数据集所需的毫秒数。

代码语言:javascript
复制
    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?

  • What的代码大小的algorithm?

  • Is该算法可读,understandable?

,

源代码

下面的源代码包含了所有使用的算法。它包括:

测试我的原始算法(带注释)我的算法的一个更快的版本(但较少原始的慢速测试算法readable)

  • The

代码语言:javascript
复制
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);
    }

}
票数 9
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5124743

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档