My Universe Logo

My Universe Blog » Entries Tagged as algorithms

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

Aus dem Leben eines ABAP-Programmieres

Posted by André Mühlnikel at April 20, 2009 8:17 p.m.

WAAAAAAAH. Tschuldige. Musste mal gesagt werden. Hier die lange Version:

continue reading Aus dem Leben eines ABAP-Programmieres

No comments | Defined tags for this entry: ABAP, algorithms, bizarre, software

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

Page 1 of 1