dividieren verdammt langer Zahlen

[HW764]

Warum willst du die Unit nicht nehmen?

[atreju2oo0]

Weil er es selber machen will was ja auch Ziel sein sollte...
Also nochmal:

In der 3ten Klasse lernt man den Algorithmus der schriftlichen Division kennen.
Mit diesem kann man BELIEBIG lange Zahlen dividieren.
Falls Du nicht wissen solltest wie der funktioniert einfach mal ins Mathebuch oder bei Google schauen.
Das ist auf jeden Fall der einfachste Weg und es gibt keine Sonderfälle ausser Periodizität,
die aber einfach zu überprüfen ist!

[gmarts]

Klick hier.

Hab zwar etwas Schelte bekommen für die ungünstige Variante mit Strings und für das Nichtbenutzen von Assembler, aber es funktioniert.

MfG
GM

[negaH]

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.

[negaH]

Und weil du so andeutest das du die 4 Grundrechenarten selber proggen willst, und mit großen Primzahlen arbeiten willst. Die fehlt dann nämlich eine ganz entscheidende Operation: die modulare Inversion, InvMod, X = Y^-1 mod Z. Diese Operation wirst du 100%tig bei großen Primzahlen, bzw. deren Berechnung benötigen, denn nur mit dieser Funktion ist es möglich zwei Zahlen in einem Modularen Ring zu dividieren. Im Grunde nichts anderes als eine Reziprokale Division aber in modularen Ringen. Nun, die Inversion wird durch den Erweiterten GCD berechnet. Auch dafür gibts spezielle Algos, zb. den von Euklid. den Binäre GCD oder den nach Lehmer/Sorenson die auch mit Initalapproximationen arbeiten.

Gruß hagen

[Patrick]

Ersteinmal Danke an alle, ich schaue mir das ganze nochmal genauer an und werde versuches es zu versehen und hoffentlich zu einer Lösung kommen...

Die Lösung aus der dritten Klasse kann ich nicht anwenden, sie ist unzureichend, sie funktioniert nur bei Teilern, die in einen Delphi Datentyp passen...

Noch bin ich guter Hoffnung