Алгоритм упрощения десятичной дроби

Question

Я попытался написать алгоритм, упрощающий десятичную дробь, и понял, что это не слишком просто. Удивительно, но я посмотрел в Интернете и все коды, которые я нашел, где либо слишком долго, либо не работал бы в некоторых случаях. Что еще более раздражало, так это то, что они не работали на повторяющиеся десятичные дроби. Мне было интересно, однако, будет ли здесь математик / программист, который понимает все вовлеченные процессы в упрощении десятичной дроби до дроби. Кто-нибудь?

Answer 1

Алгоритм, который вам дали другие люди, получает ответ, вычисляя Continued Fraction числа. Это дает дробную последовательность, которая гарантированно очень и очень быстро сходится. Тем не менее, не гарантированно даст вам наименьшую дробь, которая находится на расстоянии эпсилона от действительного числа. Чтобы обнаружить, что вам нужно пройтись по дереву Штерн-Брокот .

Чтобы сделать это, вычтите из пола, чтобы получить число в диапазоне [0, 1), тогда ваша нижняя оценка равна 0, а ваша верхняя оценка равна 1. Теперь выполните бинарный поиск, пока вы не окажетесь достаточно близко. На каждой итерации, если ваш нижний равен a / b, а ваш верхний равен c / d, ваш средний равен (a + c) / (b + d). Проверьте свою середину против x и сделайте середину верхней, нижней или верните свой окончательный ответ.

Здесь приведен не очень идиоматический (и, следовательно, надеюсь, читаемый, даже если вы не знаете язык) Python, который реализует этот алгоритм.

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 г. - прокрутите вниз до пункта «оптимизация» ...)

(таблица сравнения алгоритмов в конце этого ответа)

Я реализовал ответ btilly в C # и ...

• добавлена ​​поддержка отрицательных чисел
• укажите параметр 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);
        }
    }
}

Тип Fraction - это простая структура. Конечно, используйте свой предпочтительный тип ... (мне нравится этот Рика Дэвина.)

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 г. оптимизация

Для определенных значений, таких как 0.01, 0.001 и т. Д., Алгоритм проходит сотни или тысячи линейных итераций. Чтобы исправить это, я реализовал двоичный способ определения конечного значения - спасибо btilly за эту идею. Внутри if -составления подставьте следующее:

// 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 замедляет его максимум в 2 раза, но оригинальный Stern-Brocot может быть в сотни или тысячи раз медленнее, когда он достигает упомянутых неудачных значений. Это по-прежнему всего пара микросекунд на звонок.
• Ричардс неизменно быстр.
• Эппштайн примерно в 3 раза медленнее других.

Стерн-Броко и Ричардс по сравнению:

• Оба возвращают хорошие дроби.
• Ричардс часто приводит к меньшей ошибке. Это также немного быстрее.
• Штерн-Броко идет по дереву S-B. Он находит часть наименьшего знаменателя, которая соответствует требуемой точности, затем останавливается.

Если вам не требуется наименьшая доля знаменателя, Ричардс - хороший выбор.

Answer 3

Я знаю, что вы сказали, что искали в Интернете, но если вы пропустили следующую статью, это может помочь. Включает пример кода на Паскале.

Алгоритм преобразования десятичной дроби в дробные ^*

В качестве альтернативы, как часть стандартной библиотеки, в Ruby есть код, который работает с рациональными числами. Он может конвертировать из числа с плавающей точкой в ​​рациональные и наоборот. Я верю, что вы также можете просмотреть код. Документация найдена здесь . Я знаю, что вы не используете Ruby, но это может помочь взглянуть на алгоритмы.

Кроме того, вы можете вызывать код Ruby из C # (или даже писать код Ruby в файле кода C #), если вы используете IronRuby , который работает поверх платформы .net.

* _{Обновлен до новой ссылки, так как кажется, что исходный URL не работает (http://homepage.smc.edu/kennedy_john/DEC2FRAC.pdf)}

Answer 4

Я нашел ту же статью, на которую ссылался Мэтт, и взял секунду и реализовал ее на 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,соответственно).

Другое редактирование (я не думал, что это было бы так интересно!): Если вы хотите узнать больше о теории, лежащей в основе этого алгоритма, В Википедии есть отличная страница по алгоритму Евклида

Answer 5

Вы не можете представлять повторяющиеся десятичные числа в .net, поэтому я проигнорирую эту часть вашего вопроса.

Вы можете представлять только конечное и относительно небольшое количество цифр.

Существует чрезвычайно простой алгоритм:

• принимает десятичное число x
• считать количество цифр после десятичной точки;назовите это n
• создайте дробь (10^n * x) / 10^n
• удалите общие множители из числителя и знаменателя.

так что если у вас 0,44, вы бы посчитали2 знака после запятой - n = 2, а затем написать

• (0.44 * 10^2) / 10^2
• = 44 / 100
• факторинг (удаление общего множителя 4)т 11 / 25

Answer 6

Вот 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 7

Я написал быстрый класс, который работает довольно быстро и дает ожидаемые результаты. Вы также можете выбрать свою точность. Это намного проще из любого кода, который я видел, и работает быстро.

//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 8

Это версия алгоритма на C # Ian Richards / John Kennedy.Другие ответы здесь с использованием этого же алгоритма:

• Matt (только ссылки на статью Кеннеди)
• Haldean Brown (Python)
• Джереми Херман (C #)
• PinkFloyd (C)

Он не обрабатывает бесконечности и NaN.

Этот алгоритм быстрый .

Примеры значений и сравнение с другими алгоритмами см. Мой другой ответ

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 9

Этот алгоритм Дэвида Эппштейна, UC Irvine, основанный на теории непрерывных дробей и первоначально в C, был переведен мной на C #.Фракции, которые он генерирует, удовлетворяют запасу ошибок, но в большинстве случаев выглядят не так хорошо, как решения других моих ответов.Например, 0.5 становится 999/1999, тогда как 1/2 будет предпочтительным при отображении для пользователя (если вам это нужно, см. Мои другие ответы ).

Имеется перегрузка для указания допустимой погрешности как двойного (относительно значения, а не абсолютной ошибки).Для типа Fraction см. Мой другой ответ.

Кстати, если ваши дроби могут стать большими, измените соответствующие int s на long.По сравнению с другими алгоритмами этот склонен к переполнению.

Пример значений и сравнение с другими алгоритмами см. мой другой ответ

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

Я пришел с очень поздним ответом. Код взят из статьи из Ричардс опубликовал в 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/(g-s);
        if(err>std::abs(sign*num/den-x0)){ return iter; }
    } while(iter++<1e6);
    std::cerr<<__PRETTY_FUNCTION__<<" : failed to find a fraction for "<<x0<<std::endl;
    return 0;
}

Я переписываю здесь мою реализацию 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 |

Как видите, два метода дают более или менее одинаковые результаты, но единица Ричардса намного эффективнее и проще в реализации.

Редактировать

Для компиляции моего кода вам нужно определение для my::sign, которое просто функция, которая возвращает знак переменной. Вот моя реализация

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

К сожалению

Я думаю этот ответ относится к тому же алгоритму. Я не видел этого раньше ...