Performante Klasse für große Zahlen



  • Hey,

    ich möchte gerne eine Klasse schreiben, die eine besonders große Zahl repräsentieren kann. Dabei geht es nicht um große Präzision, sondern eher um Performance.

    Überlegt habe ich mir, dass ich einfach ein float als Basis speichere und ein Prefix (std::string) als "Ersatz" für die Nachkommastellen.

    Zahlen wie z.B. 100 oder 10000 würden nur das float verwenden und das Prefix leer lassen.

    Eine größe Zahl wie z.B. eine Quadrillion (1000000000000000000000000) könnte ich dann als z.B. 1 und Prefix "Q" speichern.

    Natürlich müsste ich noch Rechenoperationen einführen, was möglicherweise auch bedeutet, das sichergestellt werden muss, dass der Prefix bei z.B. einer Addition identisch ist.

    Ich wollte von euch einfach nur grundsätzlich wissen, ob dieser Ansatz funktionieren könnte oder ob ihr noch eine bessere Idee habt? Natürlich weiß ich, dass es bereits existierende Bibliotheken gibt, aber ich brauche die Komplexität nicht und es muss auch nur hinreichend genau sein.
    Sprich wenn man 1 Quadrillionen mit einer anderen addiert, dann soll auch 2Q rauskommen, aber wenn man die Zahl 1 zu einer Quadrillion addiert, dann ist das irrelevant. Negative Zahlen sind ebenfalls nicht notwendig.

    Ich bin sehr auf euer Feedback gespannt, denn ich habe das Gefühl, dass es sehr einfach aussieht, aber im Detail doch ein wenig komplexer ist und mein Ansatz möglicherweise zum Scheitern verurteilt. 🙄


  • Mod

    Grauenhafter Ansatz, wenn es um Performance geht. Wieso String? Wieso float? Du nutzt beides wie einen Integer und nennst keinen zufriedenstellenden Grund (oder genauer: du nennst gar keinen Grund) für deine Wahl. Beziehungsweise schlimmer noch: Dein String ist nur ein Mapping auf einen Integer (in deinem Beispiel 'Q' für Exponent 24), was nochmals um Welten ineffizienter ist. Außerdem ist 10 als Basis des Exponenten doof. Das ist menschenzentriert. Basis 2 ist im Computer um Welten schneller zu exponentieren.

    Bessere Wahl: Mantisse und Exponent beide als Integer speichern. Also quasi Fließkommazahlen mit Integern nachprogrammieren.

    Wobei mich doch mal interessieren würde, welche abgefahrene Anwendung du hast, bei der dir die 53 Bit Basis und der 11 Bit Exponent von handelsüblichen Fließkommazahlen nicht mehr reichen. Denn da diese im Computer direkt in der Hardware fest verdrahtet sind, sind sie viel, viel, viel schneller als alles, was du jemals mit der Integeremulation erreichen wirst. Es ist jedenfalls verwunderlich, dass du eine Quadrillion (10^24) als Beispiel für eine große Zahl nennst, wenn die im Computer eingebauten Fließkommazahlen locker bis 10^308 kommen.



  • Ich hatte an float gedacht, um z.B. auch 1,23Q darstellen zu können. An String hatte ich gedacht, weil es möglicherweise auch Prefixe geben wird die aus mehr als ein Zeichen bestehen. Insgesamt habe ich auch den Denkfehler gemacht, dass ich diese Zahlen ja irgendwie definieren muss und fand auch hier String besser. Tatsächlich ist das natürlich quatsch, weil ich ja ohnehin eine Funktion brauche, um z.B. "1,23Q" einzulesen (sprich String eher z.B. in Konstruktor).

    Es geht einfach um exponentielles Wachstum und die Zahlen werden sehr schnell ziemlich groß. Daran lässt sich auch in keinster Weise rütteln, sprich auch kein klassisches XY-Problem, sondern ich brauche tatsächlich das was ich oben beschrieben habe.

    Ja, mein Beispiel war nicht sehr repräsentativ, aber ich wollte auch das Forum nicht mit einer riesengroßen Zahl als Beispiel abnerven, das ist alles. 🤡

    Jedenfalls schon mal vielen Dank für deine Antwort. Ein paar sehr gute Punkte! Ich bin super froh nachgefragt zu haben und schaue mal, ob ich damit schon zurecht komme.

    Natürlich bin ich trotzdem für weitere Ideen und Anregungen offen. 👍


  • Mod

    ZahlDerGroße schrieb:

    Ich hatte an float gedacht, um z.B. auch 1,23Q darstellen zu können.

    1.23 Quadrillion sind 1230 Trilliarden. Oder Alternativ sind es 123 * 10^-2 Quadrillionen. Das ist das Geheimnis.

    Es geht einfach um exponentielles Wachstum und die Zahlen werden sehr schnell ziemlich groß. Daran lässt sich auch in keinster Weise rütteln, sprich auch kein klassisches XY-Problem, sondern ich brauche tatsächlich das was ich oben beschrieben habe.

    Dann klingt mein Lösungsvorschlag durchaus ganz passend.



  • ZahlDerGroße schrieb:

    ich möchte gerne eine Klasse schreiben, die eine besonders große Zahl repräsentieren kann. Dabei geht es nicht um große Präzision, sondern eher um Performance.

    Gibt es einen Grund dafür, dass du die Klasse selbst schreiben möchtest? Gerade weil es dir um Performance geht und sich dein erster Ansatz alles andere als performancemäßig durchdacht anhört... Ansonsten würde ich nämlich einfach mal ne fertige Bibliothek nutzen, zum Beispiel https://gmplib.org/ oder Boost.Multiprecision oder ...


  • Mod

    wob schrieb:

    ZahlDerGroße schrieb:

    ich möchte gerne eine Klasse schreiben, die eine besonders große Zahl repräsentieren kann. Dabei geht es nicht um große Präzision, sondern eher um Performance.

    Gibt es einen Grund dafür, dass du die Klasse selbst schreiben möchtest? Gerade weil es dir um Performance geht und sich dein erster Ansatz alles andere als performancemäßig durchdacht anhört... Ansonsten würde ich nämlich einfach mal ne fertige Bibliothek nutzen, zum Beispiel https://gmplib.org/ oder Boost.Multiprecision oder ...

    Ich hatte es nicht genannt, weil die Präzision des Exponenten bei denen nicht wählbar ist. Wobei der Vorgabewert bei ihnen halt auch die Größe eines Integers ist, was natürlich erst einmal identisch mit der einfachsten Ausführung meines Vorschlags ist. Aber falls es nicht ausreichend ist, kann man den Exponenten bei meinem Vorschlag relativ problemlos erhöhen, bei MPF steckt man fest.



  • wob schrieb:

    ZahlDerGroße schrieb:

    ich möchte gerne eine Klasse schreiben, die eine besonders große Zahl repräsentieren kann. Dabei geht es nicht um große Präzision, sondern eher um Performance.

    Gibt es einen Grund dafür, dass du die Klasse selbst schreiben möchtest? Gerade weil es dir um Performance geht und sich dein erster Ansatz alles andere als performancemäßig durchdacht anhört... Ansonsten würde ich nämlich einfach mal ne fertige Bibliothek nutzen, zum Beispiel https://gmplib.org/ oder Boost.Multiprecision oder ...

    Na ja, es handelt sich um eine Simulation mit exponentiellen Wachstum und es geht mehr um den Spaß als genauste Präzision. Außerdem werden manche Berechnungen sehr häufig stattfinden und die hohe Präzision dieser Bibliotheken wird die Performance unnötig reduzieren ohne das ich dadurch einen Vorteil habe.

    Gerade bin ich am Überlegen, ob ich nicht einen noch ungenaueren und noch billigeren Ansatz verwenden kann:

    int diff = exponent - other.exponent;
    
    // Differenz zu groß? Können wir vermutlich einfach ignorieren.
    if (abs(diff) >= 12)
    	return;
    
    if (diff != 0)
    {
        if (diff > 0)
            value += other.value / (pow(10, diff));
        else
            value -= other.value / (pow(10, diff));
    }
    else
    {
        value += other.value;
    }
    

    Hier ist value ein double und exponent ein int. Wenn der Exponent übereinstimmt, dann wird einfach addiert. Stimmt er nicht überein, dann wird versucht das Ergebnis entsprechend anzupassen und dann zu addieren.

    Theoretisch kann ich den gesamten Vorgang abbrechen, wenn die Differenz zu groß ist (z.B. die Genauigkeit von double überschreitet).

    Ich hab es nur sehr kurz getestet, aber es scheint so zu funktionieren und alles weitere scheint trivial.

    Weitere Ideen, Anmerkungen zu dieser Variante? Habe ich etwas nicht bedacht und renne damit in die Klinge?



  • Kann man so machen, allerdings ist der Code nicht richtig.
    Zum einen kannst du den zu addierenden Wert nur ignorieren, wenn dieser sehr klein ist (diff >=12). Im Falle von diff<=-12 natürlich nicht.

    Die Fallunterscheidung ist ebenfalls nicht richtig, es muss in allen Fällen value += ... lauten.

    Weiterhin musst du den Exponenten anpassen, falls nötig. Du könntest zwar den jeweils größeren Exponenten übernehmen, allerdings reicht das nicht ganz aus, da der Wert von value trotzdem noch entarten kann.
    Du müsstest dafür sorgen, dass value immer im Bereich von [0.1,1) bzw. (-1,-0.1] bleibt (außer bei 0).
    Apropos: es gibt hier keinen Grund, die teure Division zu verwenden, wenn du auch * pow(0.1, diff) rechnen kannst.


  • Mod

    Außerdem ist Basis 10 nach wie vor doof. Du denkst viel zu dezimalzentriert, wenn es dafür doch keinen guten Grund gibt, außer dass du es in der Grundschule gelernt hast. Wohingegen für 2 nach wie vor der extrem gute Grund spricht, dass ein Computer Potenzen davon besonders schnell berechnen kann.



  • ZahlDerGroße schrieb:

    Na ja, es handelt sich um eine Simulation mit exponentiellen Wachstum und es geht mehr um den Spaß als genauste Präzision. Außerdem werden manche Berechnungen sehr häufig stattfinden und die hohe Präzision dieser Bibliotheken wird die Performance unnötig reduzieren ohne das ich dadurch einen Vorteil habe.

    Das klingt für mich danach, als ob Du float oder double nutzen möchtest.



  • SeppJ schrieb:

    Außerdem ist Basis 10 nach wie vor doof. Du denkst viel zu dezimalzentriert, wenn es dafür doch keinen guten Grund gibt, außer dass du es in der Grundschule gelernt hast. Wohingegen für 2 nach wie vor der extrem gute Grund spricht, dass ein Computer Potenzen davon besonders schnell berechnen kann.

    Ja, das sehe ich ein, da es möglicherweise nur ein einzelner Bit-Shift ist. Allerdings könnte ich dann ja kein int mehr verwenden, denn:

    100 * 2^16.6096404744 = ~10000000

    anstatt

    100 * 10^5 = 10000000

    Abgesehen davon hätte ich kein Problem die Basis 2 zu verwenden. Mir scheint es einfach nur so als würde ich dadurch einfach an anderen Stellen Probleme bekommen (bzw. vermutlich auch ein bisschen das Grundschule-Argument).

    Insgesamt wieder sehr viele gute Hinweise. Vielen Dank dafür! 👍


  • Mod

    Ich kann dein Argument nicht im geringsten nachvollziehen. Ich weiß nicht einmal, was du sagen möchtest.



  • ZahlDerGroße schrieb:

    Ja, das sehe ich ein, da es möglicherweise nur ein einzelner Bit-Shift ist. Allerdings könnte ich dann ja kein int mehr verwenden, denn:

    100 * 2^16.6096404744 = ~10000000

    anstatt

    100 * 10^5 = 10000000

    Du hast die falsch Darstellung. Der Exponent ist ganzzahlig.
    100000 ist 1,52587890625 * 216
    100 ist 1,5625 * 26

    1,52587890625 * 216 * 1,5625 * 26 = 2,384185791015625 * 216+6

    Jetzt noch Normieren, damit der Faktor zwischen 1 und 2 liegt (Der Faktor wird durch 2 geteilt und der Exponent um eins erhöht)
    10000000 = 1,1920928955078125 * 223

    Zum spielen: https://www.h-schmidt.net/FloatConverter/IEEE754de.html


Anmelden zum Antworten