Алгоритм упрощения десятичной дроби
Я попытался написать алгоритм, упрощающий десятичную дробь, и понял, что это не слишком просто. Удивительно, но я посмотрел в Интернете и все коды, которые я нашел, где либо слишком долго, либо не работал бы в некоторых случаях. Что еще более раздражало, так это то, что они не работали на повторяющиеся десятичные дроби. Мне было интересно, однако, будет ли здесь математик / программист, который понимает все вовлеченные процессы в упрощении десятичной дроби до дроби. Кто-нибудь?
25 ответов
Алгоритм, который дали другие люди, получает ответ, вычисляя Продолженную Дробь числа. Это дает дробную последовательность, которая гарантированно очень и очень быстро сходится. Однако не гарантируется, что вы получите наименьшую дробь, которая находится в эпсилоне на расстоянии от действительного числа. Чтобы обнаружить, что вам нужно пройтись по дереву Штерн-Броко.
Чтобы сделать это, вычтите из пола, чтобы получить число в диапазоне [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)
(код улучшен в феврале 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 раза медленнее остальных.
Стерн-Броко и Ричардс сравнили:
- Оба возвращают хорошие фракции.
- Ричардс часто приводит к меньшей ошибке. Это также немного быстрее.
- Стерн-Броко идет по дереву SB. Он находит часть наименьшего знаменателя, которая соответствует требуемой точности, затем останавливается.
Если вам не требуется наименьшая доля знаменателя, Ричардс - хороший выбор.
Я знаю, что вы сказали, что искали в Интернете, но если вы пропустили следующий документ, это могло бы помочь. Он включает в себя пример кода на Паскале.
Алгоритм для преобразования десятичной дроби в дробь*
Кроме того, как часть стандартной библиотеки, в Ruby есть код, который работает с рациональными числами. Он может конвертировать из числа с плавающей точкой в рациональные и наоборот. Я верю, что вы также можете просмотреть код. Документация находится здесь. Я знаю, что вы не используете Ruby, но это может помочь взглянуть на алгоритмы.
Кроме того, вы можете вызывать код Ruby из C# (или даже писать код Ruby в файле кода C#), если вы используете IronRuby, который работает поверх платформы.net.
*Обновлен до новой ссылки, поскольку кажется, что оригинальный URL не работает ( http://homepage.smc.edu/kennedy_john/DEC2FRAC.pdf)
Наиболее популярными решениями этой проблемы являются алгоритм Ричардса и алгоритм Штерна-Броко, реализованные btilly с оптимизацией скорости с помощью btilly и Jay Zed. Алгоритм Ричардса является самым быстрым, но не гарантирует возврата лучшей доли.
У меня есть решение этой проблемы, которое всегда дает лучшую дробь, а также быстрее, чем все алгоритмы выше. Вот алгоритм на 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 или решения, основанные на повторяющихся десятичных числах, оказались медленнее и / или дают субоптимальные результаты.
Продолжение дроби
Решения, основанные на непрерывной дроби, в основном основаны на двух алгоритмах, оба описаны в статье Иана Ричардса, опубликованной здесь в 1981 году. Он назвал их "алгоритм медленной непрерывной дроби" и "алгоритм быстрой непрерывной дроби". Первый известен как алгоритм Штерна-Броко, а второй известен как алгоритм Ричардса.
Мой алгоритм (краткое объяснение)
Чтобы полностью понять мой алгоритм, вам нужно прочитать статью Яна Ричардса или хотя бы понять, что такое пара Фари. Кроме того, прочитайте алгоритм с комментариями в конце этой статьи.
Алгоритм использует пару Фари, содержащую левую и правую дроби. Повторно принимая посредник, он приближается к целевому значению. Это похоже на медленный алгоритм, но есть два основных различия:
- Многократные итерации выполняются одновременно, пока посредник остается на одной стороне от целевого значения.
- Левая и правая дроби не могут приблизиться к целевому значению, чем заданная точность.
Поочередно правая и левая сторона целевого значения проверяются. Если алгоритм не может выдать результат ближе к целевому значению, процесс заканчивается. Полученный медиант является оптимальным решением.
Тест скорости
Я провел несколько тестов скорости на своем ноутбуке по следующим алгоритмам:
- Улучшен медленный алгоритм от Kay Zed и btilly
- Реализация алгоритма Fast Джона Кеннеди, преобразованная в C# Кей Зед
- Моя реализация алгоритма Fast (близка к оригиналу Иана Ричардса)
- Реализация быстрого алгоритма Джереми Хермана
- Мой алгоритм выше
Я пропустил оригинальный медленный алгоритм из-за его плохой производительности в худшем случае.
Тестовый набор
Я выбираю набор целевых значений (очень произвольно) и рассчитываю дробь 100000 раз с 5 различными значениями точности. Поскольку некоторые (будущие) алгоритмы не могли обрабатывать неправильные дроби, были протестированы только целевые значения от 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% медленнее, чем самый быстрый алгоритм ".
С другой стороны, даже самый медленный алгоритм выполняет вычисления в среднем менее чем за микросекунду. Так что в нормальных условиях скорость не является проблемой. На мой взгляд, лучший алгоритм - это в основном дело вкуса, поэтому выбирайте любой из проверенных алгоритмов по другим критериям.
- Алгоритм дает лучший результат?
- Доступен ли алгоритм на моем любимом языке?
- Каков размер кода алгоритма?
- Является ли алгоритм читаемым, понятным?
Исходный код
Исходный код ниже содержит все используемые алгоритмы. Это включает:
- Мой оригинальный алгоритм (с комментариями)
- Еще более быстрая версия моего алгоритма (но менее читабельная)
- Оригинальный медленный алгоритм
- Все проверенные алгоритмы
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);
}
}
Я нашел ту же статью, на которую ссылался Мэтт, и взял секунду и реализовал ее на Python. Может быть, увидев ту же идею в коде, станет понятнее. Конечно, вы запросили ответ на C#, а я даю его вам на Python, но это довольно тривиальная программа, и я уверен, что ее будет легко перевести. Параметры num (десятичное число, которое вы хотите преобразовать в рациональное) и epsilon (максимально допустимая разница между num и рассчитывается рационально). Некоторые быстрые тестовые прогоны обнаруживают, что обычно сходятся только две или три итерации, когда epsilon около 1е-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, соответственно).
Другое редактирование (я не думал, что это было бы так интересно!): Если вы хотите узнать больше о теории, лежащей в основе этого алгоритма, в Википедии есть отличная страница по алгоритму Евклида.
Вы не можете представлять повторяющиеся десятичные числа в.net, поэтому я проигнорирую эту часть вашего вопроса.
Вы можете представлять только конечное и относительно небольшое количество цифр.
Там очень простой алгоритм:
- принять десятичную
x - посчитать количество цифр после десятичной точки; позвони
n - создать дробь
(10^n * x) / 10^n - удалить общие факторы из числителя и знаменателя.
так что если у вас есть 0,44, вы бы посчитали 2 знака после запятой - n = 2, а затем напишите
(0.44 * 10^2) / 10^2- знак равно
44 / 100 - факторинг (удаление общего множителя 4) дает
11 / 25
Это версия C# алгоритма Иана Ричардса / Джона Кеннеди. Другие ответы здесь с использованием этого же алгоритма:
- Мэтт (ссылки только на статью Кеннеди)
- Haldean Brown (Python)
- Джереми Херман (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);
}
Я написал быстрый класс, который проходит довольно быстро и дает ожидаемые результаты. Вы также можете выбрать свою точность. Это намного проще из любого кода, который я видел, и работает быстро.
//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;
}
}
}
Вот C# версия примера Python Уилла Брауна. Я также изменил его для обработки отдельных целых чисел (например, "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()
);
}
Я пришел с очень поздним ответом. Код взят из статьи Ричардса, опубликованной в 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); }
}
сожалею
Я думаю, что этот ответ относится к тому же алгоритму. Я не видел этого раньше...
Этот алгоритм Дэвида Эппштейна, UC Irvine, основанный на теории непрерывных дробей и первоначально в C, был переведен мной на C#. Фракции, которые он генерирует, удовлетворяют запасу ошибок, но в большинстве случаев выглядят не так хорошо, как решения в других моих ответах. Например 0.5 становится 999/1999 в то время как 1/2 будет предпочтительным при отображении для пользователя (если вам это нужно, см. мои другие ответы).
Существует перегрузка, чтобы указать допустимое значение ошибки как двойное (относительно значения, а не абсолютной ошибки). Для Fraction типа, смотрите мой другой ответ.
Кстати, если ваши фракции могут стать большими, измените соответствующие intс 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);
}
Ну, кажется, мне наконец-то пришлось сделать это самому. Мне просто нужно было создать программу, имитирующую естественный способ, которым я бы решил ее сам. Я только что отправил код в codeproject, так как выписывание всего кода здесь не подходит. Вы можете скачать проект отсюда Fraction_Conversion или посмотреть страницу проекта кода здесь.
Вот как это работает:
- Узнайте, является ли данный десятичный знак отрицательным
- Преобразовать десятичное в абсолютное значение
- Получить целую часть заданного десятичного числа
- Получить десятичную часть
- Проверьте, повторяется ли десятичное число. Если десятичная дробь повторяется, мы возвращаем точное повторяющееся десятичное
- Если десятичное число не повторяется, начните сокращение, изменив числитель на 10^ нет. десятичного числа, иначе мы вычтем 1 из числителя
- Затем уменьшите дробь
Предварительный просмотр кода:
private static string dec2frac(double dbl)
{
char neg = ' ';
double dblDecimal = dbl;
if (dblDecimal == (int) dblDecimal) return dblDecimal.ToString(); //return no if it's not a decimal
if (dblDecimal < 0)
{
dblDecimal = Math.Abs(dblDecimal);
neg = '-';
}
var whole = (int) Math.Truncate(dblDecimal);
string decpart = dblDecimal.ToString().Replace(Math.Truncate(dblDecimal) + ".", "");
double rN = Convert.ToDouble(decpart);
double rD = Math.Pow(10, decpart.Length);
string rd = recur(decpart);
int rel = Convert.ToInt32(rd);
if (rel != 0)
{
rN = rel;
rD = (int) Math.Pow(10, rd.Length) - 1;
}
//just a few prime factors for testing purposes
var primes = new[] {41, 43, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2};
foreach (int i in primes) reduceNo(i, ref rD, ref rN);
rN = rN + (whole*rD);
return string.Format("{0}{1}/{2}", neg, rN, rD);
}
Спасибо @ Darius за предоставленную мне идею о том, как решить повторяющиеся десятичные дроби:)
Повторяющаяся десятичная дробь может быть представлена двумя конечными десятичными знаками: левая часть перед повторением и повторяющаяся часть. Например 1.6181818... = 1.6 + 0.1*(0.18...), Думайте об этом как a + b * sum(c * 10**-(d*k) for k in range(1, infinity)) (в нотации Python здесь). В моем примере a=1.6, b=0.1, c=18, d=2 (количество цифр в c). Бесконечная сумма может быть упрощена (sum(r**k for r in range(1, infinity)) == r / (1 - r) если я правильно помню), уступая a + b * (c * 10**-d) / (1 - c * 10**-d))конечное соотношение. То есть начнем с a, b, c, а также d как рациональные числа, и вы в конечном итоге с другим.
(Это детализирует ответ Кирка Бродхерста, который является правильным, но не распространяется на повторяющиеся десятичные дроби. Я не обещаю, что не допустил ошибок выше, хотя я уверен, что общий подход работает.)
Недавно мне пришлось выполнить эту задачу работы с десятичным типом данных, который хранится в нашей базе данных SQL Server. На уровне представления это значение было отредактировано как дробное значение в TextBox. Сложность здесь заключалась в работе с десятичным типом данных, который содержит довольно большие значения по сравнению с int или long. Поэтому, чтобы уменьшить вероятность переполнения данных, я придерживался десятичного типа данных на протяжении всего преобразования.
Прежде чем я начну, я хочу прокомментировать предыдущий ответ Кирка. Он абсолютно прав, пока не сделано никаких предположений. Однако, если разработчик ищет только повторяющиеся шаблоны в пределах десятичного типа данных.3333333... можно представить как 1/3. Пример алгоритма можно найти на basic-matmatics.com. Опять же, это означает, что вы должны делать предположения на основе доступной информации, и при использовании этого метода фиксируется только очень небольшое подмножество повторяющихся десятичных знаков. Однако для небольших номеров должно быть в порядке.
Двигаясь вперед, позвольте мне сделать снимок моего решения. Если вы хотите прочитать полный пример с дополнительным кодом, я создал пост в блоге с гораздо более подробной информацией.
Преобразовать десятичный тип данных в строковую дробь
public static void DecimalToFraction(decimal value, ref decimal sign, ref decimal numerator, ref decimal denominator)
{
const decimal maxValue = decimal.MaxValue / 10.0M;
// e.g. .25/1 = (.25 * 100)/(1 * 100) = 25/100 = 1/4
var tmpSign = value < decimal.Zero ? -1 : 1;
var tmpNumerator = Math.Abs(value);
var tmpDenominator = decimal.One;
// While numerator has a decimal value
while ((tmpNumerator - Math.Truncate(tmpNumerator)) > 0 &&
tmpNumerator < maxValue && tmpDenominator < maxValue)
{
tmpNumerator = tmpNumerator * 10;
tmpDenominator = tmpDenominator * 10;
}
tmpNumerator = Math.Truncate(tmpNumerator); // Just in case maxValue boundary was reached.
ReduceFraction(ref tmpNumerator, ref tmpDenominator);
sign = tmpSign;
numerator = tmpNumerator;
denominator = tmpDenominator;
}
public static string DecimalToFraction(decimal value)
{
var sign = decimal.One;
var numerator = decimal.One;
var denominator = decimal.One;
DecimalToFraction(value, ref sign, ref numerator, ref denominator);
return string.Format("{0}/{1}", (sign * numerator).ToString().TruncateDecimal(),
denominator.ToString().TruncateDecimal());
}
Это довольно просто, когда DecimalToFraction (десятичное значение) является не чем иным, как упрощенной точкой входа для первого метода, который обеспечивает доступ ко всем компонентам, составляющим дробь. Если у вас есть десятичное число.325, то разделите его на 10 в степени числа десятичных знаков. Наконец, уменьшить долю. И в этом примере.325 = 325/10^3 = 325/1000 = 13/40.
Далее идем в другом направлении.
Преобразовать дробную строку в десятичный тип данных
static readonly Regex FractionalExpression = new Regex(@"^(?<sign>[-])?(?<numerator>\d+)(/(?<denominator>\d+))?$");
public static decimal? FractionToDecimal(string fraction)
{
var match = FractionalExpression.Match(fraction);
if (match.Success)
{
// var sign = Int32.Parse(match.Groups["sign"].Value + "1");
var numerator = Int32.Parse(match.Groups["sign"].Value + match.Groups["numerator"].Value);
int denominator;
if (Int32.TryParse(match.Groups["denominator"].Value, out denominator))
return denominator == 0 ? (decimal?)null : (decimal)numerator / denominator;
if (numerator == 0 || numerator == 1)
return numerator;
}
return null;
}
Преобразование обратно в десятичное также довольно просто. Здесь мы анализируем дробные компоненты, сохраняем их во что-то, с чем мы можем работать (здесь десятичные значения) и выполняем наше деление.
Мои 2 цента. Вот VB.NET-версия отличного алгоритма btilly:
Public Shared Sub float_to_fraction(x As Decimal, ByRef Numerator As Long, ByRef Denom As Long, Optional ErrMargin As Decimal = 0.001)
Dim n As Long = Int(Math.Floor(x))
x -= n
If x < ErrMargin Then
Numerator = n
Denom = 1
Return
ElseIf x >= 1 - ErrMargin Then
Numerator = n + 1
Denom = 1
Return
End If
' The lower fraction is 0/1
Dim lower_n As Integer = 0
Dim lower_d As Integer = 1
' The upper fraction is 1/1
Dim upper_n As Integer = 1
Dim upper_d As Integer = 1
Dim middle_n, middle_d As Decimal
While True
' The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
middle_n = lower_n + upper_n
middle_d = lower_d + upper_d
' If x + error < middle
If middle_d * (x + ErrMargin) < middle_n Then
' middle is our new upper
upper_n = middle_n
upper_d = middle_d
' Else If middle < x - error
ElseIf middle_n < (x - ErrMargin) * middle_d Then
' middle is our new lower
lower_n = middle_n
lower_d = middle_d
' Else middle is our best fraction
Else
Numerator = n * middle_d + middle_n
Denom = middle_d
Return
End If
End While
End Sub
Я знаю, что это старый пост, но хотел поделиться тем, что придумал.
public static string ToFraction(this decimal value)
{
decimal numerator = value;
int denominator = 0;
while (numerator % 1 != 0)
{
denominator++;
numerator = value * denominator;
}
return decimal.ToInt32( numerator).ToString() + "/" + denominator.ToString();
}
Простое решение / разбивка повторяющихся десятичных.
Я взял логику, что числа 1-9, разделенные на 9, повторяются. АКА 7/9 = .77777
Моим решением было бы умножить целое число на 9, добавить повторяющееся число, а затем снова разделить на 9.
Ex: 28.66666
28*9=252
252+6=258
258/9=28.66666
Этот метод довольно прост в программировании. Усечь десятичную цифру, умножить на 9, добавить сначала десятичную, а затем разделить на 9.
Единственное, чего не хватает, так это того, что дробь, возможно, придется упростить, если левое число делится на 3.
Если бы я был тобой, я бы справился с проблемой "нет повторяющихся десятичных знаков в.NET", если бы он преобразовывал строки с рекуррентностью, помеченной каким-либо образом.
Например, 1/3 можно представить как "0.R3" 1/60 можно представить как "0.01R6"
Я бы потребовал явного приведения из двойного или десятичного числа, потому что такие значения можно было преобразовать только в дробную часть, которая была близка. Неявное приведение от int в порядке.
Вы можете использовать структуру и хранить свою дробь (f) в двух длинных p и q, таких что f=p/q, q!=0 и gcd(p, q) == 1.
Первая функция получает строку формата fration "1/2", вторая находит gcd(наибольший общий делитель) для частей вверх и вниз.
public static string DoubleToFraction(double num)
{
if (Math.Round(num, 6) == Math.Round(num, 0))
return Math.Round(num, 0).ToString();
bool minus = (num < 0) ? true : false;
int up;
if (minus)
up = (int)((Math.Round(num, 6) - 0.000001) * 362880);
else
up = (int)((Math.Round(num, 6) + 0.000001) * 362880);
int down = 362880;
int div = gcd(up, down);
up /= div;
down /= div;
return up + "/" + down;
}
public static int gcd(int a, int b)
{
if (b == 0)
return Math.Abs(a);
return gcd(b, a % b);
}
Вот два преобразования Swift 4 из популярных ответов на эту проблему:
public func decimalToFraction(_ d: Double) -> (Int, Int) {
var df: Double = 1
var top: Int = 1
var bot: Int = 1
while df != d {
if df < d {
top += 1
} else {
bot += 1
top = Int(d * bot)
}
df = top / bot
}
return (top, bot)
}
public func realToFraction(_ value: Double, accuracy: Double = 0.00005) -> (Int, Int)? {
var value = value
guard accuracy >= 0 && accuracy <= 1 else {
Swift.print(accuracy, "Must be > 0 and < 1.")
return nil
}
let theSign = sign(value)
if theSign == -1 {
value = abs(value)
}
// Accuracy is the maximum relative error; convert to absolute maxError
let maxError = theSign == 0 ? accuracy : value * accuracy
let n = floor(value)
value -= n
if value < maxError {
return (Int(theSign * n), 1)
}
if 1 - maxError < value {
return (Int(theSign * (n + 1)), 1)
}
// The lower fraction is 0/1
var lowerN: Double = 0
var lowerD: Double = 1
// The upper fraction is 1/1
var upperN: Double = 1
var upperD: Double = 1
while true {
// The middle fraction is (lowerN + upperN) / (lowerD + upperD)
let middleN = lowerN + upperN
let middleD = lowerD + upperD
if middleD * (value + maxError) < middleN {
// real + error < middle : middle is our new upper
upperN = middleN
upperD = middleD
} else if middleN < (value - maxError) * middleD {
// middle < real - error : middle is our new lower
lowerN = middleN
lowerD = middleD
} else {
// Middle is our best fraction
return (Int(n * middleD + middleN * theSign), Int(middleD))
}
}
}
Здесь вы можете использовать метод для преобразования десятичной дроби в дробные:
/// <summary>
/// Converts Decimals into Fractions.
/// </summary>
/// <param name="value">Decimal value</param>
/// <returns>Fraction in string type</returns>
public string DecimalToFraction(double value)
{
string result;
double numerator, realValue = value;
int num, den, decimals, length;
num = (int)value;
value = value - num;
value = Math.Round(value, 5);
length = value.ToString().Length;
decimals = length - 2;
numerator = value;
for (int i = 0; i < decimals; i++)
{
if (realValue < 1)
{
numerator = numerator * 10;
}
else
{
realValue = realValue * 10;
numerator = realValue;
}
}
den = length - 2;
string ten = "1";
for (int i = 0; i < den; i++)
{
ten = ten + "0";
}
den = int.Parse(ten);
num = (int)numerator;
result = SimplifiedFractions(num, den);
return result;
}
/// <summary>
/// Converts Fractions into Simplest form.
/// </summary>
/// <param name="num">Numerator</param>
/// <param name="den">Denominator</param>
/// <returns>Simplest Fractions in string type</returns>
string SimplifiedFractions(int num, int den)
{
int remNum, remDen, counter;
if (num > den)
{
counter = den;
}
else
{
counter = num;
}
for (int i = 2; i <= counter; i++)
{
remNum = num % i;
if (remNum == 0)
{
remDen = den % i;
if (remDen == 0)
{
num = num / i;
den = den / i;
i--;
}
}
}
return num.ToString() + "/" + den.ToString();
}
}
Вот алгоритм, реализованный в VB, который преобразует десятичную с плавающей запятой в целочисленную дробь, которую я написал много лет назад.
Обычно вы начинаете с числителя = 0 и знаменателя = 1, затем, если частное меньше десятичного, добавьте 1 к числителю, а если частное больше десятичного, добавьте 1 к знаменателю. Повторяйте, пока не достигнете желаемой точности.
Вот javascript-версия ответа btilly. Я просто хотел отобразить число с плавающей запятой в виде дроби, поэтому возвращаю строку;
function float_to_fraction(x, error = 0.00001) {
const n = Math.floor(x);
x -= n;
if (x < error) {
return `${n}`;
} else if (1 - error < x) {
return `${n + 1}`;
}
// The lower fraction is 0/1
let lower_n = 0;
let lower_d = 1;
// The upper fraction is 1/1
let upper_n = 1;
let upper_d = 1;
while (true) {
// The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
let middle_n = lower_n + upper_n;
let 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
} else if (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}`;
}
}
}
Я попытался расширить ответ btilly
. Изменения: Если вы хотите отобразить его в формате fration, измените последнюю часть ответа btilly. Таким образом, модифицированный код становится:
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)
frac = Fraction(n * middle_d + middle_n, middle_d)
if (frac.numerator // frac.denominator) == 0:
return(f"{frac.numerator % frac.denominator}/{frac.denominator}")
elif ((frac.numerator % frac.denominator)/frac.denominator) == 0/1:
return(f"{frac.numerator // frac.denominator}")
else:
return(f"{frac.numerator // frac.denominator} "f"{frac.numerator % frac.denominator}/{frac.denominator}")```
Вот алгоритм, который я написал для проекта не так давно. Требуется другой подход, который больше похож на то, что вы бы сделали вручную. Я не могу гарантировать его эффективность, но он выполняет свою работу.
public static string toFraction(string exp) {
double x = Convert.ToDouble(exp);
int sign = (Math.Abs(x) == x) ? 1 : -1;
x = Math.Abs(x);
int n = (int)x; // integer part
x -= n; // fractional part
int mult, nm, dm;
int decCount = 0;
Match m = Regex.Match(Convert.ToString(x), @"([0-9]+?)\1+.?$");
// repeating fraction
if (m.Success) {
m = Regex.Match(m.Value, @"([0-9]+?)(?=\1)");
mult = (int)Math.Pow(10, m.Length);
// We have our basic fraction
nm = (int)Math.Round(((x * mult) - x));
dm = mult - 1;
}
// get the number of decimal places
else {
double t = x;
while (t != 0) {
decCount++;
t *= 10;
t -= (int)t;
}
mult = (int)Math.Pow(10, decCount);
// We have our basic fraction
nm = (int)((x * mult));
dm = mult;
}
// can't be simplified
if (nm < 0 || dm < 0) return exp;
//Simplify
Stack factors = new Stack();
for (int i = 2; i < nm + 1; i++) {
if (nm % i == 0) factors.Push(i); // i is a factor of the numerator
}
// check against the denominator, stopping at the highest match
while(factors.Count != 0) {
// we have a common factor
if (dm % (int)factors.Peek() == 0) {
int f = (int)factors.Pop();
nm /= f;
dm /= f;
break;
}
else factors.Pop();
}
nm += (n * dm);
nm *= sign;
if (dm == 1) return Convert.ToString(nm);
else return Convert.ToString(nm) + "/" + Convert.ToString(dm);
}