Как преобразовать числа с плавающей запятой в понятные человеку дроби?
https://stackoverflow.com/questions/95727
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Допустим, у нас есть 0.33, нам нужно вывести "1/3".
Если у нас есть "0.4", нам нужно вывести "2/5".
Идея состоит в том, чтобы сделать его доступным для чтения человеком, чтобы пользователь понимал "x частей из y" как лучший способ понимания данных.
Я знаю, что проценты - хорошая замена, но мне было интересно, есть ли простой способ сделать это?
Решение
Я нашел книгу Дэвида Эппштейна найти рациональное приближение к заданному действительному числу Код на языке Си должен быть именно тем, о чем вы просите.Она основана на теории непрерывных дробей и очень быстрая и довольно компактная.
Я использовал версии этого, настроенные для определенных ограничений в числителе и знаменателе.
/*
** find rational approximation to given real number
** David Eppstein / UC Irvine / 8 Aug 1993
**
** With corrections from Arno Formella, May 2008
**
** usage: a.out r d
** r is real number to approx
** d is the maximum denominator allowed
**
** based on the theory of continued fractions
** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
** then best approximation is found by truncating this series
** (with some adjustments in the last term).
**
** Note the fraction can be recovered as the first column of the matrix
** ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
** ( 1 0 ) ( 1 0 ) ( 1 0 )
** Instead of keeping the sequence of continued fraction terms,
** we just keep the last partial product of these matrices.
*/
#include <stdio.h>
main(ac, av)
int ac;
char ** av;
{
double atof();
int atoi();
void exit();
long m[2][2];
double x, startx;
long maxden;
long ai;
/* read command line arguments */
if (ac != 3) {
fprintf(stderr, "usage: %s r d\n",av[0]); // AF: argument missing
exit(1);
}
startx = x = atof(av[1]);
maxden = atoi(av[2]);
/* initialize matrix */
m[0][0] = m[1][1] = 1;
m[0][1] = m[1][0] = 0;
/* loop finding terms until denom gets too big */
while (m[1][0] * ( ai = (long)x ) + m[1][1] <= maxden) {
long t;
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;
if(x==(double)ai) break; // AF: division by zero
x = 1/(x - (double) ai);
if(x>(double)0x7FFFFFFF) break; // AF: representation failure
}
/* now remaining x is between 0 and 1/ai */
/* approx as either 0 or 1/m where m is max that will fit in maxden */
/* first try zero */
printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
startx - ((double) m[0][0] / (double) m[1][0]));
/* now try other possibility */
ai = (maxden - 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];
printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
startx - ((double) m[0][0] / (double) m[1][0]));
}
Другие советы
Начиная с Python 2.6, существует fractions модуль.
(Цитирую из документов.)
>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)
>>> from math import pi, cos
>>> Fraction.from_float(cos(pi/3))
Fraction(4503599627370497, 9007199254740992)
>>> Fraction.from_float(cos(pi/3)).limit_denominator()
Fraction(1, 2)
Если вывод должен дать читателю-человеку быстрое представление о порядке результата, нет смысла возвращать что-то вроде "113/211", поэтому вывод должен ограничиваться использованием однозначных чисел (и, возможно, 1/10 и 9/10).Если это так, то вы можете заметить, что их всего 27 другой дроби.
Поскольку математика, лежащая в основе генерации выходных данных, никогда не изменится, решением могло бы быть простое жесткое кодирование двоичного дерева поиска, чтобы функция выполняла не более log (27) ~ = 4 3/4 сравнений.Вот протестированная версия кода на языке Си
char *userTextForDouble(double d, char *rval)
{
if (d == 0.0)
return "0";
// TODO: negative numbers:if (d < 0.0)...
if (d >= 1.0)
sprintf(rval, "%.0f ", floor(d));
d = d-floor(d); // now only the fractional part is left
if (d == 0.0)
return rval;
if( d < 0.47 )
{
if( d < 0.25 )
{
if( d < 0.16 )
{
if( d < 0.12 ) // Note: fixed from .13
{
if( d < 0.11 )
strcat(rval, "1/10"); // .1
else
strcat(rval, "1/9"); // .1111....
}
else // d >= .12
{
if( d < 0.14 )
strcat(rval, "1/8"); // .125
else
strcat(rval, "1/7"); // .1428...
}
}
else // d >= .16
{
if( d < 0.19 )
{
strcat(rval, "1/6"); // .1666...
}
else // d > .19
{
if( d < 0.22 )
strcat(rval, "1/5"); // .2
else
strcat(rval, "2/9"); // .2222...
}
}
}
else // d >= .25
{
if( d < 0.37 ) // Note: fixed from .38
{
if( d < 0.28 ) // Note: fixed from .29
{
strcat(rval, "1/4"); // .25
}
else // d >=.28
{
if( d < 0.31 )
strcat(rval, "2/7"); // .2857...
else
strcat(rval, "1/3"); // .3333...
}
}
else // d >= .37
{
if( d < 0.42 ) // Note: fixed from .43
{
if( d < 0.40 )
strcat(rval, "3/8"); // .375
else
strcat(rval, "2/5"); // .4
}
else // d >= .42
{
if( d < 0.44 )
strcat(rval, "3/7"); // .4285...
else
strcat(rval, "4/9"); // .4444...
}
}
}
}
else
{
if( d < 0.71 )
{
if( d < 0.60 )
{
if( d < 0.55 ) // Note: fixed from .56
{
strcat(rval, "1/2"); // .5
}
else // d >= .55
{
if( d < 0.57 )
strcat(rval, "5/9"); // .5555...
else
strcat(rval, "4/7"); // .5714
}
}
else // d >= .6
{
if( d < 0.62 ) // Note: Fixed from .63
{
strcat(rval, "3/5"); // .6
}
else // d >= .62
{
if( d < 0.66 )
strcat(rval, "5/8"); // .625
else
strcat(rval, "2/3"); // .6666...
}
}
}
else
{
if( d < 0.80 )
{
if( d < 0.74 )
{
strcat(rval, "5/7"); // .7142...
}
else // d >= .74
{
if(d < 0.77 ) // Note: fixed from .78
strcat(rval, "3/4"); // .75
else
strcat(rval, "7/9"); // .7777...
}
}
else // d >= .8
{
if( d < 0.85 ) // Note: fixed from .86
{
if( d < 0.83 )
strcat(rval, "4/5"); // .8
else
strcat(rval, "5/6"); // .8333...
}
else // d >= .85
{
if( d < 0.87 ) // Note: fixed from .88
{
strcat(rval, "6/7"); // .8571
}
else // d >= .87
{
if( d < 0.88 ) // Note: fixed from .89
{
strcat(rval, "7/8"); // .875
}
else // d >= .88
{
if( d < 0.90 )
strcat(rval, "8/9"); // .8888...
else
strcat(rval, "9/10"); // .9
}
}
}
}
}
}
return rval;
}
Вот ссылка, объясняющая математику, лежащую в основе преобразования десятичной дроби в дробную:
http://www.webmath.com/dec2fract.html
И вот пример функции, показывающей, как на самом деле это сделать с помощью VB (из www.freevbcode.com/ShowCode.asp?ID=582):
Public Function Dec2Frac(ByVal f As Double) As String
Dim df As Double
Dim lUpperPart As Long
Dim lLowerPart As Long
lUpperPart = 1
lLowerPart = 1
df = lUpperPart / lLowerPart
While (df <> f)
If (df < f) Then
lUpperPart = lUpperPart + 1
Else
lLowerPart = lLowerPart + 1
lUpperPart = f * lLowerPart
End If
df = lUpperPart / lLowerPart
Wend
Dec2Frac = CStr(lUpperPart) & "/" & CStr(lLowerPart)
End Function
(Из поисковых запросов Google:преобразовать десятичную дробь в дробный код, преобразовать десятичную дробь в код дроби)
Возможно, вы захотите почитать Что должен знать Каждый специалист по информатике об арифметике с плавающей запятой.
Вам придется указать некоторую точность путем умножения на большое число:
3.141592 * 1000000 = 3141592
затем вы можете сделать дробь:
3 + (141592 / 1000000)
и уменьшить с помощью GCD...
3 + (17699 / 125000)
но нет никакого способа получить предназначенный дробь вышла.Возможно, вы захотите всегда вместо этого используйте дроби по всему вашему коду - просто не забывайте по возможности уменьшать дроби, чтобы избежать переполнения!
Вот версии кода VB на Perl и Javascript, предложенные devinmoore:
Perl:
sub dec2frac {
my $d = shift;
my $df = 1;
my $top = 1;
my $bot = 1;
while ($df != $d) {
if ($df < $d) {
$top += 1;
}
else {
$bot += 1;
$top = int($d * $bot);
}
$df = $top / $bot;
}
return "$top/$bot";
}
И почти идентичный javascript:
function dec2frac(d) {
var df = 1;
var top = 1;
var bot = 1;
while (df != d) {
if (df < d) {
top += 1;
}
else {
bot += 1;
top = parseInt(d * bot);
}
df = top / bot;
}
return top + '/' + bot;
}
Реализация на C #
/// <summary>
/// Represents a rational number
/// </summary>
public struct Fraction
{
public int Numerator;
public int Denominator;
/// <summary>
/// Constructor
/// </summary>
public Fraction(int numerator, int denominator)
{
this.Numerator = numerator;
this.Denominator = denominator;
}
/// <summary>
/// Approximates a fraction from the provided double
/// </summary>
public static Fraction Parse(double d)
{
return ApproximateFraction(d);
}
/// <summary>
/// Returns this fraction expressed as a double, rounded to the specified number of decimal places.
/// Returns double.NaN if denominator is zero
/// </summary>
public double ToDouble(int decimalPlaces)
{
if (this.Denominator == 0)
return double.NaN;
return System.Math.Round(
Numerator / (double)Denominator,
decimalPlaces
);
}
/// <summary>
/// Approximates the provided value to a fraction.
/// http://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions
/// </summary>
private static Fraction ApproximateFraction(double value)
{
const double EPSILON = .000001d;
int n = 1; // numerator
int d = 1; // denominator
double fraction = n / d;
while (System.Math.Abs(fraction - value) > EPSILON)
{
if (fraction < value)
{
n++;
}
else
{
d++;
n = (int)System.Math.Round(value * d);
}
fraction = n / (double)d;
}
return new Fraction(n, d);
}
}
Тот Самый Корма-Парчовое дерево индуцирует довольно естественный способ аппроксимации действительных чисел дробями с простыми знаменателями.
Частично проблема заключается в том, что так много дробей на самом деле нелегко интерпретировать как дроби.Например.0,33 - это не 1/3, а 33/100.Но если вы помните свое обучение в начальной школе, то существует процесс преобразования десятичных значений в дроби, однако это вряд ли даст вам то, что вы хотите, поскольку большую часть времени десятичные числа хранятся не в 0.33, а в 0.32999999999999998 или что-то в этом роде.
Сделайте себе одолжение и не утруждайте себя этим, но если вам нужно, вы можете сделать следующее:
Умножайте исходное значение на 10, пока не уберете дробную часть.Сохраните это число и используйте его как делитель.Затем выполните ряд упрощений, отыскав общие знаменатели.
Таким образом, 0,4 будет равно 4/10.Затем вы бы искали общие делители, начинающиеся с низких значений, вероятно, простых чисел.Начиная с 2, вы увидите, равномерно ли делит 2 числитель и знаменатель, проверяя, совпадает ли этаж деления с самим делением.
floor(5/2) = 2
5/2 = 2.5
Таким образом, 5 не делит 2 поровну.Итак, затем вы проверяете следующее число, скажем, 3.Вы делаете это до тех пор, пока не достигнете квадратного корня из меньшего числа или выше него.
После того, как вы это сделаете, вам нужно
Это не "алгоритм", просто решение на Python:http://docs.python.org/library/fractions.html
>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)
"Допустим, у нас есть 0.33, нам нужно вывести "1/3"."
Какой точности вы ожидаете от "решения"?0,33 не равно 1/3.Как вы распознаете "хороший" (легко читаемый) ответ?
Несмотря ни на что, возможным алгоритмом может быть:
Если вы ожидаете найти ближайшую дробь в форме X / Y, где Y меньше 10, то вы можете перебрать все 9 возможных Y, для каждого Y вычислить X, а затем выбрать наиболее точную.
Встроенное решение в R:
library(MASS)
fractions(0.666666666)
## [1] 2/3
При этом используется метод непрерывной дроби и имеет необязательный cycles и max.denominator аргументы в пользу корректировки точности.
Вам нужно будет выяснить, с каким уровнем ошибки вы готовы согласиться.Не все десятичные дроби сведутся к простой дроби.Я бы, вероятно, выбрал легко делимое число, например 60, и выяснил, сколько 60-х ближе всего к значению, а затем упростил дробь.
Вы можете сделать это на любом языке программирования, выполнив следующие действия:
- Умножьте и разделите на 10 ^ x, где x - степень 10, необходимая для того, чтобы убедиться, что в числе не осталось знаков после запятой.Пример:Умножьте 0,33 на 10 ^ 2 = 100, чтобы получить 33, и разделите на то же самое, чтобы получить 33/100
- Уменьшайте числитель и знаменатель результирующей дроби путем факторизации до тех пор, пока вы больше не сможете получать целые числа из результата.
- Полученная уменьшенная фракция должна быть вашим ответом.
Пример:0,2 =0,2 х 10^1/10^1 =2/10 =1/5
Итак, это можно прочесть как "1 часть из 5".
Одно из решений состоит в том, чтобы просто сохранить все числа в виде рациональных чисел в первую очередь.Существуют библиотеки для арифметики рациональных чисел (например GMP).Если вы используете язык OO, вы можете просто использовать библиотеку классов rational number для замены вашего класса number.
Финансовые программы, среди прочего, использовали бы такое решение, чтобы иметь возможность производить точные вычисления и сохранять точность, которая может быть потеряна при использовании простого числа с плавающей точкой.
Конечно, это будет намного медленнее, так что для вас это может оказаться непрактичным.Зависит от того, сколько вычислений вам нужно выполнить и насколько важна для вас точность.
a = rational(1);
b = rational(3);
c = a / b;
print (c.asFraction) ---> "1/3"
print (c.asFloat) ----> "0.333333"
Я думаю, что лучший способ сделать это - сначала преобразовать ваше значение с плавающей точкой в представление ascii.В C ++ вы могли бы использовать ostringstream или в C, вы могли бы использовать sprintf .Вот как это выглядело бы в C ++:
ostringstream oss;
float num;
cin >> num;
oss << num;
string numStr = oss.str();
int i = numStr.length(), pow_ten = 0;
while (i > 0) {
if (numStr[i] == '.')
break;
pow_ten++;
i--;
}
for (int j = 1; j < pow_ten; j++) {
num *= 10.0;
}
cout << static_cast<int>(num) << "/" << pow(10, pow_ten - 1) << endl;
Аналогичный подход можно было бы использовать в прямой С.
После этого вам нужно будет проверить, что дробь находится в наименьшем выражении.Этот алгоритм даст точный ответ, т.е.0.33 выведет "33/100", а не "1/3". Однако 0.4 даст "4/10", что при сокращении до наименьших значений будет равно "2/5". Возможно, это не так эффективно, как решение Эппштейна, но я считаю, что это более просто.
У Ruby уже есть встроенное решение:
0.33.rationalize.to_s # => "33/100"
0.4.rationalize.to_s # => "2/5"
В Rails числовые атрибуты ActiveRecord также могут быть преобразованы:
product.size = 0.33
product.size.to_r.to_s # => "33/100"
Ответьте на C ++, предполагая, что у вас есть класс 'BigInt', который может хранить целые числа неограниченного размера.
Вместо этого вы можете использовать 'unsigned long long', но это будет работать только для определенных значений.
void GetRational(double val)
{
if (val == val+1) // Inf
throw "Infinite Value";
if (val != val) // NaN
throw "Undefined Value";
bool sign = false;
BigInt enumerator = 0;
BigInt denominator = 1;
if (val < 0)
{
val = -val;
sign = true;
}
while (val > 0)
{
unsigned int intVal = (unsigned int)val;
val -= intVal;
enumerator += intVal;
val *= 2;
enumerator *= 2;
denominator *= 2;
}
BigInt gcd = GCD(enumerator,denominator);
enumerator /= gcd;
denominator /= gcd;
Print(sign? "-":"+");
Print(enumerator);
Print("/");
Print(denominator);
// Or simply return {sign,enumerator,denominator} as you wish
}
Кстати, GetRational (0.0) вернет "+ 0/1", так что вы, возможно, захотите обработать этот случай отдельно.
P.S.:Я использую этот код в своем собственном классе 'RationalNum' в течение нескольких лет, и он был тщательно протестирован.
Этот алгоритм с помощью Иэн Ричардс / Джон Кеннеди он не только возвращает хорошие дроби, но и очень хорошо работает с точки зрения скорости.Это код на C #, взятый из этот ответ мной.
Он может справиться со всеми double значения, за исключением специальных значений, таких как NaN и + / - infinity, которые вам придется добавить при необходимости.
Он возвращает new Fraction(numerator, denominator).Замените на свой собственный тип.
Для получения дополнительных примеров значений и сравнения с другими алгоритмами, иди сюда
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);
}
Пример значений, возвращаемых этим алгоритмом:
Accuracy: 1.0E-3 | Richards
Input | Result Error
======================| =============================
3 | 3/1 0
0.999999 | 1/1 1.0E-6
1.000001 | 1/1 -1.0E-6
0.50 (1/2) | 1/2 0
0.33... (1/3) | 1/3 0
0.67... (2/3) | 2/3 0
0.25 (1/4) | 1/4 0
0.11... (1/9) | 1/9 0
0.09... (1/11) | 1/11 0
0.62... (307/499) | 8/13 2.5E-4
0.14... (33/229) | 16/111 2.7E-4
0.05... (33/683) | 10/207 -1.5E-4
0.18... (100/541) | 17/92 -3.3E-4
0.06... (33/541) | 5/82 -3.7E-4
0.1 | 1/10 0
0.2 | 1/5 0
0.3 | 3/10 0
0.4 | 2/5 0
0.5 | 1/2 0
0.6 | 3/5 0
0.7 | 7/10 0
0.8 | 4/5 0
0.9 | 9/10 0
0.01 | 1/100 0
0.001 | 1/1000 0
0.0001 | 1/10000 0
0.33333333333 | 1/3 1.0E-11
0.333 | 333/1000 0
0.7777 | 7/9 1.0E-4
0.11 | 10/91 -1.0E-3
0.1111 | 1/9 1.0E-4
3.14 | 22/7 9.1E-4
3.14... (pi) | 22/7 4.0E-4
2.72... (e) | 87/32 1.7E-4
0.7454545454545 | 38/51 -4.8E-4
0.01024801004 | 2/195 8.2E-4
0.99011 | 100/101 -1.1E-5
0.26... (5/19) | 5/19 0
0.61... (37/61) | 17/28 9.7E-4
|
Accuracy: 1.0E-4 | Richards
Input | Result Error
======================| =============================
0.62... (307/499) | 299/486 -6.7E-6
0.05... (33/683) | 23/476 6.4E-5
0.06... (33/541) | 33/541 0
1E-05 | 1/99999 1.0E-5
0.7777 | 1109/1426 -1.8E-7
3.14... (pi) | 333/106 -2.6E-5
2.72... (e) | 193/71 1.0E-5
0.61... (37/61) | 37/61 0
У вас возникнут две основные проблемы, которые усложнят это:
1) Плавающая точка не является точным представлением, что означает, что если у вас есть дробь "x / y", которая приводит к значению "z", ваш алгоритм дроби может вернуть результат, отличный от "x / y".
2) Иррациональных чисел на бесконечность больше, чем рациональных.Рациональное число - это такое число, которое может быть представлено в виде дроби.Иррациональные существа - это те, которые не могут.
Однако, дешевым способом, поскольку плавающая точка имеет предельную точность, вы всегда можете представить ее как некоторую форму фракции.(Я думаю...)
Дополнил приведенный выше код и преобразовал его в as3
public static function toFrac(f:Number) : String
{
if (f>1)
{
var parte1:int;
var parte2:Number;
var resultado:String;
var loc:int = String(f).indexOf(".");
parte2 = Number(String(f).slice(loc, String(f).length));
parte1 = int(String(f).slice(0,loc));
resultado = toFrac(parte2);
parte1 *= int(resultado.slice(resultado.indexOf("/") + 1, resultado.length)) + int(resultado.slice(0, resultado.indexOf("/")));
resultado = String(parte1) + resultado.slice(resultado.indexOf("/"), resultado.length)
return resultado;
}
if( f < 0.47 )
if( f < 0.25 )
if( f < 0.16 )
if( f < 0.13 )
if( f < 0.11 )
return "1/10";
else
return "1/9";
else
if( f < 0.14 )
return "1/8";
else
return "1/7";
else
if( f < 0.19 )
return "1/6";
else
if( f < 0.22 )
return "1/5";
else
return "2/9";
else
if( f < 0.38 )
if( f < 0.29 )
return "1/4";
else
if( f < 0.31 )
return "2/7";
else
return "1/3";
else
if( f < 0.43 )
if( f < 0.40 )
return "3/8";
else
return "2/5";
else
if( f < 0.44 )
return "3/7";
else
return "4/9";
else
if( f < 0.71 )
if( f < 0.60 )
if( f < 0.56 )
return "1/2";
else
if( f < 0.57 )
return "5/9";
else
return "4/7";
else
if( f < 0.63 )
return "3/5";
else
if( f < 0.66 )
return "5/8";
else
return "2/3";
else
if( f < 0.80 )
if( f < 0.74 )
return "5/7";
else
if(f < 0.78 )
return "3/4";
else
return "7/9";
else
if( f < 0.86 )
if( f < 0.83 )
return "4/5";
else
return "5/6";
else
if( f < 0.88 )
return "6/7";
else
if( f < 0.89 )
return "7/8";
else
if( f < 0.90 )
return "8/9";
else
return "9/10";
}
Допустим, у нас есть 0.33, нам нужно вывести "1/3".Если у нас есть "0.4", нам нужно вывести "2/5".
Это неправильно в обычном случае, потому что 1/3 = 0,3333333 = 0. (3) Более того, из предложенных выше решений невозможно выяснить, может ли десятичная дробь быть преобразована в дробь с определенной точностью, потому что выходные данные всегда являются дробью.
НО я предлагаю свою комплексную функцию со множеством опций, основанную на идее Бесконечный геометрический ряд, в частности , по формуле:
Сначала эта функция пытается найти период дроби в строковом представлении.После этого применяется описанная выше формула.
Код рациональных чисел заимствован из Стивен М.Маккейми реализация рациональных чисел в C#.Я надеюсь, что перенести мой код на другие языки не составит большого труда.
/// <summary>
/// Convert decimal to fraction
/// </summary>
/// <param name="value">decimal value to convert</param>
/// <param name="result">result fraction if conversation is succsess</param>
/// <param name="decimalPlaces">precision of considereation frac part of value</param>
/// <param name="trimZeroes">trim zeroes on the right part of the value or not</param>
/// <param name="minPeriodRepeat">minimum period repeating</param>
/// <param name="digitsForReal">precision for determination value to real if period has not been founded</param>
/// <returns></returns>
public static bool FromDecimal(decimal value, out Rational<T> result,
int decimalPlaces = 28, bool trimZeroes = false, decimal minPeriodRepeat = 2, int digitsForReal = 9)
{
var valueStr = value.ToString("0.0000000000000000000000000000", CultureInfo.InvariantCulture);
var strs = valueStr.Split('.');
long intPart = long.Parse(strs[0]);
string fracPartTrimEnd = strs[1].TrimEnd(new char[] { '0' });
string fracPart;
if (trimZeroes)
{
fracPart = fracPartTrimEnd;
decimalPlaces = Math.Min(decimalPlaces, fracPart.Length);
}
else
fracPart = strs[1];
result = new Rational<T>();
try
{
string periodPart;
bool periodFound = false;
int i;
for (i = 0; i < fracPart.Length; i++)
{
if (fracPart[i] == '0' && i != 0)
continue;
for (int j = i + 1; j < fracPart.Length; j++)
{
periodPart = fracPart.Substring(i, j - i);
periodFound = true;
decimal periodRepeat = 1;
decimal periodStep = 1.0m / periodPart.Length;
var upperBound = Math.Min(fracPart.Length, decimalPlaces);
int k;
for (k = i + periodPart.Length; k < upperBound; k += 1)
{
if (periodPart[(k - i) % periodPart.Length] != fracPart[k])
{
periodFound = false;
break;
}
periodRepeat += periodStep;
}
if (!periodFound && upperBound - k <= periodPart.Length && periodPart[(upperBound - i) % periodPart.Length] > '5')
{
var ind = (k - i) % periodPart.Length;
var regroupedPeriod = (periodPart.Substring(ind) + periodPart.Remove(ind)).Substring(0, upperBound - k);
ulong periodTailPlusOne = ulong.Parse(regroupedPeriod) + 1;
ulong fracTail = ulong.Parse(fracPart.Substring(k, regroupedPeriod.Length));
if (periodTailPlusOne == fracTail)
periodFound = true;
}
if (periodFound && periodRepeat >= minPeriodRepeat)
{
result = FromDecimal(strs[0], fracPart.Substring(0, i), periodPart);
break;
}
else
periodFound = false;
}
if (periodFound)
break;
}
if (!periodFound)
{
if (fracPartTrimEnd.Length >= digitsForReal)
return false;
else
{
result = new Rational<T>(long.Parse(strs[0]), 1, false);
if (fracPartTrimEnd.Length != 0)
result = new Rational<T>(ulong.Parse(fracPartTrimEnd), TenInPower(fracPartTrimEnd.Length));
return true;
}
}
return true;
}
catch
{
return false;
}
}
public static Rational<T> FromDecimal(string intPart, string fracPart, string periodPart)
{
Rational<T> firstFracPart;
if (fracPart != null && fracPart.Length != 0)
{
ulong denominator = TenInPower(fracPart.Length);
firstFracPart = new Rational<T>(ulong.Parse(fracPart), denominator);
}
else
firstFracPart = new Rational<T>(0, 1, false);
Rational<T> secondFracPart;
if (periodPart != null && periodPart.Length != 0)
secondFracPart =
new Rational<T>(ulong.Parse(periodPart), TenInPower(fracPart.Length)) *
new Rational<T>(1, Nines((ulong)periodPart.Length), false);
else
secondFracPart = new Rational<T>(0, 1, false);
var result = firstFracPart + secondFracPart;
if (intPart != null && intPart.Length != 0)
{
long intPartLong = long.Parse(intPart);
result = new Rational<T>(intPartLong, 1, false) + (intPartLong == 0 ? 1 : Math.Sign(intPartLong)) * result;
}
return result;
}
private static ulong TenInPower(int power)
{
ulong result = 1;
for (int l = 0; l < power; l++)
result *= 10;
return result;
}
private static decimal TenInNegPower(int power)
{
decimal result = 1;
for (int l = 0; l > power; l--)
result /= 10.0m;
return result;
}
private static ulong Nines(ulong power)
{
ulong result = 9;
if (power >= 0)
for (ulong l = 0; l < power - 1; l++)
result = result * 10 + 9;
return result;
}
Вот несколько примеров использования:
Rational<long>.FromDecimal(0.33333333m, out r, 8, false);
// then r == 1 / 3;
Rational<long>.FromDecimal(0.33333333m, out r, 9, false);
// then r == 33333333 / 100000000;
Ваш случай с обрезкой правой части нулевой частью:
Rational<long>.FromDecimal(0.33m, out r, 28, true);
// then r == 1 / 3;
Rational<long>.FromDecimal(0.33m, out r, 28, true);
// then r == 33 / 100;
Демонстрация минимального периода:
Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.5m));
// then r == 1234 / 9999;
Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.6m));
// then r == 123412 / 1000000; because of minimu repeating of period is 0.1234123 in this case.
Округление в конце:
Rational<long>.FromDecimal(0.8888888888888888888888888889m, out r));
// then r == 8 == 9;
Самый интересный случай:
Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 9);
// then r == 12345678 / 100000000;
Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 8);
// Conversation failed, because of period has not been founded and there are too many digits in fraction part of input value.
Rational<long>.FromDecimal(0.12121212121212121m, out r, 28, true, 2, 9));
// then r == 4 / 33; Despite of too many digits in input value, period has been founded. Thus it's possible to convert value to fraction.
Другие тесты и код каждый может найти в моя библиотека MathFunctions на github.
Вот быстрая и грязная реализация на javascript, которая использует подход грубой силы.Совсем не оптимизированный, он работает в пределах заранее определенного диапазона фракций: http://jsfiddle.net/PdL23/1/
/* This should convert any decimals to a simplified fraction within the range specified by the two for loops. Haven't done any thorough testing, but it seems to work fine.
I have set the bounds for numerator and denominator to 20, 20... but you can increase this if you want in the two for loops.
Disclaimer: Its not at all optimized. (Feel free to create an improved version.)
*/
decimalToSimplifiedFraction = function(n) {
for(num = 1; num < 20; num++) { // "num" is the potential numerator
for(den = 1; den < 20; den++) { // "den" is the potential denominator
var multiplyByInverse = (n * den ) / num;
var roundingError = Math.round(multiplyByInverse) - multiplyByInverse;
// Checking if we have found the inverse of the number,
if((Math.round(multiplyByInverse) == 1) && (Math.abs(roundingError) < 0.01)) {
return num + "/" + den;
}
}
}
};
//Put in your test number here.
var floatNumber = 2.56;
alert(floatNumber + " = " + decimalToSimplifiedFraction(floatNumber));
Это вдохновлено подходом, используемым JPS.
Как заявляли многие люди, вы действительно не можете преобразовать значение с плавающей запятой обратно в дробь (если только оно не является чрезвычайно точным, например .25).Конечно, вы могли бы создать какой-то тип поиска для большого массива дробей и использовать какую-то нечеткую логику для получения результата, который вы ищете.Опять же, это было бы не совсем точно, и вам нужно было бы определить нижние границы того, насколько большим вы хотите видеть знаменатель.
.32 < x < .34 = 1/3 или что-то в этом роде.
Вот реализация для ruby http://github.com/valodzka/frac
Math.frac(0.2, 100) # => (1/5)
Math.frac(0.33, 10) # => (1/3)
Math.frac(0.33, 100) # => (33/100)
Я наткнулся на особенно элегантное решение Haskell, использующее анаморфизм.Это зависит от схемы рекурсии посылка.
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE FlexibleContexts #-}
import Control.Applicative (liftA2)
import Control.Monad (ap)
import Data.Functor.Foldable
import Data.Ratio (Ratio, (%))
isInteger :: (RealFrac a) => a -> Bool
isInteger = ((==) <*>) (realToFrac . floor)
continuedFraction :: (RealFrac a) => a -> [Int]
continuedFraction = liftA2 (:) floor (ana coalgebra)
where coalgebra x
| isInteger x = Nil
| otherwise = Cons (floor alpha) alpha
where alpha = 1 / (x - realToFrac (floor x))
collapseFraction :: (Integral a) => [Int] -> Ratio a
collapseFraction [x] = fromIntegral x % 1
collapseFraction (x:xs) = (fromIntegral x % 1) + 1 / collapseFraction xs
-- | Use the nth convergent to approximate x
approximate :: (RealFrac a, Integral b) => a -> Int -> Ratio b
approximate x n = collapseFraction $ take n (continuedFraction x)
Если вы попробуете это в ghci, это действительно сработает!
λ:> approximate pi 2
22 % 7
