Klasse für sehr große Zahlen

  • Hallo, ich arbeite gerade an einer Klasse für sehr große Zahlen, dabei verwende ich intern ein dynamisches char array wo die einzelnen Ziffern gespeichert sind. Ich habe bereits die Operatoren für Addition, Subtraktion und Multiplikation implementiert, nur bei der Division hab ich kein Plan.Als erstes dachte ich an die schriftliche Division, die man in der Schule lernt, aber die setzt sich ja auch aus Division zusammen.Ich kann aber nicht ausschließen, dass der Divisor so groß wird, dass er nicht mehr in ein long long reinpasst, und es einen Überlauf gibt.Hat jemand vielleicht eine Idee wie man die Division machen könnte, es gibt hier ja bestimmt einige, die schon mal solch eine Klasse geschrieben haben.

  • Bei der schriftlichen Multiplikation multiplizierst du ja immer nur 2 Ziffern das bedeutet das Ergebnis ist maximal 81 groß passt also immer in ein int. Bei der schriftlichen Division "nimmst" du dir aus dem Dividend immer Ziffern, dann teilst du diese Zahl durch den Divisor. Das ergibt dann immer eine Stelle des Ergebnis. Da der Divisor aber auch so groß sein kann, dass er nicht mehr in ein long long reinpasst, brauch ich eine andere Vorgehensweise.

  • Hm, stimmt.

    Meine einzige, aeusserst ineffiziente, Idee waere, fuer jede Stelle des Ergebnisses alle moeglichen Ziffern durchzuprobieren. Also ne Rueckfuehrung auf die Multiplikation. Gibt aber vermutlich bessere Loesungen ;)

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • Eine andere Idee wäre sooft wir es geht Dividend-=Divisor zu machen, solange das größer 0 ist. Aber für große Differenzen dauert da ja ewig...

    Du könntest diese Methode nur für die "Basisdivision" verwenden (also den Teilschritt, der bei der schriftlichen Division auftritt). Da bei der schriftlichen Division ein kleinstmöglicher Prefix genommen wird der sich teilen lässt, ist die Anzahl der Subtraktionen auf 10 pro Prefix und die Anzahl der Basisdivisionen auf die Länge des Dividenden beschränkt, also gesamt dann 10*Länge des Dividenden (+Anzahl der gewünschten Nachkommastellen), unabhängig von der Differenz zwischen Divisor und Dividend.

    Falls das kein Übungsbeispiel ist sondern du die Klasse nur verwenden willst, dann bin ich aber sicher dass es schon gute Implementierungen von besseren Algorithmen gibt.

    Einmal editiert, zuletzt von Christoph R. (16. April 2014 um 16:33)

  • Das ist eine super Idee, darauf muss man erst mal kommen. Ich mache die ganze Klasse zum Üben, aber auch weil ich sie später verwenden will. Ich mach das sozusagen als Freizeitprojekt, man kann ja immer etwas verbessern. Außerdem hab ich dann was eigenes, worauf ich stolz sein kann.

  • Mir ist grad noch was aufgefallen, ich speichere die Ziffern meiner Klasse in einem char array, das kann ja maximal so groß werden wie der größte unsigned long long, das ist zwar gewaltig und diese Zahl hat dann wesentlich mehr Stellen als die größte bis jetzt gefundene Primzahl, aber kann man das irgendwie umgehen?

  • Mir ist grad noch was aufgefallen, ich speichere die Ziffern meiner Klasse in einem char array, das kann ja maximal so groß werden wie der größte unsigned long long, das ist zwar gewaltig und diese Zahl hat dann wesentlich mehr Stellen als die größte bis jetzt gefundene Primzahl, aber kann man das irgendwie umgehen?

    Verwende ein n-dimensionales Array, um die Anzahl der Stellen mit n zu potenzieren ;)

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • Das verstehe ich jetzt irgendwie nicht, kannst du es mir genauer erklären

    Normalerweise verwendest du ein char[n][1]-Array, um eine n-stellige Zahl zu speichern. Wenn n jetzt groesser ist als die maximale Arraygroesse MAX, benutzt du stattdessen ein char[MAX][2]-Array, wobei die ersten MAX Stellen die Indizes [i][1] (0≤i<MAX) haben und die weiteren die Indizes [j][2] (0≤j<n-MAX). Wenn selbst das nicht ausreicht, kannst du die zweite Dimension wieder vergroessern (char[MAX][3] usw.), bis hin zu einem char[MAX][MAX], das MAX^2 Stellen speichern kann.
    Wenn du NOCH groessere Zahlen willst, haengst du noch ne dritte Dimension an (char[MAX][MAX][k]), in der du dann bis zu MAX^3 Stellen speichern kannst, usw..

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • Ich hab gestern und vorgestern probiert die Methode für die Division zu machen, und habs irgendwie nicht geschafft:wein:
    Ich beschreib euch nochmal meinen Ansatz, vielleicht ist daran ja etwas falsch:
    1.Führe die folgenden Schritte solange durch, wie man eine geeignete Zahl hat, um durch den Divisor zu dividieren
    2. Subtrahiere von dem gefundenen Dividenden den Divisor, solange wie der Dividend >= Divisor ist
    3. Merke dir die Anzahl in einer Variable, die i-te Stelle der Ergebnis ist die Anzahl
    4. Zähle i um eins hoch
    5. Versuche an den Rest, der bei der Subtraktion geblieben ist, geeignete Ziffern von a anzuhängen, sodass man wieder eine
    geeignete Zahl findet, die durch den Divisor dividiert werden kann.

    Ist das richtig so, oder wie würdet ihr das Problem lösen

  • Die Beschreibung ist etwas verworren, ich sehe aber spontan keinen Fehler ^^
    Du kannst auch gerne deinen Code posten, wenn du Hilfe beim Debuggen brauchst ;)

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • Die Beschreibung ist etwas verworren, ich sehe aber spontan keinen Fehler ^^
    Du kannst auch gerne deinen Code posten, wenn du Hilfe beim Debuggen brauchst ;)


    JA, so sah auch der Code aus, ich hab alles wieder gelöscht und wollte die ganze Methode noch mal sauber programmieren. Wie würdest du die Methode umsetzen? Du musst jetzt keinen fertigen Code schreiben, nur so ein Pseudocode, also so formuliert wie ein Backrezept beispielsweise.

    Einmal editiert, zuletzt von henriknikolas (23. April 2014 um 21:03)

  • Wie detailliert willst dus denn? ^^

    Wenn man fuehrende Nullen im Ergebnis vermeiden will, muesste man bei der Initialisierung von m noch aufpassen

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

  • Ich hab die Division implementiert wie im folgenden Link beschrieben, volkards 2. Algorithmus eher am Ende:http://www.c-plusplus.de/forum/110407-full
    Ich werde dann wenn ich wieder Zeit habe meinen Code hier posten, damit ihr nochmal rübergucken könnt, dann werde ich noch versuchen Bradons Variante zu implementierten und beide hinsichtlich ihrer Geschwindigkeit vergleichen. Das wird natürlich etwas dauern, da für mich jetzt die Schule wieder anfängt.

    Einmal editiert, zuletzt von henriknikolas (27. April 2014 um 20:09)

  • So, ich hab jetzt meinen Code schön dokumentiert, hier ist er:


    Kann man das noch irgendwo optimieren oder verbessern, ich bin dankbar für jeden Ratschlag:thumb:

    2 Mal editiert, zuletzt von henriknikolas (1. Mai 2014 um 19:47)

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!