Profil von emnity

15.05.2020, 20:59

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

...zum Beitrag

Hilfreichste Antwort

von emnity

15.05.2020, 21:58

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ß! :)

...zur Antwort