dividieren verdammt langer Zahlen

[Patrick]

Tach,

Also ich weis nicht, ob ihr mir helfen könnt, wahrscheinlich ist mir nicht mehr zu helfen, aber ich probiers mal..

Eines meiner neusten Projekte beschäftigt sich mit dem Berechnen sehr großer Zahlen. Die Delphi Datentypen sind längst nicht ausreichend. Also habe ich mir da was gebastelt...

Mein Datentyp sieht so aus:

Delphi-Quellcode:

type 
TZahl = record
  Zahl : array of shortint;
  Lange, Komma : longint;
  Negativ : boolean;
end;

Wenn ich nun etwas verarbeite, z.B. Addiere, dann mache ich das Zahl für Zahl (also in jedem Element meines Arrays steht nur eine Ziffer). Das ganze funktioniert mir Addieren und Subtrahieren perfekt, Multiplizieren war auch nicht schwer. Aber wie zum Teufel soll das mit Dividieren gehen???

Mathematisch geht das glaube ich garnicht, oder???

[Dax]

Hagens DEC-Math. Kann verdammt lange Zahlen vererbeiten.

Unendlich viele Nachkommastellen

Oder direkter Link zum Thread: Thread

[glkgereon]

überleg, überleg.... hmm

du könntest es so machen:

(entwurf von 1 minute überlegung..)

Delphi-Quellcode:

for i:=1 to length(Zahl.zahl) do
  begin
  if Zahl.Zahl[i] mod zuDividieren <> 0  //wenns nicht aufgeht
  then Zahl.Zahl[i+1]:=Zahl.Zahl[i+1]+Zahl.zahl[i] mod zuDividieren; //dann wird der rest zur ziffer drunter dazugetan
  Zahl.Zahl[i]:=Zahl.Zahl[i] Div zuDividieren;
  end;

allerdings kann es probleme geben wenn du shortiont nutzt, ach nee, is ja bis 256 :wall: :wall:

obwohl, wenn du ne primzahl über 100 teilst dann isses im arsch...

es muss halbwegs aufgehen...

nee, ehrlich, das müsste funzen...

[Dax]

Ich bleibe dabei: Der Weg über Hagens DECMath ist besser, da es für solche Dinge optimiert ist.

[glkgereon]

wo du wahrscheinlich recht hast :-D

aber ich schätze er will sowas ähnliches selber machen

aber er hat gefragt wie er das machen kann, er könnte es aus hagens dingens rauskopieren

:zwinker:

[Patrick]

Ich könnte es kopieren, aber das will ich nicht! Ich habe die ersten drei Rechenarten auf meine Weis programmiert, jetzt will ich das auch mit der Letzten.

Also ich hab mir den Kram vom Hagen mal angesehen...
Ganz Ehrlich: Ich verstehe da nur Bahnhof

@glkbkk
Deine Lösung hinkt ein Wenig.
Was mache ich denn, wenn der Teiler sehr viel größer ist? Sagen wir einfach ich will eine 1000 stellige Zahl durch eine 1000 stellige Zahl teilen.

[atreju2oo0]

Also ich würde einfach die schriftliche Division programmieren...
Das ist für beliebig große Zahlen möglich!
Wahrscheinlich gibt es aber einen effizienteren Weg...

[glkgereon]

Zitat:

Ich könnte es kopieren, aber das will ich nicht! Ich habe die ersten drei Rechenarten auf meine Weis programmiert, jetzt will ich das auch mit der Letzten.

siehste dax, sag ich doch :mrgreen: :mrgreen:

AAALLLSSSOOO, meine lösung:

lass dir was einfallen :mrgreen: :mrgreen:

nee, ma ernsthaft, was werden das für zahlen sein mit denen du das machst?

wenn der größte primfaktor unter 256 liegt (oder was du fürn typ nimmst), dann kannst meine lösung nehmen...

[Patrick]

Stellt euch doch mal vor, der Teiler passt nicht in einen Datentyp...
Daran habe ich doch auch schon gedacht, aber nur so lange, bis ich einen zu großen Teiler hatte.

[glkgereon]

ja dann sag halt

Delphi-Quellcode:

try
  for i:=1 to length(Zahl.zahl) do
  begin
    if Zahl.Zahl[i] mod zuDividieren <> 0  //wenns nicht aufgeht
    then Zahl.Zahl[i+1]:=Zahl.Zahl[i+1]+Zahl.zahl[i] mod zuDividieren; //dann wird der rest zur ziffer drunter dazugetan
    Zahl.Zahl[i]:=Zahl.Zahl[i] Div zuDividieren;
  end;
except
  Application.MessageBox('Zu großer Primfaktor','Es wurden Divisonsoperationen mit einer Zahl durchgeführt, dessen Primfaktoren zu groß sind');
end;

wenns dir so nicht gefällt nimm hagens unit...Mann!

[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 :zwinker: 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. :mrgreen:

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 :wink: