BigINT und BigFLOAT // Operatoren

This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

  • BigINT und BigFLOAT // Operatoren

    Seid gegrüßt Kameraden!
    Ich bin gerade dabei zwei Klassen zu schreiben, die Klassen BigINT und BigFLOAT.
    Wie es der Name schon möchte ich sehr große Zahlen möglich machen. Ja, es gibt schon fertige Bibliotheken dafür und nein ich möchte diese zwei Klassen zur Übung schreiben.
    Nun möchte ich es so realisieren, in der BigINT ein std::string zu benutzen, bei BigFLOAT wende ich ebenso ein std::string an.
    Doch habe ich kleine Probleme die Operatoren zu schreiben. Gerade was die Addition und Subtraktion betrifft habe ich Probleme, letztens braucht man ja "nur" diese und kann dann damit den Operanden der Division und Multiplikation sowie Modulo überladen. Dann natürlich noch größer und kleiner, etc.pp.
    Nur um zum einfacheren Teil zu kommen, muss ich ja erst mal den schweren machen. Als schweren Teil bezeichne ich besonders die Addition. Letztens ist die Subtraktion auch nichts anderes als eine Addition. Naja... ^^
    Ich lud mir die Bibliothek bzw. einzelne Klasse "large" herunter, unter Google vielleicht schwer zu finden, doch was dort in der Addition gemacht wird, das sagt mir überhaupt gar nichts. Dort ist eine Funktion "Add", die bei dem Operator "+" aufgerufen wird, dazu dann nochmal zusätzlich massig Code. Insgesamt für die Addition ~100. Meine Idee persönlich wäre, das irgendwie in das Binärsystem umzuwandeln, wobei das doch irgendwie sinnlos/sehr langsam bei einem std::string sein dürfte, und damit dann zu arbeiten, wie bei Minecraft, da ist die Addition leichter, empfinde ich. xD
    Naja, hat irgendjemand einen Ansatz oder besser Pseudo-Code, eine Erklärung, sonst irgendwas, um mir behilflich zu sein?

    MfG
    Check

    //Erledigt

    The post was edited 2 times, last by Checkmateing ().

  • Nur einen kleinen Denkanstoß: Bei großen Integern benutzen die Bibliotheken normalerweise einfach mehrere kleine Integer Variablen, die dann geeignet "zusammengehängt" werden. Mit String wird das doch sehr langsam, da ist man ja dann ständig am parsen.

    Von BigFloats hab ich in der Form noch nichts gehört, da der Wertebereich da ja eher nicht das problem ist. Aber z.B. quadruple-precision floats zu implementieren ist bestimmt mal interessant, mit Strings würd ich das aber auch nicht machen ;)
  • Halt Floats bzw. Doubles mit sehr vielen Nachkommastellen um z.B. Pi annähernd zu berechnen.
    Daran dachte ich als erstes auch. Doch was ist denn dann, wenn du bei Array[0] nun überschreitest und dann bei Array[1] die gewissen Zahlengruppen dann ändern musst. Wie willst du das bitte anstellen? Klingt ja erst machbar, doch ich denke es ist größerer Aufwand und vor Allem pures Herumprobieren, bis das überhaupt so funktioniert. Mal drüber nachdenken. Nehmen wir an, dass ein IONT mal die maximale Größe von 10 hat. Nun nehmen wir IONT_Array[0] welches 9 ist, IONT_Array2[0] und IONT_Array3[0], welche ebenso 9 sind, und addieren diese. Nun multiplizieren wir nochmal mit 9. Jetzt dürfen wir den Wert ausrechnen, was wir keinesfalls über die normalen Werte, höchstens als "kleinen" Puffer, betreiben können, die könnten bei der Rechnung ja überlaufen... Nun haben wir also [tex](9+9+9)*9 = 27*9 = 243[/tex] und dürfen diese dreistellige Zahl einordnen, die wir vorher erhalten und eingeordnet, wo und wie auch immer, haben. Wie willst du das bitte tun? Beim Rechnen müsste man jede einzelne Ziffer genaustens einordnen. Das wäre doch wohl schwieriger, oder? :S
    Bei Allen Bibliotheken die ich sah wurde entweder ein char* oder ein std::string verwendet. Nenne doch mal ein Beispiel, dann kann ich mir die mal ansehen. ;)

    MfG
    Check

    The post was edited 4 times, last by Checkmateing ().

  • Machst du das zur Übung? Wenn nein benutz eine Fertige Bibliothek.

    Ansonsten eine Möglichkeit wäre es, die Ascii-Werte (Ziffern) runterzurechnen auf ihre tatsächliche Ziffernwerte damit man mit diesen einfacher Rechnen kann:
    '9' (0x39) - '0' (0x30) = 0x09
    '7' (0x37) - '0' (0x30) = 0x07
    Damit hätte man eine Ziffer pro Byte gespeichert.

    Die Addition dann von Hand zu für jedes Byte durchführen:
    "68" (z1) + "17" (z2)

    Source Code

    1. ueberlauf = 0
    2. for (i=last_zeichen; i>=1; --i)
    3. {
    4. add = z1[i] + z2[i] + ueberlauf;
    5. e = add % 10;
    6. ueberlauf = add / 10;
    7. }

    = "85" (e)

    Hier ein Beispiel:

    Source Code

    1. #include <iostream>
    2. #include <vector>
    3. using namespace std;
    4. class bigReal
    5. {
    6. public:
    7. vector<unsigned char> integer; // ganzzahlen (rueckwarts gespeichert)
    8. vector<unsigned char> comma; // kommazahlen (vorwaerts gespeichert)
    9. public:
    10. // constructor
    11. bigReal(char *value)
    12. {
    13. setValue(value);
    14. }
    15. // destructor
    16. ~bigReal()
    17. {
    18. }
    19. // wert setzen
    20. void setValue(char *value)
    21. {
    22. if (!value) return;
    23. // komma position ermitteln
    24. unsigned int len = strlen(value);
    25. char *pos = strstr(value, ".");
    26. unsigned int p = 0;
    27. if (pos)
    28. p = pos - value;
    29. else
    30. p = len;
    31. // ganzzahlen extrahieren
    32. integer.resize(p);
    33. for (unsigned int i=0; i<p; ++i)
    34. integer[i] = value[p-i-1] - '0';
    35. // kommazahlen extrahieren
    36. comma.resize(len-p-1);
    37. for (unsigned int i=0; i<(len-p-1); ++i)
    38. comma[i] = value[p+i+1] - '0';
    39. }
    40. const bigReal operator+(bigReal & rhs)
    41. {
    42. bigReal add = *this;
    43. // komma laenge anpassen
    44. if (rhs.comma.size() > add.comma.size())
    45. add.comma.resize(rhs.comma.size(), 0);
    46. else
    47. if (rhs.comma.size() < add.comma.size())
    48. rhs.comma.resize(add.comma.size(), 0);
    49. // komma addition durchfuehern
    50. char val = 0;
    51. for (int i=rhs.comma.size()-1; i>=0; --i)
    52. {
    53. val = rhs.comma[i] + add.comma[i] + val;
    54. add.comma[i] = val % 10;
    55. val /= 10;
    56. }
    57. // ganzzahl laenge anpassen
    58. if (rhs.integer.size() > add.integer.size())
    59. add.integer.resize(rhs.integer.size()+1, 0);
    60. else
    61. if (rhs.integer.size() < add.integer.size())
    62. rhs.integer.resize(add.integer.size(), 0);
    63. // ganzzahl addition durchfuehren
    64. for (int i=0; i<rhs.integer.size(); ++i)
    65. {
    66. val = rhs.integer[i] + add.integer[i] + val;
    67. add.integer[i] = val % 10;
    68. val /= 10;
    69. }
    70. // zahlenarray packen
    71. add.pack();
    72. rhs.pack();
    73. return add;
    74. }
    75. void pack()
    76. {
    77. unsigned int p = 0;
    78. // fuerende null beim komma entfrennen
    79. if (this->comma.size())
    80. for (unsigned int i=this->comma.size()-1; i>=0, !this->comma[i]; --i, ++p);
    81. if (p)
    82. this->comma.resize(this->comma.size()-p);
    83. p=0;
    84. // fuerende null bei ganzzahlen entfrennen
    85. if (this->integer.size())
    86. for (unsigned int i=this->integer.size()-1; i>=0, !this->integer[i]; --i, ++p);
    87. if (p)
    88. this->integer.resize(this->integer.size()-p);
    89. }
    90. };
    91. // globaler stream hilfsfunktion zur ausgabe der zahlen
    92. ostream& operator<< (ostream& out, bigReal &c)
    93. {
    94. for (int i=c.integer.size()-1; i>=0; --i)
    95. out << char(c.integer[i] + '0');
    96. if (c.comma.size())
    97. {
    98. out << ".";
    99. for (unsigned int i=0; i<c.comma.size(); ++i)
    100. out << char(c.comma[i] + '0');
    101. }
    102. return out;
    103. }
    104. // einstiegspunkt
    105. int main(int argc, char **argv)
    106. {
    107. bigReal a("323242157586876942362435642.78343243253214324567899566435");
    108. bigReal b("1243765956956214531253424149.45232143265765876954563452523");
    109. bigReal c = a + b;
    110. cout << a << "+" << endl << b <<"=" << endl << c <<endl;
    111. system("PAUSE");
    112. return(0);
    113. }
    Display All

    8
    Hoffe der Ansatz hilft dir. Natürlich kann man das ganze noch mehr optimieren, zB wie schon erwähnt mehrere Ziffern zb. in ein großeren Datentyp packen etc. um Speicher zu sparen (wobei hier wohl die Performance drunter leidet).

    Mfg Rushh0ur
  • Checkmateing wrote:

    Nenne doch mal ein Beispiel, dann kann ich mir die mal ansehen.

    Die GNU Classpath Implementation der Java BigInteger Klasse z.B. : developer.classpath.org/doc/java/math/BigInteger-source.html
    Und im Gegenzug kannst du ja mal ein Beispiel nennen, bei dem das jemand wirklich mit Strings macht. Nur weil jemand ein Char-Array benutzt, heißt das ja nicht, dass er die ASCII kodierten Zeichen benutzt sondern nur, dass er die Zahl byte-weise speichert. Aber ansonsten funktioniert das dann trotzdem genau so wie mit ner Reihe von Integern. Mit ganzen Integern kann man halt effizienter rechnen, da die CPU sie aufeinmal verarbeiten kann.

    Ansonsten versteh ich leider nicht mal ansatzweise was du in deinem zweiten Post sagen willst. Ich kann dir aber versichern: Das ist in keinster weise herumprobieren, das funktioniert schon richtig...
  • Es geht um das Prinzip. Bei dem Engine-Beispiel handelte es sich auch spezifisch für C++, ich kann ja gleich Python benutzen, dann wöllte ich das gar nicht zu tun.
    Hör doch auf zu zicken, dann sind wir alle glücklich, inklusive du selbst, denn dann bekommst du auch garantiert keine schnippischen Antworten mehr von mir. ;)
    Die Frage ist beantwortet, Punkt, fertig, Ende.

    MfG
    Check
  • Gehts dir noch gut? Ich glaub es hakt. Wenn du meine Tipps nicht annehmen willst ok, aber das geflame kannst du dir echt sparen. Ich wollte dir nur sagen nach welchem PRINZIP solche Klassen arbeiten, die in der realen Welt in realen Anwendungen zum Einsatz kommen, wo es auch um Geschwindigkeit und Speichereffiziens geht. Und um das Prinzip zu verstehen ist es völlig egal in welcher Sprache das ist, nur weil das Beispiel in Java ist, musst du es ja nicht in Java umsetzen.
    Aber du hast von Anfang an eh nicht verstanden was ich meine, und hast offensichtlich auch kein Interesse daran es zu verstehen. Dann kopier doch einfach von jemandem die fertige Lösung, wenn du meinst, dass dir das hilft. Aber was will man von jemandem erwarten, der nichtmal nen geraden deutschen Satz hinbekommt.
  • Nicht mal gerade einen deutschen Satz? Tut mir Leid, allein schon ein simples "Sei gegrüßt!" ist ein deutscher Satz. Ich bin Wohl oder Übel meiner Sprache mächtig.
    Du setzt das Prinzip in völlig falsche Dinge und drehst mir das Wort im Munde herum. Konkret wurde nach C++ gefragt, konkret, und ich bin in der Hinsicht Sprachen sehr konservativ, was du hier machst ist noch viel schlimmer, du kurbelst eine völlig sinnlose Diskussion an, einen völlig sinnlosen Streit. Lass mich doch so lernen, wie ich es für richtig halte und mische dich nicht ein. Wenn du darauf geachtet hättest, was ich in meiner Anfrage schrieb, dann wüsstest du, dass ich eher nicht "Copy & Paste" benutze, ich denke nach der Lernzeit an dieser Sprache werde ich wohl auch wissen wie ich zu lernen habe. Ich für meinen Teil griff ich dich nicht persönlich an, du allerdings meinst, dass ich nicht der Deutschen Sprache mächtig sei, ich wohl dumm sei, denn an deiner Aussage/deinen Aussagen gibt es wohl wenig falsch zu verstehen.
    Wenn du der Meinung bist, dass man so eine Diskussion führt, dann, wenn du unbedingt weitermachen musst, geh erst mal Rhetorik richtig beherrschen und gib hier nicht so unqualifizierte Beiträge gegenüber meinerseits! Man beleidigt den Gegenüber nicht bzw. greift ihn nicht persönlich an, nur Gegenwehr ist angebracht. Wenn meine Sprache so schlecht sein soll, dass ich nicht mal einen Satz herausbekäme, was ist dann deine Redensart, mit solchen Rechtschreibfehlern wie "kopier", der Imperativ ist doch eher gleich mit dem Infinitiv, "nichtmal", wird getrennt als 'nicht mal' geschrieben, mit einem möglichen Präfix 'ein-' vor dem 'mal', "nen" soll das 'einen' heißen?
    Des Weiteren, und da möchte ich nur meine Meinung zum Thema abgeben, die aber nicht unbedingt von Korrektheit geprägt ist, ist es unangenehm über so viele Anglizismen zu lesen.
    Es mag Leute geben, die, wenn sie in einem C/++/D-Thema nachfragen, nach Antworten zu C++ suchen mögen und nicht nach solchen für Java. Genauso wie es Rushh0ur tat, genauso habe ich mir es gewünscht. Er selbst hat sich viel Arbeit gemacht, gleich eine kleine Klasse dazu zu schreiben, wo ich doch mit offenen Armen Pseudo-Code empfangen hätte, doch es war C++. Es gibt nun mal Leute, die, wenn man nach Beispielen für beschriebene C++-Engines fragt, Java-Engines als Antwort akzeptieren und nun mal eben sich, mithilfe des Internets, den Java-Code verständlich machen möchten. Hättest du mir wirklich helfen wollen, dann hättest du einen Pseudo-Code geschrieben.
    [...]Und um das Prinzip zu verstehen ist es völlig egal in welcher Sprache das ist, [...]

    Falsch. Python war bereits ein genanntes Beispiel. Vollkommen egal ist es nicht.
    Doch nur als kleine Randbemerkung: Wenn es doch so egal ist in welcher Sprache, warum legst du dann selbst nicht ein Pseudo-Beispiel daher, wenn es denn nur um das Verständnis geht.
    Ich für meinen Teil muss ja wohl noch nicht für "die reale Welt und in deren realen Antworten" eine solche Klasse schreiben, ebenso schrieb ich, dass dies eine Übung sei. Für eine Übung ist es doch nicht schlimm, na und, selbst wenn ich was falsch machen würde, du kannst von ausgehen, dass ich noch mehrere Übungen in dieser Hinsicht durchführen würde.
    Nicht du bist komplett daran Schuld, ich hätte, genau wie diese Antwort hier, einfach aufhören können weiter mit dir zu diskutieren. Doch es heißt doch, der klügere gibt nach. Da du dich auf diesem Gebiet auskennst und ich nicht, du somit klüger bist, solltest du eher nachgeben als ich, oder? Es heißt nicht, dass der Intelligentere nachgibt, es gibt Unterschiede zwischen Intelligenz und Klugheit.
    Dieses Thema ist jetzt also hoffentlich endgültig erledigt.
    Da fragt man nach langem wieder was und dann das.... '._.
    Unschön.


    MfG
    Check

    PS: Danke der Nachfrage, mir geht es ganz gut soweit. ;)