Wie konvertiere ich Floats in lesbare Brüche?

Nehmen wir an, wir haben 0.33 , wir müssen ausgeben 1/3.
Wenn ja, müssen 0.4wir ausgeben 2/5.

Die Idee ist, es für den Menschen lesbar zu machen, damit der Benutzer " x Teile aus y " versteht, um Daten besser zu verstehen.

Ich weiß, dass Prozentsätze ein guter Ersatz sind, aber ich habe mich gefragt, ob es einen einfachen Weg gibt, dies zu tun.

Ich habe festgestellt, dass David Eppsteins rationale Annäherung an einen gegebenen Code der reellen Zahl C genau das ist, wonach Sie fragen. Es basiert auf der Theorie der fortgesetzten Brüche und ist sehr schnell und ziemlich kompakt.

Ich habe Versionen davon verwendet, die für bestimmte Zähler- und Nennergrenzen angepasst wurden.

/*
** 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]));
}

Ab Python 2.6 gibt es die fractions Modul.

(Zitiert aus den Dokumenten.)

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

Wenn die Ausgabe einem menschlichen Leser einen schnellen Eindruck von der Reihenfolge des Ergebnisses vermitteln soll, ist es nicht sinnvoll, so etwas wie "113/211" zurückzugeben. Daher sollte sich die Ausgabe auf die Verwendung einstelliger Zahlen (und möglicherweise 1 /) beschränken. 10 und 9/10). Wenn ja, können Sie beobachten, dass es nur 27 verschiedene gibt Fraktionen gibt.

Da sich die zugrunde liegende Mathematik zum Generieren der Ausgabe niemals ändern wird, könnte eine Lösung darin bestehen, einen binären Suchbaum einfach hart zu codieren, so dass die Funktion höchstens log (27) ~ = 4 3/4 Vergleiche ausführt. Hier ist eine getestete C-Version des Codes

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

Hier ist ein Link, der die Mathematik erklärt, die hinter der Konvertierung einer Dezimalstelle in einen Bruch steht:

http://www.webmath.com/dec2fract.html

Und hier ist eine Beispielfunktion, wie man es tatsächlich mit VB macht (von 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

(Bei Google-Suchanfragen: Dezimal in Bruch umwandeln, Dezimal in Bruch umwandeln)

Vielleicht möchten Sie lesen, was jeder Informatiker über Gleitkomma-Arithmetik wissen sollte .

Sie müssen eine gewisse Genauigkeit angeben, indem Sie mit einer großen Zahl multiplizieren:

3.141592 * 1000000 = 3141592

dann können Sie einen Bruch machen:

3 + (141592 / 1000000)

und über GCD reduzieren ...

3 + (17699 / 125000)

Es gibt jedoch keine Möglichkeit, die beabsichtigte Fraktion herauszuholen. Möglicherweise möchten Sie stattdessen immer Brüche in Ihrem Code verwenden - denken Sie daran, Brüche zu reduzieren, wenn Sie können, um einen Überlauf zu vermeiden!

Hier sind Perl- und Javascript-Versionen des von devinmoore vorgeschlagenen VB-Codes:

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

Und das fast identische 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;
}

AC # Implementierung

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

Das Stern-Brocot-Baum induziert eine ziemlich natürliche Methode, um reelle Zahlen durch Brüche mit einfachen Nennern zu approximieren.

Ein Teil des Problems ist, dass so viele Brüche nicht einfach als Brüche zu interpretieren sind. ZB ist 0,33 nicht 1/3, sondern 33/100. Wenn Sie sich jedoch an Ihre Grundschulausbildung erinnern, werden Dezimalwerte in Brüche umgewandelt. Es ist jedoch unwahrscheinlich, dass Sie das erhalten, was Sie möchten, da Dezimalzahlen meistens nicht bei 0,33, sondern bei 0,329999999999998 oder einem ähnlichen Wert gespeichert werden.

Tun Sie sich selbst einen Gefallen und kümmern Sie sich nicht darum, aber wenn Sie müssen, können Sie Folgendes tun:

Multiplizieren Sie den ursprünglichen Wert mit 10, bis Sie den Bruchteil entfernen. Behalten Sie diese Nummer und verwenden Sie sie als Teiler. Führen Sie dann eine Reihe von Vereinfachungen durch, indem Sie nach gemeinsamen Nennern suchen.

0,4 wäre also 4/10. Sie würden dann nach gemeinsamen Teilern suchen, die mit niedrigen Werten beginnen, wahrscheinlich Primzahlen. Beginnend mit 2 würden Sie sehen, ob 2 sowohl den Zähler als auch den Nenner gleichmäßig teilt, indem Sie prüfen, ob der Teilungsboden mit der Teilung selbst identisch ist.

floor(5/2) = 2
5/2 = 2.5

5 teilt also 2 nicht gleichmäßig. Dann überprüfen Sie die nächste Zahl, sagen wir 3. Sie tun dies, bis Sie an oder über der Quadratwurzel der kleineren Zahl treffen.

Nachdem Sie das getan haben, brauchen Sie

Dies ist kein "Algorithmus", sondern nur eine Python-Lösung: http://docs.python.org/library/fractions.html

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

"Nehmen wir an, wir haben 0,33, wir müssen" 1/3 "ausgeben."

Welche Präzision erwarten Sie von der "Lösung"? 0,33 ist nicht gleich 1/3. Woran erkennt man eine "gute" (leicht zu lesende) Antwort?

Egal was, ein möglicher Algorithmus könnte sein:

Wenn Sie erwarten, einen nächsten Bruch in einer Form X / Y zu finden, in der Y kleiner als 10 ist, können Sie für jede Y-Berechnung X alle 9 möglichen Ys durchlaufen und dann den genauesten auswählen.

Ich denke, der beste Weg, dies zu tun, besteht darin, zuerst Ihren Float-Wert in eine ASCII-Darstellung umzuwandeln. In C ++ können Sie ostringstream oder in C sprintf verwenden. So würde es in C ++ aussehen:

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;

Ein ähnlicher Ansatz könnte in Straight C gewählt werden.

Danach müssten Sie überprüfen, ob der Bruch am niedrigsten ist. Dieser Algorithmus gibt eine genaue Antwort, dh 0,33 würde "33/100" ausgeben, nicht "1/3". 0,4 würde jedoch "4/10" ergeben, was, wenn es auf die niedrigsten Terme reduziert würde, "2/5" wäre. Dies ist möglicherweise nicht so leistungsfähig wie die Lösung von EppStein, aber ich glaube, dass dies einfacher ist.

Eine integrierte Lösung in R:

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

Dies verwendet eine fortgesetzte Bruchmethode und verfügt über Optionen cyclesund max.denominatorArgumente zum Anpassen der Genauigkeit.

Sie müssen herausfinden, welche Fehlerstufe Sie akzeptieren möchten. Nicht alle Dezimalbrüche werden auf einen einfachen Bruch reduziert. Ich würde wahrscheinlich eine leicht teilbare Zahl wie 60 auswählen und herausfinden, wie viele 60stel dem Wert am nächsten kommen, und dann den Bruch vereinfachen.

Sie können dies in jeder Programmiersprache mit den folgenden Schritten tun:

1. Multiplizieren und dividieren Sie mit 10 ^ x, wobei x die Potenz von 10 ist, die erforderlich ist, um sicherzustellen, dass für die Zahl keine Dezimalstellen mehr vorhanden sind. Beispiel: Multiplizieren Sie 0,33 mit 10 ^ 2 = 100, um 33 zu erhalten, und dividieren Sie es durch dasselbe, um 33/100 zu erhalten
2. Reduzieren Sie den Zähler und den Nenner des resultierenden Bruchs durch Faktorisierung, bis Sie keine Ganzzahlen mehr aus dem Ergebnis erhalten.
3. Der resultierende reduzierte Anteil sollte Ihre Antwort sein.

Beispiel: 0,2 = 0,2 x 10 ^ 1/10 ^ 1 = 2/10 = 1/5

Das kann also als "1 Teil von 5" gelesen werden.

Eine Lösung besteht darin, zunächst alle Zahlen als rationale Zahlen zu speichern. Es gibt Bibliotheken für rationale Zahlenarithmetik (zB GMP ). Wenn Sie eine OO-Sprache verwenden, können Sie möglicherweise nur eine rationale Nummernklassenbibliothek verwenden, um Ihre Nummernklasse zu ersetzen.

Finanzprogramme würden unter anderem eine solche Lösung verwenden, um genaue Berechnungen durchführen und die Präzision bewahren zu können, die mit einem einfachen Float verloren gehen könnte.

Natürlich wird es viel langsamer sein, so dass es für Sie möglicherweise nicht praktisch ist. Hängt davon ab, wie viele Berechnungen Sie durchführen müssen und wie wichtig die Präzision für Sie ist.

a = rational(1);
b = rational(3);
c = a / b;

print (c.asFraction)  --->  "1/3"
print (c.asFloat) ----> "0.333333"

Nehmen wir an, wir haben 0,33, wir müssen "1/3" ausgeben. Wenn wir "0.4" haben, müssen wir "2/5" ausgeben.

Im Normalfall ist dies falsch, da 1/3 = 0,3333333 = 0. (3) Darüber hinaus ist es unmöglich, aus den oben vorgeschlagenen Lösungen herauszufinden, dass die Dezimalzahl mit definierter Genauigkeit in einen Bruch umgewandelt werden kann, da die Ausgabe immer ein Bruch ist.

ABER ich schlage meine umfassende Funktion mit vielen Optionen vor, die auf der Idee einer unendlichen geometrischen Reihe basieren , insbesondere auf der Formel:

Diese Funktion versucht zunächst, die Bruchperiode in der Zeichenfolgendarstellung zu finden. Danach wird die oben beschriebene Formel angewendet.

Der Code für rationale Zahlen stammt aus der Implementierung rationaler Zahlen von Stephen M. McKamey in C #. Ich hoffe, es ist nicht sehr schwer, meinen Code auf andere Sprachen zu portieren.

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

Es gibt einige Beispiele für Verwendungen:

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;

Ihr Fall mit dem Trimmen des rechten Teils des Nullteils:

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;

Min. 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.

Rundung am Ende:

Rational<long>.FromDecimal(0.8888888888888888888888888889m, out r));
// then r == 8 == 9;

Der interessanteste Fall:

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.

Weitere Tests und Codes finden alle in meiner MathFunctions-Bibliothek auf github .

Ruby hat bereits eine integrierte Lösung:

0.33.rationalize.to_s # => "33/100"
0.4.rationalize.to_s # => "2/5"

In Rails können auch numerische ActiveRecord-Attribute konvertiert werden:

product.size = 0.33
product.size.to_r.to_s # => "33/100"

Antworten Sie in C ++ unter der Annahme, dass Sie eine 'BigInt'-Klasse haben, in der Ganzzahlen mit unbegrenzter Größe gespeichert werden können.

Sie können stattdessen 'unsigned long long' verwenden, dies funktioniert jedoch nur für bestimmte Werte.

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
}

Übrigens gibt GetRational (0.0) "+0/1" zurück, daher möchten Sie diesen Fall möglicherweise separat behandeln.

PS: Ich verwende diesen Code seit mehreren Jahren in meiner eigenen 'RationalNum'-Klasse und er wurde gründlich getestet.

Dieser Algorithmus von Ian Richards / John Kennedy liefert nicht nur schöne Brüche, sondern ist auch sehr schnell. Dies ist der C # -Code, den ich aus dieser Antwort entnommen habe.

Es kann alle doubleWerte verarbeiten, mit Ausnahme von Sonderwerten wie NaN und +/- unendlich, die Sie bei Bedarf hinzufügen müssen.

Es gibt a zurück new Fraction(numerator, denominator). Ersetzen Sie durch Ihren eigenen Typ.

Weitere Beispielwerte und einen Vergleich mit anderen Algorithmen finden Sie hier

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

Von diesem Algorithmus zurückgegebene Beispielwerte:

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         

Sie werden zwei grundlegende Probleme haben, die dies schwierig machen:

1) Gleitkomma ist keine exakte Darstellung. Wenn Sie also einen Bruchteil von "x / y" haben, der zu einem Wert von "z" führt, gibt Ihr Bruchalgorithmus möglicherweise ein anderes Ergebnis als "x / y" zurück.

2) Es gibt unendlich viel mehr irrationale Zahlen als rationale. Eine rationale Zahl kann als Bruch dargestellt werden. Irrationales Sein, das nicht kann.

Da Gleitkommazahlen jedoch eine begrenzte Genauigkeit haben, können Sie sie auf eine billige Art und Weise immer als eine Form von Fraktion darstellen. (Meiner Ansicht nach...)

Vervollständigte den obigen Code und konvertierte ihn in 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";
    }

Hier ist eine schnelle und schmutzige Implementierung in Javascript, die einen Brute-Force-Ansatz verwendet. Überhaupt nicht optimiert, funktioniert es innerhalb eines vordefinierten Bereichs von Brüchen: 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));

Dies ist inspiriert von dem Ansatz von JPS.

Wie viele Leute angegeben haben, kann man einen Gleitkommawert wirklich nicht zurück in einen Bruch umwandeln (es sei denn, er ist extrem genau wie 0,25). Natürlich können Sie eine Art Suche nach einer großen Anzahl von Brüchen erstellen und eine Art Fuzzy-Logik verwenden, um das gewünschte Ergebnis zu erzielen. Auch dies wäre jedoch nicht genau und Sie müssten eine Untergrenze dafür definieren, wie groß der Nenner sein soll.

.32 <x <.34 = 1/3 oder so ähnlich.

Hier ist die Implementierung für 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)

Ich stieß auf eine besonders elegante Haskell-Lösung, die einen Anamorphismus nutzte. Dies hängt vom Rekursionsschema- Paket ab.

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

Wenn Sie dies in ghci ausprobieren, funktioniert es wirklich!

λ:> approximate pi 2
22 % 7