[python] Modulares Rechnen mit großen Zahlen |
05.02.2023, 20:55 | Malcang | Auf diesen Beitrag antworten » | ||||||
[python] Modulares Rechnen mit großen Zahlen wie manche ja mitbekommen haben, schaue ich mir derzeit diesen Primzahltest an: [attach]56784[/attach] In python habe ich diesen folgendermaßen umgesetzt:
Es funktioniert auch. Mir ist aber aufgefallen,dass die Berechnung in Zeile 19 ein Flaschenhals ist. Mit Exponenten in der Größenordnung dauert diese Berechnung eine Sekunde, mit bereits 8 Sekunden. Da ich im Programmieren wirklich nicht fit bin denke ich mal, dass mein Code sicherlich nicht optimal ist. Gibt es insbesondere für diese Berechnung Möglichkeiten, die ich nicht sehe? Vielen Dank und schönes Restsonntag |
||||||||
05.02.2023, 21:05 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Von welchem und (noch wichtiger) welchem Modul redest du hier? Vielleicht solltest du es statt mit pow(D, exp, n) auch einfach mal mit gmpy2.powmod(D, exp, n) probieren, diese Bibliothek hatte sich ja auch schon anderweitig als performanter erwiesen. |
||||||||
05.02.2023, 21:22 | Malcang | Auf diesen Beitrag antworten » | ||||||
Hallo HAL, danke für deine Zeit!
Es sind und . Dabei werden die Werte von sukzessive abgegrast, bis erfüllt ist.
Das probiere ich sofort aus Edit: Donnerwetter, das ist schon deutlich besser. bosma(5001, 15000) dauert jetzt nur noch 0.73 statt 8.5 Sekunden! Vielen Dank!! |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|