Gleitkommazahl in Bruch umwandeln

Hallo zusammen !
ich suche einen Algorithmus, mit dem ich eine Gleitkommazahl, also beispielsweise:

double value = 4.34166;

in einen Bruch umwandeln kann. Habt ihr dazu ne Idee (Hab schon gegoogelt, aber nix brauchbares gefunden)?

Schonmal vielen Dank!

Viele liebe Grüße
Tim

*D*

Es gibt keine vordefinierte Klasse die Brüche anzeigt. Damit müsstst du
sie selber schreiben. Das gibt es in jedem c++-Buch als Übung. In die Klasse
müsstest du dann einen Umwandlungskonstruktor einbauen. Und dann die Zahl
einfach kürzen!

Uchuujinsan

Speicher die nachkommastellen als int, und dazu halt einen ungekürzten int mit anzahl von nullen in höhe der länge der nachkommastellen, in der Form 100... etc
Hast dann zum Beispiel
34166
und
100000

Dann prüfst du oben die teilbarkeit durch 2 und 5 solange, bis du einen vollständig gekürzten Bruch hast:

int zaehler=34166;
int nenner=100000

while (!(zaehler%2) && !(nenner%2))
{
  zaehler/=2;
  nenner/=2;
}

while (!(zaehler%5) && !(nenner%5))
{
  zaehler/=5;
  nenner/=5;
}

*D*

int ggT (int a, int b) {
	int rest;
	do {
		rest = b % a;
		b = a;
		a = rest;
	} while (rest != 0);
	return b;
}

// und dann kuerzen...
int tmp_ggt = ggt(zaehler,nenner);
int tmp_nenner = nenner/tmp_ggt;
int tmp_zaehler = zaehler/tmp_ggt;

Michael E.

Uchuujinsan schrieb:

Dann prüfst du oben die teilbarkeit durch 2 und 5 solange, bis du einen vollständig gekürzten Bruch hast

Ach, kann man 3/9 nicht mehr kürzen?

Uchuujinsan

@Michael
Wär nett wenn du mir auch noch erklären könntest wie man mit dieser bruchumwandlung jemals auf 3/9 kommen soll.
Primfaktorzerlegung eines nenners nach obigen schema is halt nunmal nur
(2 x 5) x (2 x 5) x ... x (2 x 5)
Und da wirst du nie, egal wann wie wo weshalb und warum, durch 3 teilen können.
Deswegen reicht ne Prüfung nach 2 und 5 völlig.

Michael E.

Wenn du dir die Aufgabenstellung noch einmal durchliest, wirst du feststellen, dass der OP einen Algorithmus sucht, um eine "Gleitkommazahl" in einen Bruch umzuwandeln und nicht wissen will, wie die Zahl 4,34166 als Bruch aussieht.

Edit: Übrigens ist der ggT von 34166 und 100000 die Zahl 2, also könntest du dir auch noch den Test sparen, ob beide Zahlen durch 5 teilbar sind

Uchuujinsan

Lies mal meinen Beitrag, vorallem den Anfang. Vielleicht hilft dir das weiter, das ich die Zahl verwendet hab is nur ein Beispiel.
Wenn man nen Dezimalbruch in nen normalen Bruch umwandelt braucht man nie ne division durch 3..

Kannst mir erklären, mal schön von Anfang an, wie man bei der Umwandlung einer Gleitkomazahl in einen normalen Bruch jemals auf 3/9 kommen soll?
Vielleicht versteh ichs ja dann auch. Am besten mit Beispiel...

Also danke erstmal an alle, für eure Antworten!
Also das es keine Klasse dafür gibt, weiß ich - deshalb will ich mir ja eine schreiben. Einen Algorithmus zum Kürzen hab ich bereits, der -mal grob üverflogen- dem von 'D' entspricht (und auch funktioniert).

Also aus 'Uchuujinsan's Post werd ich nicht ganz schlau, verstehe nicht ganz was du mit:

Speicher die nachkommastellen als int, und dazu halt einen ungekürzten int mit anzahl von nullen in höhe der länge der nachkommastellen, in der Form 100... etc
Hast dann zum Beispiel
34166
und
100000

meinst .

Habe jetzt eine Idee gehabt (die dem vllt sogar entspricht):

double value = 0.3333; // Beispielwert
// 1. Anzahl (unsigned 'n') der Nachkommastellen ermitteln [...]

// 2. Wert zum erweitern berechnen:
int zaehler = 1;
for(unsigned u = 0; u < n; u++)
  zaehler *= 10;

int nenner = 0.3333 * zaehler;

// Das müsste man dann nur noch kürzen :)

Jetzt meine Frage(n) :
1. Ist das effizient bzw. geht das effizienter?
2. Fallen euch, so beim drüber schauen, Fehler auf, oder hab ich irgendetwas nicht berücksichtigt?

Ich danke nochmals!

Uchuujinsan

War vllt etwas undeutlich geschrieben, im Grunde mein ich ziemlich genau das was du in deinem code machst.
Zum kürzen nur verwende ich eine andere Funktion, da du nach konstruktion vom zähler (zaehler *= 10;) ja bereits weißt dass er niemals durch etwas anderes als 2 oder 5 teilbar sein wird.
Ob dir das von mir oder von D besser gefällt musst du entscheiden, ich könnt auf jedenfall nicht guten Gewissens behaupten dass das was ich geschrieben hab schneller wär.

Deswegen versteh ich btw auch nicht was das Problem von Michael ist

[edit]
Mir fällt grad auf, zähler und nenner is bei dir "falschrum" benannt, fürs programm machts natürlich keinen unterschied

ghorst

effizient wäre es, wenn du aus der binärdarstellung direkt den bruch errechnen würdest und diesen dann kürzen würdest.
also mantisse in einen bruch umwandeln. das ist ziemlich trivial, da die mantisse nur aus einer summe von brüchen besteht, dann mit den exponenten kürzen/zusammenführen. den bruch mittels ggt kürzen. vorzeichen beachten, fertig.

Michael E.

Eure Lösungsansätze sind ja alle schön und gut, nur was macht ihr aus 1/3?

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    float foo = 1.0f/3.0f;
	cout << setprecision(15) << foo;
}

~ Ausgabe:
0.333333343267441

Frage 1: Wie viele Stellen hat foo? (alternativ für ghorst: Wie viele Stellen hat 0.2?)
Frage 2: Wie kann man foo wieder auf 1/3 zurückführen?

Uchuujinsan

Frage 2: Wie kann man foo wieder auf 1/3 zurückführen?

Gar nicht?
Beim Speichern können nunmal Informationen verloren gehen, da lässt sich nix dagegen machen.
0.333333343267441 kann von der Berechnung her alles Mögliche gewesen sein - aber eins ist es zu diesem Zeitpunkt auf jedenfall nicht: 1/3.

zwutz

Michael E. schrieb:

Frage 2: Wie kann man foo wieder auf 1/3 zurückführen?

garnicht.... du kannst zwar durch eine erhöhte Präzision annähernd 1/3 erreichen, aber nie vollständig.

und 0,333333343267441 ist nunmal nicht 1/3

genausowenig ist 0,333333333333333 1/3

Jede float oder double, die du von dem Programm bekommst, ist niemals ein Bruch mit dem Nenner 3

Wenn du tatsächlich mit Brüchen arbeiten willst, musst du deinem Programm beibringen, auch periodische Brüche zu akzeptieren...

in dem Fall: $0,\overline{3} = \frac{1}{3}$

ghorst

Michael E. schrieb:

alternativ für ghorst: Wie viele Stellen hat 0.2?)

den bruch kann man dual nicht in einer endlichen schreibweise darstellen. nur darum ging es hier nicht. es ging darum, wie man eine fließkomma zahl, die binär vorliegt, in einen bruch umwandelt.
dir sollte so gut wie mir bekannt sein, dass die fließkommadarstellung grundsätzlich verlustbehaftet ist.

Hm, wie kann ich denn die Anzahl der Nachkommastellen berechnen, da hängts grad^^?

So gehts nicht:

double value = 0.1234;
int iCounter = 1;
while((value = (value * 10.0 - static_cast<int>(value * 10.0))))
    ++iCounter;

(Das Ergebnis ist Schwachsinn.)

zwutz

du multiplizierst das ganze so lange mit 10, bis du eine Ganzzahl bekommst und merkst dir, wie oft du dafür *10 machen musstest.

Genauso oft multiplizierst du 10 *10, um den Nenner zu bekommen... dann hast du in deinem Fall
$\frac{1234}{10000}$

dann nur noch den GGT ermitteln und fertig

die praktische Umsetzung ist deine Sache

CStoll

Wobei man dazusagen sollte, daß double vermutlich nicht genau genug ist für so etwas - der Rechner schafft es noch nicht einmal, den Wert 0.1 exakt darzustellen. (die interne Darstellung von Gleitkommazahlen ist binär - und da ist 0.1 eine periodische Binärzahl)

Michael E.

zwutz schrieb:

du multiplizierst das ganze so lange mit 10, bis du eine Ganzzahl bekommst

Und wie merk ich das?

zwutz

float x = 1.5;
int y = (int)x;

if( x == y )
{
  cout << "Ganzzahl" << endl;
}

den ggt ermittelst du über

unsigned int ggt( unsigned int A, unsigned int B )
{
    int Rest;
    if (A && B)
    {
        while (Rest = A % B)
        {
            A = B;
            B = Rest;
        }
        return B;
    }
    else return !(A || B) + A + B;
}