Extrem große Zahlen in Programmiersprachen?
Hallo,
bis jetzt hab ich immer gelernt das Limits von Zahlen in Programmiersprachen immer fest definiert sein müssen. So kann ein int beispielsweise in den meisten Fällen höchstens 2^32 Zahlen darstellen. Jetzt hab ich aber in Prolog gesehen, dass das auch ohne feste größenangabe möglich ist dort kann man Zahlen auch so viel Arbeitsspeicher wie nötig nutzen lassen.
http://www.swi-prolog.org/pldoc/man?section=artypes
Gibts sowas auch in sprachen wie C++ und C#? Ich hab sowas nämlich noch nie gesehen aber es funktioniert, im Anhang seht ihr ein Bild wie ich die 100000te Fibonaccizahl berechne ;).
4 Antworten
Die Datentypen mit fester Breite richten sich nach der Rechnerarchitektur, auf der dein Programm läuft. Deshalb sind diese immer am effizientesten, und für die üblichen Berechnungen reichen diese begrenzten Datentypen auch locker aus.
Grundsätzlich gibt es aber in (vermutlich) jeder Programmiersprache Bibliotheken oder Module, die eine beliebige Genauigkeit, bzw. einen unbegrenzten Wertebereich erlauben. (Wie du schon selbst gesagt hast, hängt das natürlich vom Verfügbaren RAM o. anderen Hardwarefaktoren ab).
Die gängigsten Bibliotheken für C++ sind wohl GMP oder Boost. Es gibt aber noch unzählige andere, wenn du nach "bignum" oder "BigInteger" suchst. (Übrigens ist das eine schöne Übungsaufgabe für Einsteiger, so eine Bibliothek selber zu schreiben, um mal ein Gefühl für die Innereien zu bekommen!)
Bei C# gibt es (wie auch bei Java) eine BigInteger-Klasse. Wenn ich mich nicht täusche, hat C# kein BigDecimal-Äquivalent, aber "decimal" ist 128 Bit breit, falls dir das reicht. Ansonsten musst du dir auch dafür eine Bibliothek raus suchen (bei Google gibt es viele!).
(Du kannst dir übrigens auch eine eigene BigDecimal-Klasse aus BigInteger-Komponenten zusammen bauen. Dafür ist überraschend wenig Code notwendig!)
Fazit: Für alle Programmiersprachen dürfte es eine Art Erweiterung für große Zahlen geben. Für die großen und beliebten Sprachen sowieso gleich mehrere!
PS: Noch ein kleiner Gedanke ...
...im Anhang seht ihr ein Bild wie ich die 100000te Fibonaccizahl berechne ;)
Du hast das doch hoffentlich nicht iterativ gelöst, sondern eine entsprechende Formel benutzt, oder? :)
Nein hab keine entsprechende Formel verwendet sondern es iterativ gemacht. Prolog ist eigentlich nicht wirklich für Mathematik gedacht sonder betrachtet alles eher symbolisch, da es eigentlich für logische Schulssfolgerungen gedacht ist. Deshalb wird es schwer solch eine Formel anzugeben xD. Hab das also iterativ gelöst und mir die schon berechneten Fibbonaccizahlen gemerkt.
Ich hab also eine laufzeitkomplexität von O(n) und nicht wie bei einer Formel von O(1). Dafür liegt sie aber auch nicht wie wenn ich mir die Ergebnisse nicht merke bei O(2^n). Dann komm ich nur bis zur 40ten Zahl ohne lange warten zu müssen.
Auch wenn die hilfreichste Antwort schon vergeben ist, fehlen mir noch Fakten:
- bei extrem großen Zahlen kommt man fast nur noch mit c++ oder anderen hardwarenahen Sprachen die SSE & AVX-Befehle & Multitasking unterstützen in vertretbarer Zeit ans Ziel!
http://www.gerdlamprecht.de/BisZuWelcherNKalleStringKombi.htm
Tabelle unten. (optimiertes c++ kann so 52000 mal schneller als c# werden)
- viele Eigennamen wie GMP, Pari-GP usw. basieren intern auf c++
Wer sich für große Fibonacci-Zahlen interessiert, kann sich
http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php
extrem große Ergebnisse online anzeigen lassen.
Bei Fibonacci(100000000) alle Ziffern auch als ZIP
bei Fibonacci(1000000000) kann man sie sich zuschicken lassen.
Zum Algorithmus: zwar gibt es explizite Formeln aus irrationalen Zahlen, ABER dann müsste man ja alles mit zig Mio. Nachkommastellen berechnen, wenn man auch die letzte Ziffer exakt haben möchte!
Der primitive iterative Algorithmus aus den 2 Vorgängern ist zwar exakt, aber für große Zahlen sehr langsam.
Es gibt ein iterativen Abkürzungsalgorithmus, der selbst noch per JAVA schnell genug ist, um etwas über 8 Mio. Stellen zu berechnen.
Per default bist du an die bekannten Datentypen gebunden, long long mit 64 bit oder long long double mit bis zu 80 bit.
es gibt libraries die erlauben mehr, Xint sowie Boost
Oder man baut es sich selbst, du kannst ja im heap ablegen soviel du willst.
xD Man hätte sich das einfach mal genauer durchlesen müssen. Die libary ist anscheinend ne gnu libary hier der link falls es dich interessiert :D.
https://de.m.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library
Bigint
Wenn C++ das nicht kann, dann kann doch boost.