Laden...

Komponente um mit (fast) beliebig großen Zahlen zu rechnen

Erstellt von pdelvo vor 14 Jahren Letzter Beitrag vor 14 Jahren 9.026 Views
pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren
Komponente um mit (fast) beliebig großen Zahlen zu rechnen

Hallo

Ich möchte eine Komponente, die in ca. einem Tag arbeit entstand vorstellen.

Mit dieser ist es möglich die Grundrechenarten(+,-,* und /,) mit Zahlen mit riesigen Zahlen durchzuführen.

Zu der Performance.

Ich habe die Fakultät von 20000 in ca. 14min ausgerechnet. Ich finde das Ergebnis akzeptabel.

Die Klasse unterstützt nur Natürliche Zahlen.

Ich habe auch mal ein Beispielprojekt angehangen.

Gruß pdelvo

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren

Hier noch das Zip File.

Gruß pdelvo

S
401 Beiträge seit 2008
vor 14 Jahren

Servus pdelvo,

wenn es dir "nur" um die Falkultät geht, dann gibt es effizientere Algorithmen. Ich habe vor ein paar Monaten mit einer kleinen Mathematik-Lib. angefangen und hab mir eine Natural-Klasse gebastelt. BigInteger kennt ja jeder 😉

Zur Berechnung der Falk. habe ich ein paar Algorithmen umgesetzt, die

  • ein genaues Ergebniss liefern
  • einen Annährung (obere und untere Grenze), durch double oder Natural, liefern

Wikip. hat mir die Seite empfohlen: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
Und mittels Google stieß ich auf

Mit Java "6u10" kann man z.B. !64.000.000 in ca. 455,0 s berechnen. Intressant ist der Unterschied zu C#. Naja, man darf das nicht zu eng sehen. Ich hoffe, dass ich deinen Ergeiz gewegt habe.
Ähm, laut Benchmark gibt es eine BigInteger umsetzung von MS.
Arithmetic: System.Numeric.BigInteger by Microsoft

Ich persönlich arbeite gerade an einer eigenen Speicherverwaltung in C++, die für derartige Berechnungen den nötigen Speicher bereit hält. Malloc & Co. sind mir zu langsam. Mal schauen, was mit C++ möglich ist 🙂

Gruß,
Thomas

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren

Ich habe mir gerade BigInteger von Microsoft aus dem Framework 4.0 angesehen. Er berrechnet zwar 20000! in ein paar Sekunden. Raus kommt aber nur 1,8192063202303451348276417569E+77337, und nicht die ausgeschriebene Zahl.

Ich konnte die Fakultät mit meinem Programm ohne Probleme ausrechnen(Anhang)

Gruß pdelvo

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren

Ein Update: Ich habe alles ein wenig Beschleunigt und berrechne die Fakultät aus 20000 nun in 8:19.

Gruß pdelvo

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren

Hier ein Beispielprojekt. Ich habe nun auch den Source angehangen. Vieleicht kann mir jemand ein paar Tips geben um noch mehr performance rauszukizeln.

EDIT: Ich habe gerade mal das Projekt unter Release, direkt als 64bit Anwendung und ohne debuggen gestartet. Dann hat 20000! nurnoch 1,31min gedauert.
8)

Gruß pdelvo

S
401 Beiträge seit 2008
vor 14 Jahren

Servus,

schöne Klasse, großes Lob 👍

Aber da hätte ich mal ein paar Fragen 😉

Wieso nimmst du Byte? Wird Byte von der .NET-Plattform besonders gut unterstützt? Ansonsten würde ich eher zu int tendieren. Da die Schleifendurchgänge deutlich reduziert werden. Bei sehr große Zahle wirkt sich das durch aus positiv aus.

In meiner Implementierung habe ich zusätzlich die Anzahl der Bits gespeichert, da diese Information für den Platzbedarf einer Addition, Sub., Multiplikation und Division her halten muss. Zudem ist es schöner mit unsigned zu arbeiten. Die Einführung eines Vorzeichen durch z.B. ein Enum ist viel schöner und man kann z.B. *-1 schnell durchführen 😉

Wie gut ist der C#-Compiler? Ist es nicht besser, Variablen außerhalb der Schleife zu deklarieren. Das entlasstet den GC doch enorm, oder? Macht das der C#-Compiler von MS automatisch?

Zudem würde ich den Konstruktor vereinfachen und einen weiteren Integer einführen, der die genutzte Array-Länge angibt. Ist es in C# möglich, ein Array nachträglich auf die Größe N zu verkleinern, ala realloc in C?
Ansonsten könnte man eine Mehtode normalize() einführen, die derartige Aufgaben ausführt und nicht von der Klasse intern benutzt wird. Sie sollte eher für länger benutzt Objekte interessant sein.

public BigNumber(int datalength)
        {
            data = new byte[datalength];

            //for (int i = 0; i < datalength; i++)
            //{
            //    data[i] = 0;
            //}
            // Kindersicherung entfernt -> n1.data.Length darf nicht benutzt werden!!!!!
            // Ich halte mich in den nächsten Snipptes nicht daran
        }
private static BigNumber Add(BigNumber n1, BigNumber n2)
        {
            byte overflow = 0;
            BigNumber nreturn;

            // n1 >> n2
            if(n1 < n2) {
                nreturn = n1;
                n1 = n2;
                n2 = nreturn;
           }

              // Überflüssig
//            int max = Math.Max(n1.data.Length, n2.data.Length);
//            int min = Math.Min(n1.data.Length, n2.data.Length);

            nreturn = new BigNumber(n1.data.Length + 1); // max. für byte: (n1.bits+1)/8

For-Schleife. Mit

int i=0;

for(; i < n2.data.Length; ++i)
{
// ...
}

for(;i<n1.data.Length; ++i)
{
// Kopiere n1 + overflow
}

if(overflow > 0)
  nresult.data[i++] = overflow;

usedArrayCnt = i;
// Berechne bits & Co.

sparst du dir ein paar if-Abfragen. Was es Geschwindigkeits mäßig bringt? Vielleicht eine Spur mehr Übersicht, aber das ist Ansichtssache 🙂

Wieso rechnest du bei Add in der 10-Basis? Der Rechner benutzt doch Basis 2.

//byte temp = (byte)(n1.data[i] + n2.data[i] + ü);
short temp = ((short) (n1.data[i])) + n2.data[i] + overflow;
short overflow = temp >> 8;

oder

temp = ((short) (n1.data[i])) + n2.data[i] +( temp >> 8);
nresult.data[i] = 0xFF & temp; // muss ich C# (byte) schreiben oder reicht das?

So, mittlerweile ist es spät geworden. Ich hoffe, dass ich keinen Schmarn geschrieben habe und wünsche dir noch viel Erfolg beim verbessern. Tipp, das Mono-Project hat die (zumindestens vor ein paar Jahren) effektivste Umsetzung aus Java und C++ Beispielen erstellt. Leider mit unsafe Anteilen.

Die Multiplikation ist elegant gelösst, wie hoch ist der Aufwand? Hast du dir den Schönhagen-Strasser-Alg. und dem vom Fürer angeschaut? Toom-Cook ist etwas älter, aber sehr oft umgesetzt worden.

Die Division sieht genail aus. Werd ich mir dieses Wochenende vielleicht etwas genauer betrachten. Ist diese Methode effektiver als die DividedByRemainder?

private static BigNumber Div(BigNumber op1, BigNumber op2)
        {
            BigNumber temp = new BigNumber(1);
            BigNumber temp2;

            for (temp2 = 0; temp2 < op1; temp2 = Add(temp2, op2))
            {
                temp = Add(temp, BigNumber.Parse("1"));
            }
            return temp;
        }

Hilfe 😉 BigNumber 0, 1, 2, 8, 10, 16 ; -1 sollten als Konstanten zur Verfügung stehen

Für Pow und Wurzel gibt es spezielle Lösungen für bestimmte Fälle. Was zu sehr vielen Zeilen führt.

Gruß,
Thomas

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo zusammen,

Hinweise zur Verbesserung sind - auch wenn sie detailliert sind - ok. Beachte aber bitte vorsichtshalber diesen Hinweis: Nicht ok, wäre es eine fachliche Diskussion auf diesem Detaillierungsgrad in einem Komponenten-Thread zu führen. Vielen Dank!

herbivore

3.971 Beiträge seit 2006
vor 14 Jahren

Ich habe alles ein wenig Beschleunigt und berrechne die Fakultät aus 20000 nun in 8:19.

Auf einem CPU-Kern? Ist der algorithmus Multi-Core fähig?

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

6.862 Beiträge seit 2003
vor 14 Jahren

Ich habe mir gerade BigInteger von Microsoft aus dem Framework 4.0 angesehen. Er berrechnet zwar 20000! in ein paar Sekunden. Raus kommt aber nur 1,8192063202303451348276417569E+77337, und nicht die ausgeschriebene Zahl.

Ich will dich nicht demotivieren in deinen Optimierungsversuchen, aber gib einfach als Formatstring "R" beim BigInteger.ToString(string format) an und schon bekommst du auch die voll ausgeschriebene Zahl 😃. Standardmäßig gibt BigInteger.ToString nur die 50 ersten Ziffern an, weil bei so großen Zahlen die nachfolgenden meist weniger interessieren, da gehts dann mehr um Größenordnungen statt um konkrete Werte.

Und deine eigene ToString Implementierung solltest auch mal überdenken. Nen StringBuilder statt nur immer Stringadditionen würde auch einiges sparen an Laufzeit bei großen Zahlen.

Baka wa shinanakya naoranai.

Mein XING Profil.

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren

Hallo,

Erstmal danke für deine Ausführliche Antwort.

Wieso nimmst du Byte? Wird Byte von der .NET-Plattform besonders gut unterstützt? Ansonsten würde ich eher zu int tendieren. Da die Schleifendurchgänge deutlich reduziert werden. Bei sehr große Zahle wirkt sich das durch aus positiv aus.

Ich habe byte genommen, da dieser ziemlich klein ist und da er völlig ausreicht. Das mit dem int kann ich mal verswuchen einzubauen. Danke für den hinweiß.

In meiner Implementierung habe ich zusätzlich die Anzahl der Bits gespeichert, da diese Information für den Platzbedarf einer Addition, Sub., Multiplikation und Division her halten muss. Zudem ist es schöner mit unsigned zu arbeiten. Die Einführung eines Vorzeichen durch z.B. ein Enum ist viel schöner und man kann z.B. *-1 schnell durchführen

Das ist eine gute Idee und lässt sich (hoffentlich) leicht umsetzen. Ich schaue mal.

Wie gut ist der C#-Compiler? Ist es nicht besser, Variablen außerhalb der Schleife zu deklarieren. Das entlasstet den GC doch enorm, oder? Macht das der C#-Compiler von MS automatisch?

Ich habe meine Assembly mal durch den Reflektor gejagt und habe gesehen, dass er das nicht optimiert. Werde ich also von Hand machen müssen.

Zudem würde ich den Konstruktor vereinfachen und einen weiteren Integer einführen, der die genutzte Array-Länge angibt. Ist es in C# möglich, ein Array nachträglich auf die Größe N zu verkleinern, ala realloc in C?
Ansonsten könnte man eine Mehtode normalize() einführen, die derartige Aufgaben ausführt und nicht von der Klasse intern benutzt wird. Sie sollte eher für länger benutzt Objekte interessant sein.

Da hast du genau die langsamste stelle gefunden - Der Konstruktor . Ich habe alles immer durch einen Profiler laufen lassen und der hat diese Stelle als Performancekiller enttarnt. Werde ich verbessern.

Ich werde mal gucken, ob ich die Basis umstelle.

Die Multiplikation ist elegant gelösst, wie hoch ist der Aufwand? Hast du dir den Schönhagen-Strasser-Alg. und dem vom Fürer angeschaut? Toom-Cook ist etwas älter, aber sehr oft umgesetzt worden. Ich habe das Verfahren aus der Grundschule 😄 genommen. Das ist erstaunlich schnell. Werde aber mal gucken ob sich das noch weiter beschleunigen lässt.
Die Division sieht genail aus. Werd ich mir dieses Wochenende vielleicht etwas genauer betrachten. Ist diese Methode effektiver als die DividedByRemainder? Die Division ist, ähhh, nur so umgesetzt, dass es überhaupt eine gibt. Sie ist zwar super langsam, funktioniert aber. Da muss ich aber nochmal ran.
BigNumber 0, 1, 2, 8, 10, 16 ; -1 sollten als Konstanten zur Verfügung stehen Jo mache ich.

Nochmal danke für deinen sehr ausführlichen Post.

Auf einem CPU-Kern? Ist der algorithmus Multi-Core fähig? Ich hatte ihn nur auf einem Kern laufen. Das lässt sich aber durch Multithreading um einiges beschleunigen. Das sollte bei der Fakultät sehr einfach gehen.
Ich will dich nicht demotivieren in deinen Optimierungsversuchen, aber gib einfach als Formatstring "R" beim BigInteger.ToString(string format) an und schon bekommst du auch die voll ausgeschriebene Zahl 😃. Standardmäßig gibt BigInteger.ToString nur die 50 ersten Ziffern an, weil bei so großen Zahlen die nachfolgenden meist weniger interessieren, da gehts dann mehr um Größenordnungen statt um konkrete Werte.

Misst. So ein Pech.

Dann ist es halt was für Leute, die noch kein Framework 4.0 haben 😄

Und deine eigene ToString Implementierung solltest auch mal überdenken. Nen StringBuilder statt nur immer Stringadditionen würde auch einiges sparen an Laufzeit bei großen Zahlen. Wird gemacht.

Gruß pdelvo

3.971 Beiträge seit 2006
vor 14 Jahren

Wie gut ist der C#-Compiler? Ist es nicht besser, Variablen außerhalb der Schleife zu deklarieren. Das entlasstet den GC doch enorm, oder? Macht das der C#-Compiler von MS automatisch? Variablendeklaration in oder vor der Schleife?

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo zusammen,

ich hoffe, das geht im Komponententhread nicht zu weit vom Thema weg...
*Zu System.Numerics.BigInteger:

[...] gib einfach als Formatstring "R" beim BigInteger.ToString(string format) an und schon bekommst du auch die voll ausgeschriebene Zahl Also mit meiner VS2010-CTP geht "R" nicht. Ich habe mal alle Buchstaben des Alphabets als Formatstring probiert, keins gibt mehr als 50 "richtige" Stellen zurück...

*Zu "Komponente um mit (fast) beliebig großen Zahlen zu rechnen": Man kann auch einfach Mono.Math.BigInteger benutzen.

*Zu BigInteger-Implementierungen allgemein: Da ich/wir durch diesen Thread von System.Numerics.BigInteger erfahren haben, gab's heute fast einen richtigen Contest, welche BigInteger-Implementierung am schnellsten ist.
Getestet wurden:

1.Java/java.math.BigInteger/JRE 6.13 1..NET/System.Numerics.BigInteger/MS CLR 4.0 1.Python/long/Active Python 2.6.2.2 1.Squeak/BigInt/Squeak 3.10.2 1..NET/Mono.Math.BigInteger/MS CLR 4.0

Ergebnisse:

   Berechn.  1)         2)       3)       4)        5)
   10.000!      343 ms    137 ms    91 ms  1.200 ms    169 ms
   20.000!    1.480 ms    569 ms   372 ms  1.457 ms    701 ms
   30.000!    3.424 ms  1.243 ms   836 ms  3.360 ms  1.675 ms
   40.000!    6.340 ms  2.101 ms 1.975 ms  6.738 ms  3.042 ms
   50.000!   10.493 ms  3.763 ms 3.658 ms 10.019 ms  5.242 ms
   60.000!   15.586 ms  7.683 ms 5.788 ms 14.241 ms 10.000 ms

Gruß,
dN!3L

6.862 Beiträge seit 2003
vor 14 Jahren

Also mit meiner VS2010-CTP geht "R" nicht. Ich habe mal alle Buchstaben des Alphabets als Formatstring probiert, keins gibt mehr als 50 "richtige" Stellen zurück...

Siehe MSDN Doku zu BigInteger.ToString(). Hab die Beta 1 und da tuts wie in der Doku beschrieben.

Baka wa shinanakya naoranai.

Mein XING Profil.

S
401 Beiträge seit 2008
vor 14 Jahren

Zu "Komponente um mit (fast) beliebig großen Zahlen zu rechnen": Man kann auch einfach Mono.Math.BigInteger benutzen.

Dein Ergebniss sieht die MS-Lösung vor Mono. Liegt dies an der "langsameren" Plattform oder ist die Implementation von MS besser gelungen?

Bringen Zeigeroperationen in C# einen Vorteil oder eher einen Nachteil?

Bei Python war ich erst mal erstaunt. Aber das hat sich sehr schnell gelegt. Im Hintergrund wird wahrscheinlich auf eine C-Library zurück gegriffen und dann relativiert sich das Ganze.

Interessant währe ein zusätzlicher Vergleich zu GmpLib. Eine hoch optimierte freie Bibliothek.

Gruß,
Thomas

pdelvo Themenstarter:in
1.346 Beiträge seit 2008
vor 14 Jahren

Kleines Update. Ich habe aufgrund einer Idee eines Freundes(danke floste) angefangen komplett neu anzufangen und mit einem int zu arbeiten. Ich habe mir vorgenommen zwei Versionen meiner Klasse zu machen, eine für 32 und eine für 64bit Systeme. Da ein 64bit System 64Bits gleichzeitig verarbeiten kann, sollte dort ein long noch schneller sein.

Ich habe mal eben einen mini Performancevergleich gemacht. Ich habe 200000000 mal int.MaxValue + int.MaxValue gerrechnet. Hier die Ergebnisse:

Alte Methode: 00:02:23.1268049
Neue Methode: 00:00:22.3488477

Wie man sieht, habe ich die alte Methode mit mehr als 2min geschlagen. Die nächste Version wird also ein wenig schneller 8)

PS: Und da bei der Multiplikation der Karatsuba-Algorithmus eingesetzt wird, sollte ich da auch noch ein wenig Performance rausholen können.

Gruß pdelvo

2.891 Beiträge seit 2004
vor 14 Jahren

Dein Ergebniss sieht die MS-Lösung vor Mono. Liegt dies an der "langsameren" Plattform oder ist die Implementation von MS besser gelungen?

Die Plattform ist die gleiche (MS CLR 4.0). Nur unterschiedliche Implementierungen: System.Numerics.BigInt von MS und Mono.Math.BigInteger vom Mono-Projekt (Link zum Quelltext siehe oben; Mono-Runtime habe ich nicht verwendet).

Bei Python [...] wird wahrscheinlich auf eine C-Library zurück gegriffen

Genau.

Gruß,
dN!3L