Wie Funktioniert Decimal.Divide?

[Dax]

Hi Leute

Die Frage steht schon oben im Titel: Wie funktioniert die Decimal.Divide-Methode? Soweit ich informiert bin besteht der Decimal-Typ zum größten Teil aus einem int[3]-Array.. Ich will mir einen eigenen Typ in der Art bauen, weils das DEC-Math ja auf .NET nicht gibt, und was mir noch fehlt, wär eben der Divisionsalgorithmus...

Weiß jemand Rat?

Danke

[Khabarakh]

Das habe ich mich auch schon gefragt .

[MathiasSimmack]

Dax, willst du jetzt wissen, wie diese Divide-Funktion intern arbeitet, oder wie man sie anwendet?
Und, Khabarakh, war das auch wirklich deine Frage?

[Dax]

Mathias Also wirklich. Ich will wissen, wie das Ding arbeitet, weil sich die MS-Assemblies leider asl ILDAsm-resitent erweisen. Warum eigentlich? Das will ich bei meinen auch mache können

[MathiasSimmack]

Code:

public static decimal Divide(decimal d1, decimal d2)
{
      decimal num1 = new decimal(0);
      decimal.FCallDivide(ref num1, d1, d2);
      return num1;
}

Ab da kann ich es im Moment nicht mehr weiter verfolgen, weil:

Code:

[MethodImpl(MethodImplOptions.InternalCall)]
private static extern void FCallDivide(ref decimal result, decimal d1, decimal d2);

[Dax]

*grummel* Irgendeinen Algorithmus muss dieses FCallDevide ja anwenden, aber irgendwie.. hab schon in der DP gesucht, bei Wikipedia, Informatiklehrer gefragt.. wusste wohl niemand.

Hagen?

[MathiasSimmack]

Mich würde interessieren, woher die "FCallDivide"-Funktion eigentlich kommt.

[Khabarakh]

Ähm ja, das war ein etwas zu kurzer Post .
Also, ich habe mich schon oft gefragt, wie solche mathematischen Funktionen von selbst erstellten Typen funktionieren und aussehen. Von der NInts-Unit ist ja nur die .dcu enthalten, aber ob mir der Quellcode so viel sagen würde .

[negaH]

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

[Dax]

Hmm.. hört sich alles ziemlich kompliziert an

Aber das eiigentlich ist ja: Ich würde gern mal wissen, wie man mit einem sturen array of Integer als X und Y eine Division X/Y durchführen kann. Muss ja nicht schnell sein, ich würds gern mal wissen und verstehen