C Double und Bitoperationen

[Krik]

Moin

Ich habe diese Formel:

Als effizienteste Lösung dieser Formel habe ich mir das überlegt:
In Abhängigkeit von k kommen als einzelne Summanden 1/1, 1/2, 1/4, 1/8, usw. raus.
Das sind - von 1/1 abgesehen - genau die Brüche, die in der Mantisse einer Gleitkommazahl stehen.
Wenn ich den Exponenten also um Eins erhöhe (die Mantisse beginnt ja immer mit 0,...[binär], meine Summe aber immer mit 1,... [binär]) und k-mal eine Eins in die Mantisse setze, habe ich schneller als bei allen anderen Möglichkeiten das Ergebnis berechnet.

Das Problem ist jetzt allerdings, dass man offenbar keine Bitoperationen auf Doubles anwenden darf.

summe.h

double summeBitoperationen(unsigned long k);

summe.c

#include <stdio.h>
#include "summe.h"

int main (int argc, char *argv[])
{
        unsigned long k = 1;
        double ergebnis;

        ergebnis = summeBitoperationen(k);
        printf("Summe nach Bitoperationen: %d\n", ergebnis);
}

double summeBitoperationen(unsigned long k)
{
        unsigned long i;
        double rueckgabe = 0;

        if ( k >= 0)
        {
                // Exponent setzen
                rueckgabe = (rueckgabe | 1) << 7; // Fehler Zeile 21

                // k-mal alle Bits nach links shiften und das neu eingefügte Bit auf 1 setzen
                for (i = 0; i < k; i++)
                {
                        rueckgabe = (rueckgabe << 1) | 1; // Fehler Zeile 26
                }

                // Alle Bits so weit nach links shiften, bis Exponent und Mantisse
                // nach IEEE-754-Format an der richtigen Stelle stehen.
                rueckgabe = rueckgabe << (52 - k); // Fehler Zeile 31
        }

        return rueckgabe;
}

Der GNU C-Compiler gibt mir das als Fehlermeldung zurück:

summe.c: In function `summeBitoperationen':
summe.c:21: error: invalid operands to binary |
summe.c:26: error: invalid operands to binary <<
summe.c:31: error: invalid operands to binary <<

Kann man keine Bitoperationen auf Doubles anwenden? Das wäre ja doof.

Kann mir jemand etwas dazu sagen? Es kann doch nicht sein, dass das bei Integer geht und bei Gleitkommazahlen nicht.

Gruß, Laurin

 

[Simpson474]

Ich bin mir zwar nicht sicher, ob deine Bit-Operationen passen, aber möglich ist das mit C schon:

unsigned long long int tmp;

// TODO: Bitoperationen auf tmp ausführen

double d = *((double*)&tmp);

 

[kuddlmuddl]

Ich glaub der Beweis, dass

Spoiler

2 ;-)

der Grenzwert ist geht schneller und ist ne bessere Übung als das in C++ nachzurechnen^^

Ich habs zwar noch nie gemacht, aber da C(++) ja extra low-level Arbeit auf dem Speicher erlaubt kann ich mir nicht vorstellen, dass es unmöglich ist das auf doulbe durchzuführen.
Kannst du nicht ansonsten vorher nen OR mit ner 0 machen um es in nen "veränderbaren" Speicherbereich zu kopieren?

 

[Krik]

Es geht nicht darum, den Grenzwert zu berechnen. Ziel der Übung (meines Profs) ist es, diese Formel so effizient wie möglich zu berechnen. Bitoperationen sind hier effizienter als der übliche Weg über rueckgabe += 1 / pow(2, k).

Mein Prof selber ist übrigens nicht auf diese Lösung gekommen und möchte, das ich das umsetze, damit man später die Ausführungszeiten vergleichen kann.


@Simpson474
Danke für den Tipp. Du schlägst also vor, eine 64 Bit Integer zu erzeugen, mit der man dann alles machen und dann auf double zu casten. Hm, so ne Konstruktion (long long int) habe ich noch nie gesehen. Ich werde es ausprobieren, danke.



Btw, wir werden gerade erst in C(++) eingeführt. Bitte nicht mit zu komplizierten Sachen kommen. Thx ^^



Edit:
Danke, Simpson747. Dein Tipp hat funktioniert.

Edit 2:
Sorry, Fehlalarm. Er übernimmt den Wert, der in dem Integer steht und wandelt die Bits so, dass eine Double exakt denselben Wert anzeigt. Sprich, es geht nicht so, wie es soll.

 

[Simpson474]

Sorry, Fehlalarm. Er übernimmt den Wert, der in dem Integer steht und wandelt die Bits so, dass eine Double exakt denselben Wert anzeigt. Sprich, es geht nicht so, wie es soll.

Hast du es wirklich so abgeschrieben mit den Adressoperatoren und Dereferenzierungsoperator? Das ganze ist nämlich kein einfacher Cast (dort geschieht genau das, was du jetzt beobachtest), sondern die direkte Kopie von Speicher.

 

[Krik]

unsigned long long int summe;
double rueckgabe = 0;
// ...
rueckgabe = *((double*)&summe);


So hab ich's gemacht. Die Änderungen sollten unerheblich sein.

 

[Simpson474]

Bei mir wandelt er direkt die Bits in einen Floating-Point Wert um - das Ergebnis denke ich ist jedoch falsch (sollte aber nicht an der Umwandlung liegen)

double summeBitoperationen(unsigned long k)
{
        unsigned long i;
        unsigned long long int rueckgabe = 0;

        if ( k >= 0)
        {
                // Exponent setzen
                rueckgabe = (rueckgabe | 1) << 7; // Fehler Zeile 21

                // k-mal alle Bits nach links shiften und das neu eingefügte Bit auf 1 setzen
                for (i = 0; i < k; i++)
                {
                        rueckgabe = (rueckgabe << 1) | 1; // Fehler Zeile 26
                }

                // Alle Bits so weit nach links shiften, bis Exponent und Mantisse
                // nach IEEE-754-Format an der richtigen Stelle stehen.
                rueckgabe = rueckgabe << (52 - k); // Fehler Zeile 31
        }

        return *((double*)&rueckgabe);
}

Außerdem solltest du einen Floating-Point Wert in printf nicht mit %d ausgeben.

 

[Krik]

Ok, wenn du sagst, dass die Umwandlung korrekt ist, dann hab ich wohl ein paar Bits falsch gesetzt. Ich werde nach harken.

Danke für deine Hilfe.

 

[kuddlmuddl]

Ziel der Übung (meines Profs) ist es, diese Formel so effizient wie möglich zu berechnen.

Um das wörtlich umzusetzen würde ich an deiner Stelle folgende Lösung abgeben:

double summe(int n) {
    double nennerVomRestBisGrenzwert = pow(2.0, n);
    return 2.0 - (1.0 / nennerVomRestBisGrenzwert);
}

In anderen Worten: Du brauchst weder irgend eine Art von Schleife noch Rekursion um das Ergebnis zu bestimmen.

Noch schneller zur Berechnung von pow(2.0, n) wäre dein Ansatz der Bit-Manipulation und nennerVomRestBisGrenzwert nicht als double sondern als int/long zu umzusetzen. Dort könnte man dann nämlich mit O(1) Komplexität die Berechnung von 2^n realisieren.
(pow() hat sicher steigende Laufzeit für größere n - wobei ich auch mal irgendwo aufgeschnappt habe, dass für Basis=2 diese Optimierungsmöglichkeit schon automatisch durchgeführt wird)

 

[Krik]

Es funktioniert.

#include <stdio.h>
#include "summe.h"

int main (int argc, char *argv[])
{
        unsigned long k = 52;
        double ergebnis;
        int i;

        ergebnis = summeBitoperationen(k);
        printf("Summe nach Bitoperationen:  %.16lf\n", ergebnis);

        scanf("%d",&i);
}

double summeBitoperationen(unsigned long k)
{
        unsigned long i;
        unsigned long long int rueckgabe = 0;

        if ( k >= 0)
        {
                // Exponent setzen
                rueckgabe = 1023;

                // k-mal alle Bits nach links shiften und das neu eingefügte Bit auf 1 setzen
                for (i = 0; i < k; i++)
                {
                        rueckgabe = (rueckgabe << 1) | 1;
                }

                // Alle Bits so weit nach links shiften, bis Exponent und Mantisse
                // nach IEEE-754-Format an der richtigen Stelle stehen.
                rueckgabe = rueckgabe << (52 - k);
        }
        return *((double*)&rueckgabe);
}

Deine Idee, kuddlmuddl, werde ich wohl auch umsetzen. O(1) ist sehr verlockend.

 

[kuddlmuddl]

Joa wenn dein Prof an diese Lösung mit "Grenzwert - Rest" noch nicht gedacht hat ist das sicher lustig. Ich behaupte mal, dass selbst die einfache, von mir gepostete Lösung, ohne weitere Optimierung schon für sehr kleine n schneller als jede Schleife/Rekursion ist. Für große n natürlich um so mehr!

Allgemeingültig kontante Laufzeit bzw. O(1) für reale Programme auf realen Maschinen zu behaupten ist immer etwas gewagt denn wenn jetzt jemand z.B. sagt er möchte gerne 123^(465^(789^123)) für n einsetzen steht man vor dem Problem der begrenzten 32/64 bit der üblichen Datentypen. Außerdem wird nen double da nicht die Genauigkeit hergeben noch nen Unterschied zu 2 darstellen zu können.
Man braucht dann halt bigfloat/bigdouble Klassen die meist auch mit wachsender Laufzeit einhergehen- allein fürs Speicherreservieren^^
Ich glaub in der Informatik meint man daher auch eher theoretische Komplexität eines Algos und nicht reale Laufzeit auf einem PC

Zumindest solange n kleiner ist als INT_MAX sollte das aber tatsächlich in konstanter Zeit gehen. Musst halt nur 2^n durch bitshifts direkt setzt.
Also quasi
int nennerVomRestBisGrenzwert = 1;
// n mal shiften

 

[Krik]

Die Genauigkeit von Double reicht hier bis 16 Stellen nach dem Komma. Demnach wäre es unsinnig k = 17 oder größer zu berechnen, da er dann immer auf 2 rundet.

Ich habe deine Idee mal umgesetzt:

double summeBitoperationenOptimal(unsigned long k)
{
        unsigned long long int differenzBisGrenzwert = (1023 + k) << 52; // = 2^n                          
        
        return 2.0 - (1.0 / *((double*)&differenzBisGrenzwert); // 2 - (1/(2^n))
}

In der return-Zeile, genauer gesagt, bei dem *((double*)&differenzBisGrenzwert sieht er einen Syntaxfehler, den ich nicht sehe. Ich vertage das wohl auf morgen, dann sehe ich den Fehler vielleicht auch.

 

[kuddlmuddl]

3 öffnende Klammen auf aber nur 2 schließende

Wieso eigtl 1023?
Is nicht die Zahl "1" die Bitfolge 0....01?

Und nur ne ungünstige Benennung:
Dein "differenzBisGrenzwert" ist nicht die Differenz selbst sondern nur der Nenner der Differenz

 

[IceMatrix]

O(1) ist nicht automatisch besser als O(n). Das hängt in erster Linie davon ab von welchen n-Werten du ausgehst und natürlich auch wie leistungsfähig die pow-Funktion ist.
Die Lösung über das Setzen von Bits ist jedenfalls nicht die schlechteste...

Btw. du kannst 1.0/X auch über X^(-1) darstellen.. Bias bei Double ist 1023, d.h. du solltest nicht it (1023+k) arbeiten, sondern mit (1023-k). So sparst du die Division.

 

[Krik]

Double verwendet das IEEE-754-Format. Man hat 1 Bit Vorzeichen, 11 Bits für den Exponenten und 52 Bits für die Mantisse.
Jede Zahl wird erst normalisiert, so dass sie als 0,...b * 2^e vorliegt. Die 0,...b wird ohne "0," direkt als Mantisse geschrieben. Der Exponent e wird auf 1023 addiert und dann in seinen Bereich geschrieben. 1023 deshalb, damit auch negative Exponenten gespeichert werden können, ohne dafür auch noch extra ein Bit für ein Vorzeichen verwenden zu müssen.

Das ist die Kurzfassung, wie Gleitkommazahlen intern gespeichert werden. Es gibt ein paar wenige Variationen, aber so in etwa geht es.


Da fällt mir auf, dass ich in die Mantisse mindestens 1 Bit setzen muss, sonst rechnet er ja 0 * 2^irgendwas.
Und danke für den Hinweis mit der Klammer. Das hab ich irgendwie total übersehen. Es war vermutlich einfach zu spät für mich, noch an so was zu knobeln.


Edit:
@IceMatrix
Das stimmt, ich kann mir das 1/X sparen. Ich werde mich morgen(heute) noch mal dran setzen.

Edit 2:
Die optimale Funktion ist jetzt fertig. Nächste Woche wird dann mit den anderen Möglichkeiten, die Formel aus zu rechnen, verglichen.

double summeBitoperationenOptimal(unsigned int k)
{
        unsigned long long int nennerVomGrenzwert = (1023LL - k) << 52; // 2^(-k) = 1/(2^k)

        return 2.0 - *((double*)&nennerVomGrenzwert); // 2 - (1/(2^k))
}

 

[IceMatrix]

wenn dein compiler richtig optimiert (also aus der 64-bit arithmetik ne 32-bit berechnung macht), dann ist der code schon verdammt gut