Es gibt ganz verschiedene Divisions Algorithmen:
- binär durch einfache Shift Operationen
- Multiplikation mit dem Reziprokal sprich X = Y * 1/R, wobei man das Reziproke 1/R durch eine Newton Iteration berechnet, lohnt nur bei wiederholter Division mit dem gleichem Reziproken
- basierend auf der Fast Fourier Transformation
- die Schoolboy Methode
- die Division mit Hilfe der Newton Iteration
- die modulare Division nach Montgomery
- die normale Methode nach Donald E. Knuth, dabei wird TopDown eine Aproximation benutzt und der Fehler durch Multiplikationen ausgeglichen
- die schnelle rekursive Karatsuba Division nach Christoph Burnikel & Joachim Ziegler vom Max Planck Institut, sie basiert auf der Idee die bei der Karatsuba Multiplikation angewendet wird -> Teile und Herrsche, Divide and Conquer
Essentiell benötigt man bei sehr großen Zahlen als erstes eine schnelle Multiplikation, danach kann man auch schnelle Divisionen implementieren. Die Division kann minimal 2 mal so lange dauern wie eine Multiplikation, schneller geht nicht.
Für eine schnelle Multiplikation gibt es:
- Schoolboy Methode, so wie du auf dem Papier rechnest nur mit dem Unterschied das man nicht dezimal rechnet sondern zb. zu Basis 2^32.
- COMBA Methode
- TOOM COOK Methode
- Karatsuba Methode
- Fast Fourier Methode -> Nußbaumer FFT, Zahlentheoretische FFT und Modulare Fermat FFT nach Schönhage und Strassen
ohne Assembler wirst du es aber nie schnell hinbekommen.
Alle oben angesprochenen Miltiplikations Methoden sind im
DEC implementiert. Nur bei den FFT's habe ich nur die modulare Fermat FFT nach Schönhage& Strassen genommen. Diese ist asympthotisch die schnellst Art und Weise zwei Zahlen zu multiplizieren, allerdings ist sie auch ziemlich kompliziert.
Bei der Division enthält das
DEC die Methoden nach D.E. Knuth für kleine Zahlen und die rekursive Karatsuba Division nach Burnickel & Ziegler. Desweiteren noch den Montomergy Trick um schnelle modulare Division durchzuführen. Die Kombination aus diesen drei Verfahren ist die nach meiner Kenntnis schnellste heutzutage machbare Implemntierung auf normalen 32Bit CISCs/ASICs/RISCs.
Die Multiplikation benutzt im
DEC die Schoolboy, COMAB, TOOM-COOK-3, Karatsuba und Schönhage FFT. Also im Grunde fünf verschiedene Verfahren sind implementiert. Teile der Division, zb. die anch Burnickel&Ziegler benötigen eine schnelle Multiplikation.
Man wählt je nach Größe der zu multiplizierenden/dividierenden Zahlen dynamisch den entsprechenden Algorithmus aus.
Insgesamt habe ich über einen Zeitraum von drei Jahren alle nötigen mathematischen und technischen Dokumente zusammengesucht und immer mehr meine Implementierungen ausgebaut und verbessert. Es ist also keine triviale Sache und man muß schon ziemlich viel Zeit investieren. Zudem muß ich noch dazu sagen das ca. 80% des kompletten Sources für Multiplikationen und Divisionen in purem handmade Assembler gecodet ist. Dabei wurde auch im speziellen der MMX/SSE2 Befehlssatz neuerer Intel-CPU's benutzt. Du benötigst also ziemlich viel Wissen drumherum.
Hoffe das dir dieser Abriß einen kurzen Überblick verschafft hat.
Gruß Hagen