Interne Verarbeitung von großen Zahlen

[noha1981]

Guten Abend allerseits!

Wie im Titel bereits geschrieben, interessiere ich mich für die interne Verarbeitung von großen Zahlen in Python.
In anderen Sprachen ist die Größe der Zahlen durch Datentypen z.B. int begrenzt.
Will man größere Zahlen haben, so kann man diese über floating-point-mechanismen darstellen, dies führt jedoch zu einer Ungenauigkeit aufgrund von Rundungsfehlern.
Da ich jedoch exakte Berechnungen mit natürlichen Zahlen benötige, stellt sich die Frage nach der Genauigkeit.

Hoffe mir kann einer was dazu sagen!

Viele, liebe Grüße,

noha

[MagBen]

Groß genug? Das Stichwort lautet Long Integer, 10! und 20! sind noch normale Integers, aber 30! ist eine Long Integer.

Code: Alles auswählen

>>> import math
>>> math.factorial(10)
3628800
>>> math.factorial(20)
2432902008176640000
>>> math.factorial(30)
265252859812191058636308480000000L
>>> math.factorial(50)
30414093201713378043612608166064768844377641568960512000000000000L
>>> math.factorial(80)
71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000L
>>> math.factorial(1000)
...

[cofi]

Willkommen im Forum und zu Python!

Ich vermisse da jetzt aber eine Frage. Ich rate mal, dass es dir darum geht wie grosse Zahlen in Python gespeichert werden: Python hat bignum Support, man kann mit beliebig[1] grossen Integer Zahlen rechnen.

99 ^ 999? Kein Problem:

Code: Alles auswählen

In [3]: 99 ** 999
Out[3]: 43607320616826516150134170338646201223107986075620608122042152718341096569545917590671870901580903358089476539623429084337462072232323071988487722379025918136755324190771905744346299895101262599307041418954741821869968434014360426644150217367535228232882075278549084725532810757690211467541802733062351872629554887071558565105695677775800388952822060307618460889511910384740346745943545064075415717782672023429351183468901656480345653681279807760503885914267068619022794752754526226771965509515429769648943853393239466825581612114199388796846713698917724135481280269758239887617123242806941909343309827534698631895049620931536029044672739890893731191572695394918757396075233400643214858118180583796749973549192881847496687493228681933883471419305060028239670757748730500105612756664893487357552376496719298602670598130493347017948692042081377598537358748002952547169866050883302508349720700651016938696180158800498316548501175152775533119976607827063817490547330402728524591368881264569985453491886319052131328728570583818564408673363285874627267673252785057700907094407300537042771693320295830608507458585348221347122499594911138477627406334364083621560827029793286395456214852438250303387531773235681535933473521419169488498159152761557826192742496821559991415227170097504961476506200211299335714069542688981875338616104136244975260096287855709071756715604259948711756265446540708637145010756617391517706049935039684935491582597441963211160507086049676500663852688906531131555974645591096814621093225847864090909267239163899350786582783841798570024502259541481335139715410637523456696273629960402393128908813871826086839104466371057841461548132615966946230528245048730192919253049295790150492481440313287274889457554062183833564917170760547521002721621831858497390536681773386602450057910854295098455215379515799387105287701204877340476212991327443730608598868554899539340943577841165431687252557996668355126634828795393392192731183338157723722131288855592435620519974479953860308528414089899L

[1] Solange sie in den Speicher passen.

[noha1981]

Hallo Cofi, hallo MagBen,

vielen lieben Dank erstmal für eure Antworten und für den Willkommensgruß !

Ja, es geht um wirklich große Zahlen, die weder in ein Zahlenbereich von int, noch von long long int passen!
D.h. ich spreche über natürliche Zahlen mit mehreren tausend Stellen die z.B. subtrahiert (a-b) werden, bei denen in anderen Programmiersprachen es entweder zu einer Out-of-Range Exception (C++ und Java z.B.) kommt oder das ganze über den floating point Mechanismus berechnet wird. Letzteres resultierd aber in derben Ungenauigkeiten aufgrund von Rundungsfehlern.

Meine Frage, wie Cofi nochmals aufgenommen hat, ist demnach tatsächlich die interne Verarbeitung, diese nun wohl über BigNum realisiert wird.
Weiter stellst sich aber die Frage ob bigNum von a+b oder a-b bei Zahlen mit z.B. >10000 Stellen noch ein genaues Ergebnis liefert oder ob intern dann auch auf floating point Mechanismen zugegriffen wird?
Wie werden solche großen Zahlen bzw. Berechnungen intern verarbeitet vs. C++ würde aufgeben.

Bin da gerade doch etwas fasziniert...
Zumal sich dann durch Python, sofern es genau rechnet, tolle mathematische Möglichkeiten ergeben würden!

Liebe Grüße
Noha

[cofi]

Nun wie gesagt, bignum ist das Stichwort. Das ganze ist jetzt aber auch nicht gerade exotisch, u.a. gibt es mit GMP schon ewig eine C Library fuer Bignums. Java kennt uebrigens auch Bignums in der Standardbibliothek mit java.math.BigInteger.

[snafu]

Schau dir einfach die Implementierung (für CPython) im Quelltext an:
https://hg.python.org/cpython/file/tip/ ... ngobject.c

Du kannst davon ausgehen, dass Integer-basierte Operationen in Python keinen Abweichungen unterliegen, d.h. dass die Ergebnisse mathematisch genau sind.

[Sirius3]

@noha1981: Bibliotheken zum Rechnen mit großen Zahlen hat eigentlich jede Programmiersprache. In Java heißen die z.B. BigInteger. In Python2 wird halt nur automatisch nach long konvertiert, wenn int nicht mehr reicht, in Python3 gibt es sogar nur einen Typ beliebig genauer Integer.

[snafu]

Nun wie gesagt, bignum ist das Stichwort. Das ganze ist jetzt aber auch nicht gerade exotisch, u.a. gibt es mit GMP schon ewig eine C Library fuer Bignums. Java kennt uebrigens auch Bignums in der Standardbibliothek mit java.math.BigInteger.

Nur natürlich mit dem Unterschied, dass die Handhabung großer Zahlen in Python ziemlich bequem ist, da Operationen mit kleinen Zahlen auf genau die gleiche Weise getätigt werden können wie Operationen mit großen Zahlen. Mit anderen Worten: Wenn ich "a" mit "b" multiplizieren will, dann kann ich dies stets via ``a * b`` tun, unabhängig davon, um welchen Wertebereich es sich handelt.

In Java oder C müsste ich bei großen Zahlen bekanntlich die entsprechende BigNum-Bibliothek importieren und die Operationen über die dort bereitgestellten Funktions- bzw. Methoden-Aufrufe realisieren.

[noha1981]

@all
Danke für eure Erläuterungen!
Das es in anderen Sprachen, auch schon seid langem, Bibliotheken gibt, ist mir bekannt.
Jedoch finde ich es um so erstaunlicher das Python in seiner Grundfunktion über BigNum rechnet.

Faszinierend...

@snafu
Die Implementation scheinen über Schiebeoperationen zu laufen, richtig?
Bezüglich deines letzten Beitrages hast du genau meine Faszination erfasst.
In C++ kann ich z.B. nicht einfach a*b rechnen.

Gruß
Noha

[cofi]

Nun, es ist eine Design-Entscheidung, die ich nicht allzu ueberraschend fuer eine Hochsprache halte, ANSI Lisp macht das auch schon seit Urzeiten:

Code: Alles auswählen

* (expt 99 999)

43607320616826516150134170338646201223107986075620608122042152718341096569545917590671870901580903358089476539623429084337462072232323071988487722379025918136755324190771905744346299895101262599307041418954741821869968434014360426644150217367535228232882075278549084725532810757690211467541802733062351872629554887071558565105695677775800388952822060307618460889511910384740346745943545064075415717782672023429351183468901656480345653681279807760503885914267068619022794752754526226771965509515429769648943853393239466825581612114199388796846713698917724135481280269758239887617123242806941909343309827534698631895049620931536029044672739890893731191572695394918757396075233400643214858118180583796749973549192881847496687493228681933883471419305060028239670757748730500105612756664893487357552376496719298602670598130493347017948692042081377598537358748002952547169866050883302508349720700651016938696180158800498316548501175152775533119976607827063817490547330402728524591368881264569985453491886319052131328728570583818564408673363285874627267673252785057700907094407300537042771693320295830608507458585348221347122499594911138477627406334364083621560827029793286395456214852438250303387531773235681535933473521419169488498159152761557826192742496821559991415227170097504961476506200211299335714069542688981875338616104136244975260096287855709071756715604259948711756265446540708637145010756617391517706049935039684935491582597441963211160507086049676500663852688906531131555974645591096814621093225847864090909267239163899350786582783841798570024502259541481335139715410637523456696273629960402393128908813871826086839104466371057841461548132615966946230528245048730192919253049295790150492481440313287274889457554062183833564917170760547521002721621831858497390536681773386602450057910854295098455215379515799387105287701204877340476212991327443730608598868554899539340943577841165431687252557996668355126634828795393392192731183338157723722131288855592435620519974479953860308528414089899

Und gerade bei C++ kann man durch Operator-Ueberladung ja eben doch `a*b` rechnen vorausgesetzt `a` und `b` sind entsprechende Objekte

[jerch]

noha1981:
IdR bilden die BigNum-Libs die Zahlen über Arrays von Ziffern ab (in Registerbreite). Damit lassen sich die Grundrechenarten relativ simpel abbilden. Da Deine Frage weiter oben nicht beantwortet wurde - die Berechnung der Werte erfolgt exakt, da wird nicht mit Float-Tricks genähert (Floatnäherungen werden nur für bestimmte Bereichsabschätzungen genutzt, z.B. um zu wissen, wieviel Speicher fürs exakte Ergebnis zu allozieren ist etc.)

[noha1981]

Hallo Jerch,

danke für deine exakte Antwort, über die ich allerdings erstmal grübeln muss.
Jedoch ist meine eigentliche Frage damit hinreichend beantwortet .

Interessehalber verstehe ich aber die Abbildung über die Registerbreite nicht ganz.
D.h. bei einem 64 Bit System, wäre die Registerbreite 64.
Daraus folgt das in einem Zahlenarray max. 2 Ziffern stehen, da jede Ziffer 4 byte benötigt (64/8/4).
Woraus sich den letztlich nen Tupel der Länge x ergibt [[Ziffer1,Ziffer2], [Ziffer1,Ziffer2], ... , [Ziffer1, Ziffer2]].

Wenn ich das richtig verstanden habe, würde ich es als sehr aufwändig betrachten damit zu rechnen...

Liebe Grüße
Noha

[BlackJack]

@noha1981: Wie kommst Du auf diese Ziffernpaare oder das in einem Array maximal zwei Ziffern stehen? Da können beliebig viele Ziffern stehen, eben (fast) nur durch den verfügbaren Speicher begrenzt. Mit einer Ziffer ist hier ein Registerwort gemeint, also bei 64-Bit beispielsweise eben genau diese 64-Bit, also 8 Byte. Und in einem Array können dann soviele dieser Ziffern stehen wie benötigt werden. Jede Ziffer kan 2⁶⁴ Werte annehmen.

[jerch]

@noha1981:
Die Zahlendarstellung funktioniert analog des Binär- oder Decimalsystems als Stellenwertsystem, ebenso so Grundrechenarten über ähnliche Algorithmen, wie das, was wir mal als schriftliches Rechnen in der Schule gelernt haben. Und das macht es nach wie vor sehr aufwändig in der Berechnung (große Primfaktoren taugen nur deshalb für Kryptografie mit unseren derzeitigen handelsüblichen Rechnern). Einzig für die Multiplikation wird eine geringere Komplexität von O(n (log n)) vermutet als die der Schulmathematik mit O(n²). Wenn mich nicht alles täuscht, ist für diesen Beweis/Algorithmus eine Fieldsmedaille ausgelobt. Bisher gibts nur eine "bessere" Multiplikation für absurd große n (n als Stellen im Stellenwertsystem) mit irgendwas in O(n (log n) log (log n)).