Dezimalzahl nach Bruch umwandeln

HarteWare

Hey zusammen,

ich habe einen Algo geschrieben, der eine beliebige rationale Zahl in einen Bruch umwandelt. Wenn ich mein eigenes Zeug richtig verstehe, sucht sie den Brocot-Stern-Baum ab, bis der passende Bruch gefunden wurde. Aber es wird halt immer nur dem Pfad gefolgt, der in Frage kommt. Sollte während der Suche feststehen, dass das Ergebnis nicht als Bruch darstellbar ist, weil Zähler oder Nenner einen int zum Overflow bringen würde, bricht der Algorithmus ab und sucht aus den zuvor gefundenen Ergebnissen das Beste heraus (ich glaube irgendwie es ist mathematisch gesehen immer das Ergebnis davor, bin mir aber nicht sicher).

Ich will mal wissen, was ihr davon haltet (Stil/Methode/Effizienz/Einfachheit/Korrektheit/Umsetzung/...); muss kein Essay sein.
Ich bin halt irgendwie süchtig nach Verbesserungsvorschlägen

Rational find_frac(double d)
{
    Rational a, b;
    if (d == 0) return Rational("0/1");
    if (d == 1) return Rational("1/1");
    if (d == -1) return Rational("-1/1");

    bool is_negative = d < 0;
    d = std::abs(d);
    if (d > maxint) throw std::runtime_error(
        "Number too big/small to be represented by Rational type.");

    if (d < 1) {
        a = Rational("0/1");
        b = Rational("1/1");
    } else {
        a = Rational("1/1");
        b = Rational("1/0");
    }

    Rational c = 0;
    bool overflowed = false;
    // Falls jemand meine Vermutung von oben bestätigen kann,
    // kann ich mir das sparen:
    std::vector<Rational> results;
    while (to_double(c) != d) {
        if (!add_is_safe(a, b)) {
            overflowed = true;
            break;
        }
        results.push_back(c);
        if (to_double(c) < d)
            a = c;
        else
            b = c;

        c = Rational( a.numerator() + b.numerator(),
                      a.denominator() + b.denominator() );
    }

    // find best approximation in case of overflow
    if (overflowed) {
        double smallest_diff = 0;
        for (const auto& i : results) {
            double diff = std::abs(d - to_double(i));
            if (diff < smallest_diff) {
                smallest_diff = diff;
                c = i;
            }
        }
    }
    if (is_negative) return -c;
    return c;
}

Wenn ich die Kettenbruchmethode mal zum Laufen gebracht hab, post ich die vielleicht auch noch, halt so zum Vergleich.

Wenn keiner antwortet gehe ich davon aus, dass es schon ok ist so

LG

volkard

Findet er denn 1/4, 1/7 und 11/12?

HarteWare

@volkard: hhmm, interessant. Also 1/4 funst (klar, sind ja exakt 0.25).
Für 1/7 bekomme ich Müll

(6391321/44739245)

für 11/12 auch:

(7689563/8388614)

Diese verflixten doubles. Kann man das irgendwie anders machen? Ich nehm mal stark an, dass dies aufgrund von allzeit-bekannten Rundungsfehlern passiert.

Habs allerdings so gemacht:

std::cout << "1/4: " << find_frac(1.f/4) << '\n';
std::cout << "1/7: " << find_frac(1.f/7) << '\n';
std::cout << "11/12: " << find_frac(11.f/12) << '\n';

So siehts ganz anders aus (Ergebnisse schnell mit python berechnet)

std::cout << "1/4: " << find_frac(0.25) << '\n';
std::cout << "1/7: " << find_frac(0.14285714285714285) << '\n';
std::cout << "11/12: " << find_frac(0.9166666666666666) << '\n';

1/4: (1/4)
1/7: (1/7)
11/12: (11/12)

HarteWare schrieb:

std::cout << "1/4: " << find_frac(1.f/4) << '\n';
std::cout << "1/7: " << find_frac(1.f/7) << '\n';
std::cout << "11/12: " << find_frac(11.f/12) << '\n';

Warum floats? Lass das f weg, dann ist die Eingabe exakter.

volkard

Die doubles sind ja immer z/n mit z ist eine Zweierpotenz. Das wäre genau und sonst nix.
1.0/7 hat als Nenner eine Zweierpotenz. brocot-stern hilt da gar nix. Der hilft, um 1/7 zielstrebig zu finden. Ab wann Du 1/7 glauben magst, musst Du selber schätzen. Ein bekannter Taschenrechner rechnet intern elfstellig und zeigt Zahlen nur als glatten Bruch an, wenn der Nenner kleiner als 1000 ist.

Schätze, man muss sich beschränken auf solche Tricks, wenn man 1/7 angezeigt bekommen will. Vielleicht den Benutzer die Stellenzahl angeben lassen, wie ungenau ers erlauben mag.
find_frac(1./7,10)

Werner Salomon

Hey HarteWare,

HarteWare schrieb:

Ich will mal wissen, was ihr davon haltet (Stil/Methode/Effizienz/Einfachheit/Korrektheit/Umsetzung/...); muss kein Essay sein.

Du hast einen ganz wichtigen Punkt vergessen - volkard hat schon darauf hingewiesen - es macht nur Sinn eine rationale Zahl zu finden, die bei vergleichbar 'kleinem' Nenner möglichst dicht an 'd' liegt.

Das Thema Gleitkomma nach Bruch hatten wir vor gut 7 Jahren schon mal. Das Verfahren, welches Du verwendest, kenne ich unter Farey-Folge.

Zum Stil/Methode:
- den Konstruktor mit String finde ich etwas fehl plaziert.
- Weiter finde ich den Namen der Funktion 'add_is_safe' irreführend. Ich unterstelle, dass Du genau nicht prüfst, ob a und b ohne Integer-Overflow addiert werden können, sondern Du prüfst, ob die Zähler und Nenner addiert werden können; das ist etwas anderes.
- Ich halte es für geschickter 'd' gleich am Anfang auf <0 zu prüfen. Und dann einfach mit

if( d < 0 ) 
        return -find_frac(-d);

dann sparst Du Dir alle weiteren Abfragen später.
- Die Abfrage d<1 ist überflüssig, wenn Du die Grenzen am Anfang auf 0/1 und 1/0 setzt. Dann ist das erste Medium sowieso 1/1.
- genauso überflüssig ist das Speichern der Zwischenergebnisse. Die beste Näherung ist das letzte Ergebnis.

Gruß
Werner

HarteWare

@fffffffffffff:
ohja, stimmt. Genau dieser Gedanke kam mir, als ich vom PC weg bin "Moment mal, .f sind ja floats". So

std::cout << "1/4: " << find_frac(1./4) << '\n';
std::cout << "1/7: " << find_frac(1./7) << '\n';
std::cout << "11/12: " << find_frac(11./12) << '\n';

bekomme ich wie erwartet:

1/4: (1/4)
1/7: (1/7)
11/12: (11/12)

@volkard:
Das ist jetzt interessant.
1. Auf der website, die sehr detailliert die Kettenbruchentwicklung beschreibt, hat der Rechner Dezimalzahl=>Bruch ein Feld, wo man bestimmen kann, wie groß maximal der Nenner sein darf. Es zeigt auch immer die Abweichung an.
Schon seit ich versuche das umzusetzten, hatte ich auch immer diesen Gedanken mit einer "Toleranz" oder "precision", um welche der ausgegebene Bruch von der Eingabe variieren darf.

@Werner
Auf den ersten Blick sah es aus, als würde der Link von dir Kettenbruchentwicklung nutzen. Werde mir das auf jeden Fall anschauen.
Danke für den Hinweis, safe_add() macht was es soll, aber ich verwende es falsch, das hab ich glatt verpennt, danke.
Ich werde mich auch um die anderen genannten Dinge kümmern.

edit: Hab einigen Quatsch entfernt... Auf jeden Fall, ich mach mich an die Arbeit, eure Hilfe soll nicht umsonst gewesen sein.

- - - - Update - - - -
v2.0:

Rational frac(double, double tolerance=1.E-4);

Rational frac(double d, double tol)
{
    if (d < 0) return -frac(-d, tol);

    if (d > maxint) throw std::runtime_error(
                    "Number too big/small to be represented by Rational type.");

    Rational left(0, 1);
    Rational right(1, 0);
    Rational mid(0, 1);

    while (std::abs(d - mid.to_double()) > tol) {
        if ( !add_is_safe(left.num, right.num) ||
             !add_is_safe(left.denom, right.denom) ) throw std::runtime_error(
                "Tolerance too small for converting " +
                 std::to_string(d) + " to Rational.");

        if (mid.to_double() < d) left = mid;
        else right = mid;
        mid = Rational(left.num + right.num, left.denom + right.denom);
    }
    return mid;
}

Wars ca. so gemeint?
edit: was hier stand war off-topic.

Ist die Kettenbruchmethode tatsänlich merklich besser/schneller, oder kann ichs dabei lassen? Ich verstehe nämlich die Methode oben irgendwie mehr.