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.
Klasse für sehr große Zahlen
-
-
Kann mir keiner helfen?
-
Was hast du denn bei der Division fuer ein Problem, das du bei der Multiplikation nicht auch haettest?
-
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
-
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...
-
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.
-
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
-
Verwende ein n-dimensionales Array, um die Anzahl der Stellen mit n zu potenzieren
Das verstehe ich jetzt irgendwie nicht, kannst du es mir genauer erklären -
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.. -
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 -
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. -
Wie detailliert willst dus denn?
Code
Alles anzeigenVariablen: m fuer den jeweiligen Minuend, i (int) fuer eine einzelne Stelle des Ergebnisses m mit den (Laenge des Divisors) hoechstwertigen Stellen des Dividenden initialisieren Wiederhole folgende Schritte: i = 0 Wenn m > Divisor i = i + 1 m = m - Divisor Andernfalls Die hoechstwertige, unbenutzte Stelle des Ergebnisses mit i belegen Wenn der Dividend noch (mindestens) eine unbenutzte Stelle hat m = m * 10 + (hoechstwertige unbenutzte Stelle des Dividenden) Andernfalls Ergebnis zurueckgeben
Wenn man fuehrende Nullen im Ergebnis vermeiden will, muesste man bei der Initialisierung von m noch aufpassen
-
Vielen dank, werde ich mal ausprobieren, ich habe gestern noch eine andere Variante gefunden, dann kann ich die beiden Varianten mal vergleichen
-
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. -
So, ich hab jetzt meinen Code schön dokumentiert, hier ist er:
Code
Alles anzeigenbool Int::compare_size(char *a, char*b, unsigned long long a_max, unsigned long long b_max) { //Diese FUnktion liefert a >= b zurück //Nullen am Anfang von a und b entfernen check(a, a_max); check(b, b_max); //Überprüft ob a >= b gilt //Wenn a länger ist als b ist a > b if(a_max > b_max) return true; //Wenn b länger als ist als a ist b > a bzw. a < b else if(b_max > a_max) return false; /*Da a und b die gleiche Länge haben, werden jeweils zwei Zeichen a[i] und b[i] überprüft, ist a[i] > b[i] ist auch a größer b und es wird true zurückgegeben ist b[i] > a[i] ist b auch größer als a und es wird false zurückgegeben*/ for(unsigned long long i = 0; i < a_max; i++) if(a[i] > b[i]) return true; else if(b[i] > a[i]) return false; //Es stimmen alle Zeichen überein, also ist a = b und somit a >= b return true; } bool Int::positiv_sub(char *a, char *b, unsigned long long& a_max, unsigned long long& b_max) { //Die Funktion überprüft ob a >= b gilt, und rechnet wenn dies gilt a-= b aus. Es wird a >= b zurückgegeben, //also ob die Subtraktion moeglich war //Wenn b größer ist, ist keine Subtraktion möglich if(!compare_size(a, b, a_max, b_max)) return false; //a_pos ist die aktuelle Position für die Subtraktion in a, b_pos die aktuelle Position in b //val ist die Ziffer die dann im Ergebnis an der Position j steht long long a_pos = a_max - 1, b_pos = b_max - 1, val = 0, uebertrag = 0; for(int j = a_max - 1; j >= 0; j--) { val = -uebertrag; uebertrag = 0; if(b_pos >= 0 && a_pos >= 0) { //Wenn die untere Ziffer kleiner als die obere Ziffer ist if(b[b_pos] <= a[a_pos]) { val += (a[a_pos] - 48); val -= b[b_pos] - 48; } //Wenn die untere Ziffer größer als die obere Ziffer ist else if(b[b_pos] > a[a_pos]) { val += 10 + a[a_pos] - b[b_pos]; uebertrag = 1; } } if(b_pos >= 0 && a_pos < 0) { val += b[b_pos] - 48; uebertrag = 1; } else if(a_pos >= 0 && b_pos < 0) { val += a[a_pos] - 48; } a[j] = val + 48; a_pos--; b_pos--; } //Überflüssige Nullen in a am Anfang entfernen check(a, a_max); return true; } Int Int::operator/=(const Int& a) { //Wenn a falsch initialisiert wurde, oder a größer als this ist, oder a = 0, dann wird abgebrochen if(badformat || a.badformat || operator<(a) || a[0] == 0) return Int(0); unsigned long long divisor_max = 0; char *divisor; //Wenn das erste Zeichen von this größer ist, als das erste Zeichen von a if(operator[](0) < a[0]) { divisor_max = max - 1; divisor = new char[divisor_max]; //divisor übernimmt alle Zeichen von a for(long long m = 0; m < a.max; m++) divisor[m] = a[m] + 48; //Es werden solange Nullen angefügt, wie divisor <= *this gilt for(long long m = a.max; m < divisor_max; m++) divisor[m] = 48; } else if(operator[](0 )>= a[0] ) { divisor_max = max; divisor = new char[divisor_max]; //divisor übernimmt alle Zeichen von a for(long long m = 0; m < a.max; m++) divisor[m] = a[m] +48; //Es werden solange Nullen angefügt, wie divisor <= *this gilt for(long long m = a.max; m < divisor_max; m++) divisor[m] = 48; } unsigned long long dividend_max = max; char * dividend = new char[dividend_max]; //dividend übernimmt alle Ziffern von *this for(long long m = 0; m < dividend_max; m++) dividend[m] = operator[](m) + 48; //Das ergebnis kann maximal max + 1 - a.max Stellen haben char * ergebnis = new char[max - a.max + 1]; long long temp = divisor_max; unsigned long long anzahl_ziffern = 0; //divisor_max - a.max ist die Anzahl der angefügten Nullen, solange die >= 0 ist wird die Schleife ausgeführt for(long long i = divisor_max - a.max; i >= 0; i--) { unsigned long long anzahl = 0; while(true) { //Die Schleife wird solange ausgefüht, wie dividend -= divisor >= 0 ist if(!positiv_sub(dividend, divisor, dividend_max, divisor_max)) break; anzahl++; } //Die letzte Null aus Divisor entfernen char *tmp = new char[--divisor_max]; for(long long m = 0; m < divisor_max; m++) tmp[m] = divisor[m]; delete divisor; divisor = new char[divisor_max]; for(long long m = 0; m < divisor_max; m++) divisor[m] = tmp[m]; //Das Ergebnis an der Stelle anzahl_ziffern ist die Anzahl, wie oft //die Subtraktion durchgeführt werden konnte ergebnis[anzahl_ziffern++] = anzahl + 48; } //das interne Array zum Speichern der Ziffern wird gelöscht, ihm wird ergebnis zugewiesen delete z; z = new char[anzahl_ziffern]; for(unsigned long long i = 0; i < anzahl_ziffern; i++) z[i] = ergebnis[i]; if(vorzeichen != a.vorzeichen) vorzeichen = '-'; else vorzeichen = '+'; return *this; }
Kann man das noch irgendwo optimieren oder verbessern, ich bin dankbar für jeden Ratschlag:thumb:
Jetzt mitmachen!
Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!