My Universe Logo

My Universe Blog » Entries Tagged as Project Euler

Die Rückkehr der Primzahl

Posted by Jesco Freund at Sept. 2, 2010 9:16 p.m.

Vor über einem Jahr hatte ich mal über einen kleinen Wettstreit bezüglich eines Primzahl-Generators gebloggt. Damals hatte ich mich darauf beschränkt, das Problem durch geschickte Partitionierung des zu testenden Intervalls zu parallelisieren. Allerdings war meine Implementierung alles andere als perfekt und krankte vor allem an Pythons Global Interpreter Lock. Meine Freundin hatte mich mit ihrer Implementierung fast um Faktor 2 geschlagen :-(

Doch nun habe ich sie in Händen, die ultimative Waffe des Primalitätstesters: im Zen Python Blog ist die Implementierung des Miller-Rabin-Tests in Python wunderbar beschrieben und erklärt. Dieser Test ist probabilistisch; nach unseren Spielregeln muss also bei einem positiven Treffer auf jeden Fall ein deterministischer Test (Primfaktorzerlegung) durchgeführt werden. Allerdings liefert Miller-Rabin verhältnismäßig wenige False Positives, so dass sich mit Hilfe dieses Tests das Finden von Primzahlen noch deutlich beschleunigen lassen sollte.

No comments | Defined tags for this entry: algorithms, programming, Project Euler, python

Herausforderung angenommen

Posted by Jesco Freund at March 27, 2009 12:01 p.m.

André hat es provoziert – was er mit Perl hinkriegt, muss ich mit Python doch auch hinbekommen ;-). Natürlich habe ich mich nicht damit begnügt, einen Abklatsch seiner Perl-Implementierung nach Python zu portieren – ein bisschen Optimierung musste schon sein. In Zeiten moderner Multicore-CPUs, so dachte ich, wäre es ideal, das Problem so zu formulieren, dass es parallelisiert abgearbeitet werden kann. Bei einem iterativen Algorithmus, dessen Iterationen auf die Ergebnisse der jeweiligen Vorstufen angewiesen sind, allerdings kein ganz triviales Unterfangen…

continue reading Herausforderung angenommen

No comments | Defined tags for this entry: algorithms, programming, Project Euler, python

Primzahlen und Faktorisierung

Posted by André Mühlnikel at March 14, 2009 12:26 p.m.

Dank projecteuler.net habe ich mal wieder angefangen, mich mit Perl auseinander zu setzen. Der größte Brocken bisher: Primzahl-Faktorisierung einer ziemlich großen Zahl. Nach ein paar ersten ziemlich erfolgversprechenden Versuchen, ein binäres Sieb_des_Eratosthenes zu bauen (also jede Zahl von 1 bis N wird durch ein Bit dargestellt - 0 = keine Primzahl, 1 = Primzahl), musste ich feststellen, dass das sehr schnell meinen Arbeitsspeicher sprengt (600 Mrd Bit = 75 GB), zumal das allermeiste davon nur 0en sind. Ziemlich unbefriedigend, also auf zur „Brute-Force“-Lösung des Siebes: man nehme alle bekannten Primzahlen (mindestens also „2“ als kleinste Primzahl) und probiere für jede neue Zahl aus, ob sie durch eine der Primzahlen teilbar ist. Das dauert aber UNENDLICH lange (jedenfalls fast). Also optimieren:

continue reading Primzahlen und Faktorisierung

No comments | Defined tags for this entry: open source, Perl, programming, Project Euler

Page 1 of 1