[algorithm] 浮動小数点を人間が読める分数に変換するには?


Answers

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)
Question

0.33の場合、 "1/3"を出力する必要があります。
「0.4」がある場合、「2/5」を出力する必要があります。

アイデアは、データを理解するためのよりよい方法として、ユーザーに「yのうちのx個の部分」を理解させるために人間が読めるようにすることです。

パーセンテージは良い代用品だと私は知っていますが、これを行う簡単な方法があるかどうか疑問に思っていましたか?




私はアナモフィックを利用して、特にエレガントなHaskellソリューションを見つけました。 これはrecursion-schemesパッケージに依存します。

{-# 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



小数点以下を小数点に変換する数学を説明するリンクは次のとおりです。

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検索から:小数から小数への変換、小数から小数への変換)




Stern-Brocot Treeは、実数を単純分母で分数で近似するかなり自然な方法を誘導します。




あなたはこれを難しくする2つの基本的な問題を持つつもりです:

1)浮動小数点は正確な表現ではありません。つまり、 "x / y"の値が "z"になる場合、小数点アルゴリズムは "x / y"以外の結果を返す可能性があります。

2)有理数より無理数が多い。 有理数は、分数として表現できるものです。 不合理なことはできないものです。

しかし、安価な方法では、浮動小数点は限界精度を持っているので、あなたはいつでもそれをある種の派閥として表すことができます。 (おもう...)




次の手順を使用して、任意のプログラミング言語でこれを行うことができます。

  1. 乗算と10 ^ xで除算します。ここで、xは小数点以下の桁数がないことを確認するために必要な10の累乗です。 例:0.33を10 ^ 2 = 100で掛けて33にし、それを33/100にする
  2. 結果から整数を得ることができなくなるまで、分子と分数の分母を分数分解します。
  3. 減った分数があなたの答えになるはずです。

例:0.2 = 0.2×10 ^ 1/10 ^ 1 = 2/10 = 1/5

それで、それは「5のうち1つの部分」と読むことができます




Rのビルトインソリューション:

library(MASS)
fractions(0.666666666)
## [1] 2/3

これは、連続分数法を使用し、精度を調整するためのオプションのcyclesmax.denominator引数を持ちます。




答えは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
}

BTW、GetRational(0.0)は "+0 / 1"を返しますので、このケースを個別に処理したいかもしれません。

PS:私はこのコードを自分の 'RationalNum'クラスで数年間使用してきましたが、それは完全にテストされています。




私はこれを行う最善の方法は、最初にあなたの浮動小数点値を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;

同じようなアプローチがまっすぐなC.

その後、分数が最低の条件であることを確認する必要があります。 このアルゴリズムは正確な答えを与えます。すなわち、0.33は "1/3"ではなく "33/100"を出力します。 しかし、0.4を指定すると "4/10"となり、最も低い条件になると "2/5"になります。 これはEppSteinのソリューションほど強力ではないかもしれませんが、これはより簡単だと思います。




これは単に「アルゴリズム」ではなく、Pythonのソリューションです: fractions : fractions

>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)



AC#の実装

/// <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://.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"を出力する必要があります。 「0.4」がある場合、「2/5」を出力する必要があります。

1/3 = 0.3333333 = 0のため、一般的に間違っています。さらに、出力が常に小数であるため、小数点は定義された精度で小数に変換できます。

しかし、私は無限の幾何学的なシリーズのアイデアに基づいて、数式に具体的には、多くのオプションで私の包括的な機能をお勧めします:

最初に、この関数は文字列表現の小数点の期間を見つけようとしています。 その後、上記の式が適用される。

Rationalナンバーコードは、C#のStephen M. McKamey有理数実装から借りています。 自分のコードを他の言語に移植することが非常に難しくないことを願っています。

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

最小期間demostration:

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.

他のテストとコードは、githubのMathFunctionsライブラリで見つけることができます。




多くの人が言っているように、本当に浮動小数点数を分数に戻すことはできません。 もちろん、大規模な配列を探すために何らかのタイプのルックアップを作成し、探している結果を生成するために何らかのファジーロジックを使用することもできます。 繰り返しますが、これは正確ではありません。分母がどれくらいの大きさであるかを定義する必要があります。

.32 <x <.34 = 1/3またはそのようなもの。




Links