double Wert in Bruch umwandeln

FireFlow

Ich hab mal das relevante herausgesucht: Man kann das aber sicher noch weit optimieren:

struct rational
{
    int zaehler;
    int nenner;
};

int ggt(int m, int n)
{
    int r;
    do
    {
        if(m<n)
        {
            int t=m;
            m=n;
            n=t;
        }
        r=m-n;
        m=n;
        n=r;
    } while(r>0);
    return m;
}

rational double2rational(double v)
{
    rational erg;
    erg.nenner = 1;

    while(int(v)!=v)
    {
        v*=10;
        erg.nenner *= 10;
    }
    erg.zaehler = v;

    int teiler = ggt(erg.zaehler, erg.nenner);

    erg.zaehler /= teiler;
    erg.nenner /= teiler;

    return erg;
}

@fireflow
Ich möchte etwas ganz ähnliches machen, nämlich eine class Bruch, die als private die 2 int Werte hat und einen Konstruktor Bruch(double).
Ich weiß immer noch nicht wie ich den Konstruktor machen soll

PAD

Hier taucht wirklich die Frage auf ob das noch ins C-Forum passt oder bei der Art der Implementierung nicht besser nach C++ verschoben werden sollte.

volkard

ich habe da vielleicht ein besseres verfahren. das gibt auch gute näherungen für doubles wie pi (22/7 und 355/113).

ich gehe mal davon aus, daß x zwischen 0 und 1 liegt.
ich nehme als beispiel mal 0.75

dann schreibe ich
0/1 < 0.75 < 1/1
dann berechne ich die zahl zwischen den grenzen mit zähler+zähler und nenner+nenner. also 1/2 und schau, ob 0.75 kleiner oder gößer als 1/2 ist. je nachdem ersetze ich die untere oder die obere grenze.
1/2 < 0.75 < 1/1
2/3 < 0.75 < 1/1
3/4 == 0.75 < 1/1
ups, ist gleich. gut.

das verfahren ist ausreichend schnell, es ist furchtbar fein, wenn es drum geht, irrationale zahlen anzunähern. es ist einfach zu coden. und ich hab's erfunden (und wie immer später festgestellt, daß ein anderer früher war.)

Herr-Vorragend

und was ist, wenn x z.B. 0.2 ist?

volkard

Herr-Vorragend schrieb:

und was ist, wenn x z.B. 0.2 ist?

0/1 < 0.2 < 1/1
neue mitte: 1/2
0/1 < 0.2 < 1/2
neue mitte: 1/3
0/1 < 0.2 < 1/3
neue mitte: 1/4
0/1 < 0.2 < 1/4
neue mitte: 1/5
treffer.

das verfahren besucht unter anderem alle näherungen, die auch die kettenbruchemtwicklung besucht.

Konfusius

und was ist, wenn du 1.0e+30 in einen bruch verwandeln willst. dein vorhaben ist leider nicht für jeden double-wert durchführbar. die routine müsste einen fehler (ERANGE oder so) melden, wenn der double-wert nicht als quotient zweier ints dargestellt werden kann.

volkard

Konfusius schrieb:

und was ist, wenn du 1.0e+30 in einen bruch verwandeln willst. dein vorhaben ist leider nicht für jeden double-wert durchführbar. die routine müsste einen fehler (ERANGE oder so) melden, wenn der double-wert nicht als quotient zweier ints dargestellt werden kann.

er ist eh fast nie als quotient zweier ints darstellbar.
1/7 kriegste nicht glatt in nen double rein. man müßte bemerken, daß beim erreichen von 1/7 die genauigkeit auf einmal um viele größenordnungen zunimmt.

aber hast schon recht, daß das verfahren auch ne dummheit hat, es ist für sachen wie 1/1000000 saulahm, weil's ne million schritte braucht. hoffen wir mal, daß sowas relativ selten vorkommt.

Windalf

zum anderen ist ggT ausrechnen schon überall im Netz fertig implementiert zu finden so das man sich hier keinen Kopf mehr machen brauch...

volkard

Windalf schrieb:

zum anderen ist ggT ausrechnen schon überall im Netz fertig implementiert zu finden so das man sich hier keinen Kopf mehr machen brauch...

ich behaupte aber, daß ggt-ausrechnen sehr oft schlechte lösungen liefert.