Ganzzahlen Division implementieren
-
Hallo erstmal,
wie der Titel schon sagt möchte ich (oder besser gesagt muss ich) einen Code schreiben, der sehr große Zahlen dividieren kann. Wobei das ganze nur ganzzahlig sein muss. Da ich die Implementation einfach halten wollte wird jede Zahl in ihre Ziffern zerlegt und so abgespeichert. Damit habe ich jetzt alle Grundrechenarten implementieren können, bis auf die Division. Mein bisheriger Ansatz ist einfach solange den Divisor vom Dividend abzuziehen bis dieser kleiner ist als der Divisor. Leider ist dies extrem langsam, wenn das Verhältnis zwischen beiden Werten sehr groß ist. Die schriftliche Division ist auch nicht geeignet, da dort mit Zahlen gerechnet wird und nicht wie bei allen anderen Rechenarten Ziffer für Ziffer.
Ich bräuchte also ein Verfahren wie ich Berechnungen wie [2,7,2] / [1,3] = [2,0] (entspricht 272 / 13 = 20) durchführen könnte nur mit den Ziffern. Ideen habe ich leider keine, so bin ich für jeden Ansatz dankbar.
-
LarumBalum schrieb:
Die schriftliche Division ist auch nicht geeignet, da dort mit Zahlen gerechnet wird und nicht wie bei allen anderen Rechenarten Ziffer für Ziffer.
Ich sehe nicht, inwiefern dich das stören sollte.
-
http://de.wikipedia.org/wiki/Russische_Bauernmultiplikation
http://de.wikipedia.org/wiki/Karatsuba-Algorithmushttp://www-i1.informatik.rwth-aachen.de/~algorithmus/algo16.php
-
SeppJ, danke es geht damit tatsächlich, das habe ich wohl die ganze Zeit übersehen
Knivil, danke der Karatsuba-Algo ist wesentlich schneller als die Schulmethode :).
