Delphi-PRAXiS - Delphi dividieren verdammt langer Zahlen

Also, was ist 123 / 20 so Pi mal Daumen ??
Was ist 1 / 2 so Pi mal Daumen ??
Das nennt sich Approximation. D.h. du nimmst nur die ersten höchstwertigsten Ziffern beider Zahlen so daß beide im Zahlenbereich zB. von Double liegen. Im obigen Beispiel also die 1 aus 123 und die 2 aus 20. Nun dividierst du 1 / 2 und erhälst 0.5, das liegt Zifferntechnisch schon sehr am Ziel. Denn wir müssten nun das Resulat 0.5 an die Exponenten angleichen. Da jede Ziffer in einer Speicherstelle steht schieben wir also 0.5 um 2 ziffern nach linksund bekommen 50. Da aber die 20 ebenfalls eine zweistellige Zahl ist dürften wir die 0.5 eben nur um 1 Ziffern nach links schieben, es ergibt sich 5. Das liegt für so eine offenstischtliche Annährung = Approximation schon sehr nahe an 6.15. Man stellt sich also vor das man statt 123 / 20 eben 1 * 10^2 / 2 * 10^1 dividiert, man dividiert also 1 / 2 und korregiert mit 10^2/10^1 = 10^(2-1) = 10.

Mit dieser Technik arbeiten fast alle Divisonsroutinen für sehr große Zahlen, selbst die CPU's und deren Microcode arbeiten so. Wie man das Resultat schrittweise so approximiert das zum Schluß exakt 6.15 rauskommt ist eine andere Frage. Da gibt es sehr verschiedene Verfahren und die machen es erst so richtig interessant. Zb. die Newton Iteration, oder eben D.E.Knuths Division oder die Reziprokale Division, sprich Division durch Kehrwertbildung oder aber das absolut Gelbe vom Ei der "Fast Recursive Karatsuba Division" von Burnikel & Ziegler.

Ich empfehle dir unbedingt auf die Suche im WEB nach Donald E. Knuth's Standardwerk "The Art of Computer Programming" zu gehe. Das Kapitel 5 -> "Arithmetik" ist das einzigst gute Kapitel an diesem Buch, und es beschreibt alles was du brauchst. Zum Glück kannst du das als deutsche Übersetzung im Buchladen kaufen. Es haben sich also schon andere die Mühe gemacht das beste Kapitel des Buches zu übersetzen ISBN 3-540-66745-8

Willst du mehr, sprich ganz große Zahlen Dividieren, dann benötigst du als WICHTIGSTES eine schnelle Multiplikation. Hört sich komisch an ist aber wahr. Denn es ist theoretisch erwiesen das eine Division exakt minimal 2 mal solangsam sein wird wie eine Multiplikation. Die Quadierung ist theoretisch 1.5 mal schneller als die Multiplikation. Nun, im DEC habe ich für sehr große Zahlen eben obige "Fast Recursive Karatsuba Division" implementiert. Sie arbeitet mit Multiplikationen, einen Divide&Conquer Verfahren, und nutzt dazu die Fast Fourier Transformation in den Multiplikationen. Dieser Algorithmus ist der einzigste bekannte der an die Schwelle von "2 mal" langsammer rankommt. Alle anderen universellen Divisionsalgorithmen mit großen Zahlen sind bei weitem langsammer. Es gibt Ausnahmen, zB. die Reziprokale Division. 123 / 20 = 123 * (1/20). Das ist aber nur dann effizient wenn man viele Zahlen nacheinander durch 20 dividieren will, denn die Berechnung des Kehrwertes 1/20 dauert eben auch lange.

Dann gäbe es noch die Modularen Divisionen, sprich der "mod" oder "rem" Operator. Bei diesen Divisionen benötig man nicht den Quotienten sondern nur den Remainder=Rest. Da wäre der Montgomery Trick erwähnenswert.

Naja fehlen noch die Divisionen in anderen Zahlendomains, wie zB. in GF(2), Zn, F oder ECgf(p). Diese sind wiederum eine ganz andere Klasse von Algortihmen.

Es ist also noch ein langer weiter Weg für dich ;)

Gruß Hagen

PS: das DEC solltest du dir denoch mal anschauen. Nicht zum abkupfern, da das was du suchst eh nicht als Source veröffentlicht wurde. Eher zur Überprüfung ob deine eigenen Routinen auch richtig rechnen. Ich kann dir aus eigener Erfahrung versichern das das Gold wert ist.