Gleitkommazahl in Bruch umwandeln

CStoll

zwutz schrieb:

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

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

Wenn du dein Programm fertig hast, kannst du mir ja mal mitteilen, wie der Wert 0.1 als Bruch aussieht

zwutz

CStoll schrieb:

Wenn du dein Programm fertig hast, kannst du mir ja mal mitteilen, wie der Wert 0.1 als Bruch aussieht

0.1 * 10 = 1

1 ist keine Bruchzahl mehr, und dafür wurde 1mal mit 10 multipliziert

daraus folgt: Zähler ist 1, Nenner ist 10 (10*1)

ggt aus 1 und 10 ist 1, also ist das endergebnis 1/10

sollte ja nicht so schwer sein

CStoll

zwutz schrieb:

CStoll schrieb:

Wenn du dein Programm fertig hast, kannst du mir ja mal mitteilen, wie der Wert 0.1 als Bruch aussieht

0.1 * 10 = 1

1 ist keine Bruchzahl mehr, und dafür wurde 1mal mit 10 multipliziert

daraus folgt: Zähler ist 1, Nenner ist 10 (10*1)

ggt aus 1 und 10 ist 1, also ist das endergebnis 1/10

sollte ja nicht so schwer sein

Na dann probier das mal in C++ aus (wie ich oben schon geschrieben habe, basiert double auf der Binärdarstellung - und kann den Wert 1/10 nicht exakt darstellen - genausowenig wie du in absehbarer Zeit den Wert 1/3 nicht exakt darstellen kannst)

Michael E.

Bei 0.1 wird er wohl noch Glück haben, weil die Binärdarstellung wohl 0.1 und en paar Zerquetschte sind. Aber wehe, wenn die Ungenauigkeit sich negativ auswirkt...

Simon2

CStoll schrieb:

...genausowenig wie du in absehbarer Zeit den Wert 1/3 nicht exakt im Dezimalsystem darstellen kannst)

zwutz

CStoll schrieb:

Na dann probier das mal in C++ aus (wie ich oben schon geschrieben habe, basiert double auf der Binärdarstellung - und kann den Wert 1/10 nicht exakt darstellen - genausowenig wie du in absehbarer Zeit den Wert 1/3 nicht exakt darstellen kannst)

#include <iostream>
using namespace std;

unsigned int ggt( unsigned int nZaehler, unsigned int nNenner )
{
   int nRest;
   if( nZaehler && nNenner )
   {
      while( nRest = nZaehler % nNenner )
      {
         nZaehler = nNenner;
         nNenner = nRest;
      }
      return nNenner;
   } else {
      return !( nZaehler || nNenner ) + nZaehler + nNenner;
   }
}

unsigned int macheZuGanzzahl( float fZahl, unsigned int *nNenner )
{
   int nTemp = (unsigned int)fZahl;
   while( nTemp != fZahl )
   {
      cout << "";
      *nNenner *= 10;
      fZahl *= 10;
      nTemp = (unsigned int)fZahl;
   }
   return (unsigned int)fZahl;
}

int main ()
{
   float fZahl = 0.1;
   unsigned int nNenner = 1;
   unsigned int nZaehler = macheZuGanzzahl( fZahl, &nNenner );

   unsigned int teiler = ggt( nNenner, nZaehler );
   nNenner /= teiler;
   nZaehler /= teiler;

   cout << nZaehler << "/" << nNenner << endl;

   return 0;
}

Et voilà

@zwutz: Ich bräuchte das aber (wie aus meinem Beispiel hervorgeht) für double und damit funktioniert es nicht .

Sonst funktioniert das echt gut - danke !

zwutz

Seeker schrieb:

@zwutz: Ich bräuchte das aber (wie aus meinem Beispiel hervorgeht) für double und damit funktioniert es nicht .

Sonst funktioniert das echt gut - danke !

hab ich gesagt, dass ich dir die Arbeit abnehmen will? Ich hab dir die nötigen Denkanstöße und ein halbwegs funktionierendes Beispielskript gegeben... der Rest liegt bei dir

Werner Salomon

Hallo Tim,

für das Umwandeln einer Gleitkommazahl in einen Bruch gibt es mehrere Verfahren. Zu beachten ist in jeden Fall, dass eine Gleitkommazahl selten genau ist (das wurde schon hinreichend erwähnt), ein Bruch dagegen schon. Folglich ist es in den meisten Fällen sinnlos, einen Bruch zu generieren, der der gespeicherten Gleitkommazahl exakt entspricht.
Man muss also die Genauigkeit mit angeben, mit der der gesuchte Bruch den Input treffen soll.

Der Klassiker zur Generierung eines Bruches ist das wiederholte Abschneiden der Ganzzahl und die Berechnung des Kehrwerts. Zum Beispiel 0,73913.
Die Ganzzahl ist 0 und der Kehrwert vom Rest ist 1,352942 also 1 + Rest 0,352942.
Bzw.: $0,73913=\frac{1}{1 + 0,352942}$
Mit dem Rest geht man jetzt genau so vor
$0,73913=\frac{1}{1 + \frac{1}{2 + 0,833327}}$
und im nächsten Schritt
$0,73913=\frac{1}{1 + \frac{1}{2 + \frac{1}{1 + 0,200009}}}$
und schließlich
$0,73913=\frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{4 + 0,999770}}}}$
den letzen Rest rundet man auf 1 und erhält nach Auflösen des Kettenbruchs 17/23.

Um das in Code zu gießen sollte man eine Klasse 'Bruch' habe, um diesen Kettenbruch zu berechnen zu können. Eine solche Bruchklasse findet man bei boost.rational.

Mein Lösungsweg ist ein rekursiver Ansatz. Das Problem dabei ist Nachführen des Epsilons, also das maximalen Deltas zwischen dem Input und dem berechneten Bruch.

#include <iostream>
#include <cassert>
#include <cmath>
#include <boost/rational.hpp>

template< typename Q, typename R >
Q make_rational( const R& x, R eps = 1.E-6 )
{
    using std::floor;
    assert( x > R(0) ); // nur für positive Zahlen
    if( x >= R(1) )
        return Q::int_type( floor( x ) ) + make_rational< Q >( x - floor( x ), eps );
    const R invR = 1/x;                           // Kehrwert
    const Q::int_type inv = Q::int_type( invR );  // Ganzzahl des Kehrwerts
    const R rest = invR - inv;                    // Rest bestimmen
    // --  Epsilon nachführen ...
    const R n_eps = inv * eps;
    if( n_eps > R(1) || rest <= (n_eps * inv)/(1 - n_eps)
        || rest >= ( R(1) - n_eps * (inv + 1) )/( R(1) + eps *(inv + 1) ) )
    {
        return Q( 1, (2* rest > R(1)? inv + 1: inv) );
    }
    return Q::int_type( 1 ) / ( inv + make_rational< Q >( rest, 2*eps*invR ) );
}

int main()
{
    using namespace std;
    for( double x; cout << "Eine Gleitkommazahl bitte: ", cin >> x; )
        cout << x << " := " << make_rational< boost::rational< int > >( x ) << endl;
    return 0;
}

Die Berechnung des Epsilon von einer Stufe zur nächsten ist noch nicht ganz richtig, aber es funktioniert.
Ein Prüfstein für solche Algorithmen ist immer das Verhältnis des goldenen Schnitts $\phi=\frac{1}{2}(\sqrt{5}-1)=0,61803398874989$ . Warum? - Debuggt Euch mal durch und schaut was mit dem Rest passiert.

Ein anderes Verfahren ist das von Farey. Man beginnt auch hier wieder mit dem Nachkommaanteil im Intervall der Brüche 0/1 und 1/1. Dann bestimmt man eine Mediante indem man beide Zähler und beide Nenner addiert und daraus einen neuen Bruch macht (-> 1/2). Nun wird geprüft, ob der neue Bruch kleiner oder größer der Gleitkommazahl ist und die Grenzen des Intervalls werden entsprechend neu gesetzt.
Der Algorithmus benötigt im Allgemeinen mehr Schritte als die klassische Methode, ist aber leichter zu codieren und benötigt auch keine Klasse Bruch. Ich habe hier einfach ein pair<int,int> anstatt des Bruchs gewählt.

#include <iostream>
#include <utility>      // std::pair
#include <cmath>        // std::abs

// -- Verfahren von Farey
std::pair< int, int > make_rational( double x, double eps = 1.E-6 )
{
    typedef std::pair< int, int > Q;// Ersatz für die Klasse Bruch
    const int vz = x < 0.0? -1: 1;  // Vorzeichen bestimmen
    if( vz < 0 ) x = -x;
    const int vk = int( x );
    x -= vk;                        // x enthält jetzt den Nachkommaanteil
    if( x <= eps )                  // x == Ganzzahl abfangen
        return Q( vz * vk, 1 );
    for( Q q1( 0, 1 ), q2( 1, 1 );;)
    {
        const Q med( q1.first + q2.first, q1.second + q2.second ); // Mediante bestimmen
        const double r = double( med.first ) / med.second;
        if( std::abs( r - x ) < eps )
            return Q( vz * (med.first + vk * med.second), med.second );;
        if( x < r )       // ist x < als die Mediante
            q2 = med;     // dann ist sie die obere Grenze
        else
            q1 = med;     // und ansonsten die untere Grenze
    }
}

int main()
{
    using namespace std;
    for( double x; cout << "Eine Gleitkommazahl bitte: ", cin >> x; )
    {
        pair< int, int > q = make_rational( x );
        cout << x << " := " << q.first << "/" << q.second << endl;
    }
    return 0;
}

Gruß
Werner

@swutz: du Witzbold, was hat das mit durcharbeiten zu tun? Hättest du dir mein 1. Post (und auch meine weiteren) durchgelesen müsstest Du *eigentlich* wahrgenommen haben, dass ich mich bereits intentiv mit der Materie auseinander gesetzt habe.

@Werner Salomon: Wahnsinn - Danke! Also ich hab mir das noch nicht alles durchgelesen, aber muss trotzdem schonmal meinen Dank ausprechen! - Falls ich noch Fragen habe, melde ich mich nochmal .

Viele Grüße an alle,
Tim.

Michael E.

Werner Salomon schrieb:

Ein anderes Verfahren ist das von Farey. Man beginnt auch hier wieder mit dem Nachkommaanteil im Intervall der Brüche 0/1 und 1/1. Dann bestimmt man eine Mediante indem man beide Zähler und beide Nenner addiert und daraus einen neuen Bruch macht (-> 1/2). Nun wird geprüft, ob der neue Bruch kleiner oder größer der Gleitkommazahl ist und die Grenzen des Intervalls werden entsprechend neu gesetzt.

Hey, das ist genau mein Ansatz Hatte nur in den letzten Tagen keine Zeit, das mal zu probieren.