Python: Große Zahlen faktorisieren?
Hallo, ich möchte mit Python große Zahlen faktorisieren und habe auch einen an sich funktionieren Algorithmus implementiert (p-1 Pollards)
Ich habe aber das Problem, das ab Zahlen der Größenordnung 10^16 die wissenschaftliche Schreibweise verwendet wird.
Wenn ich nun überprüfe, ob diese Zahl beispielsweise durch 2 teilbar ist, dann ist diese Aussage immer wahr.
Ich habe im Internet mehrere Möglichkeiten gefunden, diese Zahl "normal" darzustellen, also ohne die e schreibweise. Aber ich weiß nicht wie ich dafür sorgen kann, dass Python intern auch ohne diese Schreibweise rechnet.
Z.B. sagt Python, dass 1431245232242343162415 durch zwei teilbar ist, und zwar weil intern nicht mit 1431245232242343162415 sondern 1.431245232242343e+20 gerechnet wird.
Ich würde mich sehr freuen wenn mir jmd helfen könnte.
MfG
Ich glaub ich hab mich bei den großen Zahlen am Ende verschrieben, aber das Problem sollte trotzdem klar sein
3 Antworten
Das Problem liegt an deinem Programm!
In Python werden große Ganzzahlen nicht als Gleitpunktzahlen mit Exponent gespeichert!
Wenn deine Zahl als Gleitpunktzahl vorliegt, dann nur, weil du vorher eine Rechnung auf einer Ganzzahl durchgeführt hast, die implizit in einer Gleitpunktzahl mündet.
Ich würde raten, dass du irgendwo eine Division mit "/" anstatt "//" gemacht hast.
Bei so großen Ganzzahlen gibt es übrigens Überläufe, sodass sie nicht mehr als Gleitpunktzahlen dargestellt werden können.
Und davon abgesehen: Die schreibweise mit "e" und Exponenten ist nur eine reine Stringrepräsentation und hat nichts damit zu tun, wie Zahlen intern behandelt werden. Du kannst die natürlich auch genauso gut als Strings mit fixer Schreibweise formatieren!
Und zu guter letzt: Python ist für viele Dinge eine wunderbare Programmiersprache, aber fürs Numbercrunching denkbar schlecht geeignet.
Python ist viel viel viel zu lahm, um damit vernünftig größere Operationen auf Zahlen durchführen zu können. Das merkt man aber erst bei größeren Mengen Zahlen!
Ich hatte vor einer Weile ein Programm zum Herausfinden von Primzahlen geschrieben, und exakt das gleiche dann in C++ übersetzt.
Das Ergebnis war, dass die Python-Version über 700 Sekunden lief, und die C++ Variante nach 1.3 Sekunden fertig war.
Wenn man bedenkt, wie Python intern mit Ganzzahlen umgeht, ist das auch gar kein Wunder, bei dem, was es dort alles für Fallunterscheidungen und Sonderfälle gibt.
Pythons Integer sind zwar sehr komfortabel, da sie praktisch unendlich lang sein können, und man nicht wie in anderen Sprachen eine BigInteger-Klasse als Wrapper benötigt, aber das hat natürlich einen massiven Einfluss auf die Performance.
Merke dir also einfach ...
- ... auch wenn Python oberflächlich keine Typen "kennt", solltest du in deinem Programm unbedingt auf eben diese achten!
- ... du hast einen Bug, bei dem du eine Gleitpunktzahl wie eine Ganzzahl behandelst.
- ... Python nutzt intern keine Mantisse mit Exponent für Ganzzahlen.
- ... Pythons Integer können beliebig groß sein.
- ... Python ist saulahm wenn es um Rechenoperationen geht.
Ansonsten noch viel Spaß! :)
Vielen Dank für die ausführliche Antwort, es lag tatsächlich an den / statt //.
Da wirst du wohl einen Datentype "beliebig große Integer" implementieren müssen, mit den notwendigen Operationen darauf, z.B. Modulo.
In C und verwandten Sprachen, ja. Aber offenbar nicht in Python:
https://docs.python.org/2.4/lib/typesnumeric.html
Zitat: "Long integers have unlimited precision."
Das liegt nicht an der wissenschaftlichen Schreibweise, sondern das nur eine gewisse Größe von Zahlen in den Speicherplatz eines Integers passt (weiß gerade die genauen Daten nicht), aber auf alle Fälle werden dann (noch) größere Zahlen als Double gespeichert, weil double mehr Speicherplatz zur Verfügung hat (in Python).
dh als double ist deine Zahl durch zwei Teilbar
Tipp: Lies dich mal in die C++ Datentypen rein (int, float, double, long int, ....) für Python gelten (je nach BS) die gleichen Werte
Ich kenn zwar dein Lösungsansatz nicht, aber wenn ich prüfen möchte ob eine Zahl durch zwei Teilbar ist nehme ich Modulo und prüfe den Rest ob er gleich 0 ist, wenn ja, ist die Zahl gerade, wenn nicht, halt nicht.... Das hat auch bei deiner angegebenen Zahl funktioniert.
Dazu muss man auch sagen, dass der Computer bzw. Python intern gar nicht mit der wissenschaftlichen Schreibweise arbeitet! Dies ist nur für den User damit man größere Zahlen versteht und nicht die Anzahl der Stellen nachzählen muss usw.
Das stimmt alles überhaupt nicht!
Pythons Integer arbeiten intern meist mit 64 Bit und bei größeren Werten wird auf eine spezielle Implementierung einer Klasse für große Ganzzahlen umgeschaltet.
Und in "double" passen logischerweise WENIGER ganzzahlige Werte, als in einen "long", da die auf den meisten Plattformen beide 64 Bit breit sind.
Bei Python wird nur implizit bei bestimmten Rechenoperationen konvertiert, allen voran die Division.
Oke danke. Ja aber warum ist denn meine zahl als Double durch zwei teilbar? Und wie kann ich das verhindern.
Wie gesagt, ich habe zum Faktorisieren der Zahl den p-1 Pollard Algorithmus implementiert. Ich bin Mathestudent und soll die mathematische Funktionalität mehrerer Faktorisierungsalgorithmen im Rahmen eines Algebra Seminars vortragen. Dazu habe ich eben auch angefangen die Algorithmen zu implementieren.
Deswegen brauche ich leider eine Lösung für das konkrete Problem und kann das nicht auf modulo umschreiben
MfG
Pythons Integer sind von Haus aus sowieso immer beliebig groß!
Das Limit stellt der verfügbare RAM dar!
(Genau genommen sind Pyhon Integer meist 64 bittig und wenn es größer wird, dann wird intern automatisch auf eine Art BigInteger umgeschaltet!)