Das Sieb von Atkin


Ich hatte ja schon eine dynamische Version des Sieb des Eratosthenes mit Wheel vorgestellt.

Erst kürzlich habe ich davon gelesen, dass es nach nur ein-, zweitausend Jahren tatsächlich eine schnellere Version des Siebs gibt: Das Sieb von Atkin, das auf quadratischen Formen beruht. Die dazu nötige Mathematik ist zwar alles andere als trivial, aber der Pseudocode auf Wikipedia ist wirklich verblüffend einfach, und lässt sich fast eins zu eins nach Scala übersetzen:

  def atkinSieve(limit:Int) = {
    val isPrime = Array.fill(limit)(false)
    List(2,3).foreach(isPrime(_) = true)
    for{x <- 1 to math.sqrt(limit).toInt
        y <- 1 to math.sqrt(limit).toInt} {
      def invert(n:Int, test:Int => Boolean) {
        if (n < limit && test(n)) isPrime(n) = ! isPrime(n)
      }
      invert(4*x*x+y*y, n => n % 12 == 1 || n % 12 == 5)
      invert(3*x*x+y*y, n => n % 12 == 7)
      if(x > y) invert(3*x*x-y*y, n => n % 12 == 11)
    }
    for{n <- 5 until math.sqrt(limit).toInt+1 if isPrime(n)
        s <- n*n until limit by n*n}
      isPrime(s) = false
    isPrime.zipWithIndex.filter(_._1).map(_._2)
  }

Sicher alles andere als hochoptimiert, aber es funktionert. Da ich zur zugrundeliegenden Mathematik wenig Erhellendes beitragen kann, beschränke ich mich auf ein paar Anmerkungen zum Code. Ich benutze zweimal eine for-Comprehension. Da ich mehrere Laufvariablen habe, verwende ich geschweifte Klammern – damit spart man sich die bei runden Klammern notwendigen Semikolons. In der zweiten for-Comprehension findet sich „if isPrime(n)“. Obwohl es fast so aussieht, handelt es sich nicht um eine if-Anweisung, sondern um einen sogenannten „Wächter“ (Guard), der die möglichen Werte einschränkt. Auch case-Klauseln können solche Guards besitzen. Dieses Konstrukt ist schon lange in vielen funktionalen Sprachen „Standard“, etwa in Haskell.

Innerhalb der ersten for-Comprehension möchte ich dreimal „fast das Gleiche“ machen, und habe deshalb im Sinne des DRY-Prinzips eine lokale Methode verwendet – ein Feature, das mir bei Java wirklich fehlt. Dabei lassen lokale Methoden nicht nur eine bessere Strukturierung zu, sonder man „spart“ sich auch einige Übergabeparameter (hier z.B. die Variablen „limit“ und „isPrime“). Das zweite Argument von invert ist übrigens eine Funktion (oder Closure), womit wir gleich das zweite wichtige Scala-Feature hätten, das ich in Java vermisse. Ist es nicht obercool, dass man einen Test einfach so als Argument mitgeben kann? Natürlich lässt sich sowas auch in Java nachbilden – siehe z.B. functionaljava – aber es bleibt doch so schwerfällig, dass ich in diesem Beispiel lieber darauf verzichtet und die Code-Wiederholungen in Kauf genommen hätte.

Bleibt noch das vielleicht etwas mysteriöse isPrime.zipWithIndex.filter(_._1).map(_._2). Aber das ist ganz einfach erklärt: isPrime ist ein boolesches Array, das für jeden Index angibt, ob die jeweilige Zahl eine Primzahl ist. Nun ist natürlich ein Array mit den tatsächlichen Primzahlen meist wesentlich praktischer und vor allem viel kürzer. Wie macht man nun aus dem booleschen Array eine Collection mit Primzahlen? Die nützliche Funktion zipWithIndex „vertupelt“ die Werte einer Collection mit ihren Indizes, aus unserem isPrime-Array (false, false, true, true, false, true, …) wird also (Pair(false,0), Pair(false,1), Pair(true,2), Pair(true,3), Pair(false,4), Pair(true,5) …). Pair(x, y) ist nur ein vordefinierter Alias für Tuple2(x, y) oder schlicht (x, y). Auf das erste Element eines Tupels kann man mit tuple._1 zugreifen, auf das zweite mit tuple._2 u.s.w. Damit sieht man auch schon, was das filter macht (nur die Tupel behalten, deren erstes Element „true“ ist) und was map macht (es erstellt eine Collection aus den zweiten Elementen des Tupel – also unsere Indizes). Am Ende bleibt ein Array mit Primzahlen übrig.

Nun würde ich gern auch für das Sieb von Atkin eine „dynamische“ Variante ohne festes Limit präsentieren, aber bisher hatte ich noch keine tolle Inspiration, wie man das realisieren könnte. Irgendwelche Ideen?

[Edit] Kleinen Bug in der zweiten for-Comprehension beseitigt, der bei großen Sieben zu Überlauf-Problemen geführt hat.
[Edit] Da die Modulo-Tests auch die 5 finden und invertieren, darf ich diese zu Beginn nicht setzen.

Advertisements

3 Gedanken zu “Das Sieb von Atkin

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s