Gibt es ein Dokument, in dem genau angegeben ist, für welchen Zahlenbereich .NET BigInteger ausgelegt sind?

12

Ich spiele mit der .NET BigInteger herum und frage mich im Grunde, welche Zahl - eine geschätzte Antwort wäre in Ordnung - der Punkt der Abweichung der Kurve von (der Graph von (für Operationen erforderliche Zeitzunahme ) vs (Wert von BigInteger))?

oder sind sie so konstruiert, dass sie eine glatte Kurve haben, wenn wir den Anstieg der für Operationen benötigten Zeit gegen den Wert von BigInteger von 1 bis unendlich zeichnen?

Angenommen, Arrays sind für die Verarbeitung von 50 Elementen ausgelegt. Dies bedeutet, dass, wenn ich 1 Element habe, Operationen f (1) Zeit sind. und wenn ich 2 Einzelteile habe, sind Operationen f (2) Zeit. Wenn ich 50 Elemente habe, sind Operationen f (50) Zeit. Da es jedoch nur für die Verarbeitung von 50 Elementen ausgelegt ist, sind die Operationen, die ausgeführt werden, wenn 51 Elemente vorliegen, g (51), wobei g (51)> f (51).

Bei richtiger Implementierung sollte die Komplexität der BigInteger-Arithmetik eine glatte Kurve sein. Zum Beispiel sollte die zeitliche Komplexität der Multiplikation O (NM) sein, wobei N die Anzahl der Stellen im ersten Multiplikanden und M die Anzahl der Stellen im zweiten Multiplikanden ist. Natürlich gibt es praktische Grenzen, in denen Sie N und M so groß wählen können, dass die Zahlen nicht in Ihre Maschine passen.

Gibt es / kennt jemand Dokumente, die behaupten, dass sie als solche implementiert sind?

Pacerier
quelle
3
@Down-Wähler, Down-Stimmen bedeuten nichts, wenn Sie keinen Kommentar hinterlassen können, der erklärt, warum die Frage keine gute Frage ist. Ich habe dem zugestimmt, da ich keine Probleme damit sehe.
The Muffin Man
Ich habe nicht abgelehnt, aber ich bin nicht sicher, was die Frage hier ist. Möchten Sie die Laufzeit- / Speicherkomplexität von Operationen auf Bigints (Addition, Multiplikation, Division usw.) kennen?
Nikie
Angenommen, Arrays sind für die Verarbeitung von 50 Elementen ausgelegt. Dies bedeutet, dass, wenn ich 1 Element habe und Operationen f (1) Zeit sind. und wenn ich 2 Einzelteile habe, sind Operationen f (2) Zeit. wenn ich 50 Einzelteile habe, sind Operationen f (50) Zeit. Da es jedoch nur für die Verarbeitung von 50 Elementen ausgelegt ist, werden bei 51 Elementen folgende Vorgänge ausgeführt: g (51) wobei g (51)> f (51)
Pacerier
@ Charles E. Grant ja! das ist worüber ich spreche. Frage: Gibt es irgendwelche / kennt jemand Dokumente, die behaupten, dass sie als solche implementiert sind?
Pacerier
@Paceier Ich habe meinen Kommentar in meine Antwort verschoben und einen Link zu einem Dokument hinzugefügt, in dem genau das besprochen wird.
Charles E. Grant

Antworten:

7

Jede Zahl, die möglicherweise größer als ULong.MaxValue oder kleiner als Long.MinValue sein kann, sollte mit BigInteger dargestellt werden.

Wenn NICHT (Long.MinValue <= X <= ULong.MaxValue), dann BigInteger

BigInteger ist für zu große Zahlen, als dass normale Primitive damit umgehen können.

Wenn Ihre Ganzzahl beispielsweise außerhalb des Bereichs von Long liegt, sollten Sie wahrscheinlich BigInteger verwenden. Diese Fälle sind jedoch sehr selten und bei Verwendung dieser Klassen ist der Overhead erheblich höher als bei Verwendung ihrer primitiven Gegenstücke.

longIst beispielsweise 64 Bit breit und kann den Bereich von -9.223.372.036.854.775.808 bis 9.223.372.036.854.775.80 enthalten. ulong kann 0 bis 18.446.744.073.709.551.615 halten. Wenn Ihre Zahlen größer oder kleiner sind, ist BigInteger Ihre einzige Option

Das einzige Mal, dass ich sie in einer realen Anwendung gesehen habe, war eine Starchartting-Anwendung.

Siehe auch: Primitive Bereiche in .NET

Malfist
quelle
Ich meine natürlich, ich weiß, wir sollten normale Primitive verwenden, wann immer wir können. Ich meine, wie sagen wir, ist BigInteger für Zahlen ausgelegt, die 100-mal größer als ULong.MaxValue sind, oder ist BigInteger für Zahlen ausgelegt, die 100-mal größer als ULong.MaxValue sind? Ich meine, ich weiß, dass es 100k-mal größer als ULong.MaxValue unterstützen kann, aber wurde es mit Blick auf diesen Bereich entwickelt, oder wurde es mit diesem als "außergewöhnliche Anforderung" deklarierten Bereich entwickelt?
Pacerier
5
Sie können keine Zahl darstellen, die sogar eine Nummer größer als ULong.MaxValue ist, ohne BigInteger zu verwenden. Jede Zahl, die möglicherweise größer als ULong.MaxValue sein könnte, sollte eine BigInteger sein.
Malfist
Natürlich gibt es Möglichkeiten, Zahlen darzustellen, die größer als ULong.MaxValue sind, ohne BigInteger zu verwenden. Ich könnte einfach eine benutzerdefinierte Struktur schreiben, die aus einem ULong und einem Boolean und einer Bratsche besteht, die ich bis zu zweimal für ULong.MaxValue
Pacerier
Ja, aber die Verwendung von BigInteger ist weitaus unkomplizierter, und es wäre wahrscheinlich nicht viel schneller, wenn überhaupt, und es wäre nicht so flexibel wie BigInteger. Sie könnten auch sehr große Zahlen mit einer Reihe von Booleschen Werten darstellen, aber das ist einfach zu kompliziert.
Malfist
2
@Mavrik, er hat dies in eine ganz andere Frage geändert als die, die ich beantwortet habe.
Malfist
4

In gewissem Sinne ist der Punkt von BigInteger nicht so sehr die absolute Größe, sondern die unbegrenzte Präzision. Gleitkommazahlen können ebenfalls sehr groß sein, haben jedoch eine begrenzte Genauigkeit. Mit BigInteger können Sie Arithmetik ausführen, ohne Rundungsfehler oder Überlauf befürchten zu müssen. Der Preis, den Sie zahlen, ist, dass es hunderte Male langsamer ist als Arithmetik mit gewöhnlichen Ganzzahlen oder Gleitkommazahlen.

Wie bereits erwähnt, kann ulong zwischen 0 und 18.446.744.073.709.551.615 liegen. Solange Sie in diesem Bereich bleiben, können Sie exakte Berechnungen durchführen. Wenn Sie sogar 1 über diesen Bereich hinausgehen, kommt es zu einem Überlauf. Daher lautet die Antwort auf Ihre Frage "BigInteger", wenn Sie eine exakte Arithmetik benötigen und die Wahrscheinlichkeit besteht, dass ein Zwischenergebnis 18.446.744.073.709.551.615 überschreitet.

Die meisten Probleme in Wissenschaft, Technik und Finanzen können mit den durch Gleitkommazahlen erzwungenen Näherungen leben und können sich die Zeitkosten der BigInteger-Arithmetik nicht leisten. Die meisten kommerziellen Berechnungen können nicht mit den Näherungen der Gleitkomma-Arithmetik leben, sondern arbeiten im Bereich von 0 bis 18.446.744.073.709.551.615, sodass sie normale Arithmetik verwenden können. BigInteger wird benötigt, wenn Algorithmen aus der Zahlentheorie verwendet werden, die Dinge wie Kryptographie beinhalten (man denke an 50-stellige Primzahlen). Es wird auch manchmal in kommerziellen Anwendungen verwendet, wenn exakte Berechnungen erforderlich sind, die Geschwindigkeit nicht zu wichtig ist und die Einrichtung eines geeigneten Festkommasystems zu schwierig ist.

Bei richtiger Implementierung sollte die Komplexität der BigInteger-Arithmetik eine glatte Kurve sein. Zum Beispiel sollte die zeitliche Komplexität der Multiplikation O (NM) sein, wobei N die Anzahl der Stellen im ersten Multiplikanden und M die Anzahl der Stellen im zweiten Multiplikanden ist. Natürlich gibt es praktische Grenzen, in denen Sie N und M so groß wählen können, dass die Zahlen nicht in Ihre Maschine passen.

Wenn Sie "Computing Complexity of Biginteger" googeln, erhalten Sie mehr Referenzen, als Sie sich vorstellen können. Eine, die direkt zu Ihrer Frage spricht, ist die folgende: Vergleich zweier Arithmetikpakete mit willkürlicher Genauigkeit .

Charles E. Grant
quelle
4

Speicherlimit

BigInteger ist für die Speicherung auf das Array int angewiesen. Angenommen, die theoretische Grenze für die maximale Anzahl, die BigInteger darstellen kann, kann aus der in .net verfügbaren maximalen Array-Größe abgeleitet werden. Hier gibt es ein SO-Thema zu Arrays: Ermitteln, wie viel Speicher ich einem Array in C # zuweisen kann .

Unter der Annahme, dass wir die maximale Arraygröße kennen, können wir die maximale Anzahl schätzen, die BigInteger darstellen kann: (2 ^ 32) ^ max_array_size, wobei:

  • 2 ^ 32 - maximale Anzahl in Array-Zelle (int)
  • max_array_size - Maximal zulässige Größe des int-Arrays, die durch die Objektgröße von 2 GB begrenzt ist

Dies ergibt eine Zahl mit 600 Millionen Dezimalstellen.

Leistungslimit

Für die Performance verwendet BigInteger den Karatsuba-Algorithmus zur Multiplikation und den linearen Algorithmus zum Addieren. Die Multiplikationskomplexität ist 3 * n ^ 1,585, das bedeutet, dass sie auch für große Zahlen ziemlich gut skaliert werden kann ( Komplexitätsdiagramm ). Je nach RAM-Größe und Prozessor-Cache kann es jedoch zu Leistungseinbußen kommen.

Solange die maximale Anzahl auf 2 GB begrenzt ist, werden Sie auf Abstiegsmaschinen keine unerwartete Leistungslücke sehen, aber wenn Sie weiterhin mit 600 Millionen Ziffern arbeiten, werden Sie sehr langsam sein.

Valera Kolupaev
quelle
Dies ist eine wundervolle Information, aber wo ist Ihre Quelle, auf die sich BigInteger bei Int Arrays stützt?
Pacerier
Ich habe mich gerade mit dotPeek mit .net-Quellen beschäftigt. Es scheint, dass die Zahl selbst in uint [] _data der BigInteger-Struktur gespeichert ist.
Valera Kolupaev
* Mit ausführlicherer Antwort aktualisiert, kann ich jedoch keinen .net-Quellcode finden, auf den ich verweisen kann, mit Ausnahme dekompilierter Snippets.
Valera Kolupaev
Es scheint mir, dass es in .NET einen Standard-Multiplikationsalgorithmus gibt, wie er aus ILSpy hervorgeht: .NET BigInteger Multiplication
Ivan Kochurkin
1

Die Grenze ist Ihre Speichergröße (und die Zeit, die Sie haben). Sie können also wirklich große Zahlen haben. Wie Kevin sagte, muss man in der Kryptographie Zahlen mit einigen tausend (binären) Ziffern multiplizieren oder potenzieren, und dies ist problemlos möglich.

Natürlich werden die Algorithmen oft langsamer, wenn die Zahlen größer werden, aber nicht so viel langsamer.

Wenn Sie Zahlen im Mega-Ziffern-Bereich verwenden, möchten Sie vielleicht auch über andere Lösungen nachdenken - da das Rechnen mit ihnen auch sehr langsam wird.

Paŭlo Ebermann
quelle
0

Innerhalb der wissenschaftlichen Gemeinschaft gibt es einige Verwendungszwecke (z. B. den Abstand zwischen Galaxien, die Anzahl der Atome in einem Grasfeld usw.).

Dave Wise
quelle
uh nicht unhöflich zu sein .. aber wie bezieht sich diese Antwort auf die Frage?
Pacerier
2
Die Frage, wie geschrieben, klingt so, als ob er nach einem realen Beispiel dafür gesucht hätte, warum ein solcher Datentyp erstellt werden müsste.
Dave Wise
Eine bessere Formulierung wäre "Ist BigInteger wirklich für Zahlen bis 10 ^ 30 geeignet?".
Pacerier
Dafür würde ich besser verwenden doubleoder float- Sie haben sowieso nicht die notwendige Präzision.
Paŭlo Ebermann
Eine bessere Formulierung wäre "Ist BigInteger wirklich für Zahlen bis 10 ^ 30 geeignet, wenn wir die Genauigkeit benötigen"?
Pacerier
0

Wie aus der Antwort von Kevin Cline hervorgeht, wurden BigNumbers in erster Linie zu den .NET-Bibliotheken hinzugefügt, da sie als Baustein für viele moderne kryptografische Algorithmen (digitale Signaturen, Verschlüsselung mit öffentlichen / privaten Schlüsseln usw.) benötigt wurden. Bei vielen modernen kryptografischen Algorithmen werden ganzzahlige Werte mit einer Größe von bis zu mehreren tausend Bit berechnet. Da die BigNumber-Klasse eine gut definierte und nützliche Klasse beschreibt, haben sie beschlossen, sie öffentlich zu machen (anstatt sie als internes Detail der kryptografischen APIs zu behalten).

Stephen C. Steel
quelle
Übrigens: Woher wissen Sie, dass BigNumbers in erster Linie zu den .NET-Bibliotheken hinzugefügt wurden, weil sie als Baustein für viele moderne kryptografische Algorithmen benötigt wurden (und daher Werte bis zu mehreren tausend Bit unterstützen sollten)?
Pacerier