unbegrenzter Integer, multiplizieren

Argus Magnus

Ich möchte eine Klasse schreiben, die (praktisch) unbegrenzt grosse Ganzzahlen speichern und mit ihnen rechnen kann. Ich bin noch etwas am rumprobieren und weiss nicht wirklich wie ich das ganze anstellen soll..
Mein Ansatz: Ich unterteile die Zahl in Int32 mit max 5 ziffern. Aus einer Zahl mit 15 Ziffern mache ich also ein Array von Int32 mit 3 Elementen, von denen jedes Element fünf Ziffern fasst..:
123456789123456 =
i[0] = 23456
i[1] = 67891
i[2] = 12345
(Ich hoffe das ist einigermassen verständlich)
Addieren und Subtrahieren klappt schon gut, allerdings weiss ich nicht wirklich wie ich das mit dem multiplizieren und erst recht das dividieren angehen soll.
Ich wäre sehr froh um Ideen, Anregungen und auch um (konstruktive) Kritik zu meinem Ansatz.

mfg

p.s. ich nehme an, solche Klassen gibt es bereits. Ich möchte dass aber bewusst selber machen.. Codebeispiele oder Ideen hab ich leider noch keine gefunden

hallo,

es ist am besten, wenn eine ziffer genau so viele werte einnehmen kann wie ein int. multiplizieren tust du so wie du's in der grundschule gelernt hast, nur eben nicht mit 0...9-ziffern sondern mit 0...INT_MAX.
danach kannst du einen richtigen multiplikationsalgorithmus implementieren und ihn mit deiner version (geschwindigkeit, korrektheit) vergleichen:
http://en.wikipedia.org/wiki/Toom–Cook_multiplication
http://en.wikipedia.org/wiki/Multiplication_algorithm

volkard

boofoo schrieb:

es ist am besten, wenn eine ziffer genau so viele werte einnehmen kann wie ein int.

Nee, 5 Stellen ist schon gut hier.
Damit passen Zwischenergebnisse noch in einen int. Und die Ausgabe kann dezimal erfolgen.
Alle so entwickelten Algos lassen sich dann leicht auf 0...SHORT_MAX umstellen (Zwischenergebnis paßt noch in den int) oder 0...INT_MAX (Zwischenergebnis paßt noch in EDX:EAX, braucht halt eine Zeile inline-asm).

multiplizieren tust du so wie du's in der grundschule gelernt hast, nur eben nicht mit 0...9-ziffern sondern mit 0...INT_MAX.

Yup. Das macht er ja schon bei Addieren und Subtrahieren. Nur ist das Plutimizieren auch nach der Grundschulmethode gar nicht so einfach.
Vielleicht ist die amerikanische Methode eine Überlegung wert.
Ich persönlich würde die Ziffernanzahl eine Zweierpotenz sein lassen und mich durch den Karatuba quälen, egal, wie lange es dauert.

Argus Magnus

danke für die antworten, das multiplizieren klappt jetzt vorerst auch (auch wenn noch grosses Optimierungspotential vorhanden ist)
Was mir jetzt aber richtiges Kopfzerbrechen beschert, ist das dividieren. Das Problem ist, dass man den Divisor ja nicht einfach zerlegen darf:
a/(b+c) ≠ a/b + a/c
Wenn ich aber aber durch einen sehr grossen Integer dividieren will, muss ich den Divisor irgendwie zerlegen können..

::edit::
Ich korrigiere mich: ist um einiges einfacher als ich dachte.. frage mich wieso ich da nicht selbst drauf gekommen bin..:
http://www.wer-weiss-was.de/theme9/article3230341.html

Christoph

Argus Magnus schrieb:

danke für die antworten, das multiplizieren klappt jetzt vorerst auch (auch wenn noch grosses Optimierungspotential vorhanden ist)
Was mir jetzt aber richtiges Kopfzerbrechen beschert, ist das dividieren. Das Problem ist, dass man den Divisor ja nicht einfach zerlegen darf:
a/(b+c) ≠ a/b + a/c
Wenn ich aber aber durch einen sehr grossen Integer dividieren will, muss ich den Divisor irgendwie zerlegen können..

::edit::
Ich korrigiere mich: ist um einiges einfacher als ich dachte.. frage mich wieso ich da nicht selbst drauf gekommen bin..:
http://www.wer-weiss-was.de/theme9/article3230341.html

Dieses Verfahren funktioniert bei a/b nur gut, wenn a und b ungefähr gleich groß sind, also a/b relativ klein ist. Eine Division wie 20000000000000000000000000 / 2 durch wiederholtes Subtrahieren auszurechnen, dauert möglicherweise etwas länger.

Auswendig kenn ich einen passenden Algorithmus leider auch nicht, aber ich kann dich verweisen auf D. Knuth, "The Art of Computer Programming", "Volume 2, Seminumerical Algorithms". Dort ist ein Algorithmus beschrieben, mit dem man a/b gut ausrechnen kann, wenn a und b beliebig groß sind. Dieses Buch wirst du in praktisch jeder Uni-Bibliothek finden. Es kann auf keinen Fall schaden, mal in dieses Buch reinzulesen, aber möglicherweise ist es für deinen Zweck overkill, je nachdem, wie effizient deine Big-Integer-Klasse werden soll.

Weniger overkill, aber schlauer als die Subtraktionsmethode: Einfach die Division genau wie in der Grundschule nachmachen! Das sollte mit ein bischen nachdenken möglich sein.

knivil

Ich möchte eine Klasse schreiben, die (praktisch) unbegrenzt grosse Ganzzahlen speichern und mit ihnen rechnen kann.

Nimm doch GMP. Die Bibliothek verwendet glaube http://de.wikipedia.org/wiki/Schönhage-Strassen-Algorithmus .

Mein Ansatz: Ich unterteile die Zahl in Int32 mit max 5 ziffern. Aus einer Zahl mit 15 Ziffern mache ich also ein Array von Int32 mit 3 Elementen, von denen jedes Element fünf Ziffern fasst..:

Das ist nicht schlau. Wandle die Zahl um in die Basis N, wobei N der größtmögliche Int32-Wert plus 1 ist. Dann wird das gleich viel einfacher.

Argus Magnus

und wieso? Sorry, aber ich kann dir nicht folgen..
Wäre es möglich das etwas näher zu erläutern? (Evtl. mit einem kleinen Beispiel )

@Mups:
was meinst du mit "wie in der Grundschule"?
so: http://www.mathematik-wissen.de/schriftliches_dividieren.htm?
Das funktioniert nur so lange, wie der Divisor genügend klein ist.. Und der Divisor lässt sich ja (nach meinem Wissenstand) nicht einfach so aufsplitten..

Nehmen wir mal an, ich will eine Zahl, die zu gross ist, in mehrere Teile zerlegen, also Bignums bauen. Bleiben wir bei kleinen Zahlen, also nehme ich unsigned char als Datentyp. Dann wäre eine zu grosse Zahl zB 345. Mein Typ hat 8 Bits, also ist der grösste Wert + 1 = 2 hoch 8 = 256. Ich baue die Bignums als Array von unsigned char , wobei ich die Zahl als Zahl zur Basis 256 speichere, so dass es sich ergibt, dass es genau 256 Ziffern gibt. Das trifft sich gut, denn so entspricht ein unsigned char einer Ziffer. Weil ich für die Ziffern nicht genügend Zeichen habe, schreibe ich sie in spitze Klammern und als Dezimalzahlen:

Dann ist 345 = 1 * 256 + 89 * 1. In meiner Zahlendarstellung sieht das dann so aus:

<1><89>

Was bedeuten soll:

<1>                 <89>
256er-Stelle        1er-Stelle
(1 mal 256 hoch 1)  (89 mal 256 hoch 0)

Die nächste Stelle hat dann den Wert 256 hoch 2 usw.

In C/C++ wird man statt unsigned char besser unsigned int nehmen, weil's damit schneller geht. Dann ergibt sich als Basis nicht 256 sondern 2 hoch N, wobei N die Anzahl der Bits in einem unsigned int ist. Die Rechenoperationen ergeben sich dann wie von selbst, und zwar so wie in der Grundschule, nur hatten wir dort immer 10 als Basis.

Argus Magnus

das leuchtet ein, werde mich mal damit auseinandersetzen, vielen dank

:: edit ::
Wie stelle ich es dann an, Zahlen im Zehnersystem (z.b. Benutzereingaben) in die Basis 2^n (in meinem Fall 2^32) umzurechnen? Die Methoden die ich kenne, setzen voraus, das man die Zahl im Zehnersystem durch 2^n mit Rest teilen kann, aber gerade für solche Dinge bräuchte ich ja schon eine fertige Klasse die mit so grossen Zahlen umgehen kann..

Keine Ahnung wie man das am schlausten macht. Ist aber wahrscheinlich nicht der Falschenhals typischer Bignum-Anwendungen. Du könntest zB mit Null als Akkumulator (Bignum) anfangen, dann einfach den String von hinten nach vorne durchgehen, die jeweilige dezimale Ziffer holen, mit dem Stellenwert (Bignum) multiplizieren und zum Akkumulator addieren.

volkard

Argus Magnus schrieb:

aber gerade für solche Dinge bräuchte ich ja schon eine fertige Klasse die mit so grossen Zahlen umgehen kann..

Deine Klasse eben. Aber sie braucht dafür nur halbschriftliche Multiplikation mit 10, das ist einfach.