Adventskalender 16. Dezember 2023 - Nebenläufige Zahlenzerstückelung: Teil 1

[paedubucher]

Nebenläufige Zahlenzerstückelung: Teil 1

Um die Primfaktorzerlegung ging es bereits zweimal im diesjährigen Adventskalender. So wurde am 6. Dezember DAMPF im Kessel gemacht, indem die Primfaktorzerlegung in PHP ‒ mit mod_php bzw. mit PHP-FPM ‒ als Beispiel für einen Lasttest diente. Am 10. Dezember wurde unter dem Titel Bibliothek für Quellcodeverleih eine Shared Library in C für die Primfaktorzerlegung geschrieben und dazugelinkt.

Heute und morgen wollen wir uns hierfür in eine Nische begeben und die Primfaktorzerlegung auf Code-Ebene nebenläufig machen.

Erlang

Erlang ist eine funktionale Programmiersprache mit einer Prolog-ählichen Syntax, die beim schwedischen Telekom-Anbieter Ericsson ab den 1980er-Jahren entwickelt worden ist. Zwar hat man den Namen Erlang intern als Ericsson Language verkauft, tatsächlich wurde die Sprache nach dem Mathematiker Agner Krarup Erlang benannt.

Zwei der wohl wichtigsten Merkmale von Erlang sind leichtgewichtige Prozesse und die “let it crash”-Philosophie, wonach ein abgestürzter Prozess bei Bedarf einfach neu gestartet werden kann, ohne das Gesamtsystem dadurch zu beeinträchtigen. Bei Ausfällen des Telefonnetzes von wenigen Minuten pro Jahr hätte Ericsson gewaltige Bussen bezahlen müssen. Dank Erlang funktionierten die Systeme aber so zuverlässig, dass dies nie nötig war.

Wer mehr über Erlang erfahren möchte, sollte sich Erlang: The Movie anschauen, Joe Armstrongs Doktorarbeit durchlesen oder einfach einmal das Paket erlang installieren.

In Erlang wurden neben Telefonswitches u.a. Anwendungen wie WhatsApp oder RabbitMQ geschrieben.

Elixir

An der Qualität von Erlang und dem dazugehörigen Framework OTP (Open Telecom Platform) zweifelt kaum jemand. Doch stehen die ungewohnte Prolog-artige Syntax und der recht hohe Bedarf an Boiler-Plate-Code bei gängigen Konstrukten einer höheren Adaption im Weg. Erlang hat ein Marketing-Problem, was in Erlang: The Movie II humorvoll dargestellt wird.

Lustigerweise waren es dann tatsächlich frustrierte Ruby-on-Rails-Entwickler, die mit Elixir eine neue Sprache auf Basis von Erlang und deren virtuellen Maschine BEAM entwickelt haben. Elixir ist Erlang im Ruby-Gewand, wird aber in den gleichen Bytecode wie Erlang kompiliert und kann damit sehr gut mit bestehendem Erlang-Code interagieren. Das Web-Framework Phoenix orientiert sich in der Usability stark an Ruby on Rails, läuft aber dank dem technischen Unterbau von Erlang wesentlich stabiler und performanter.

Also wird es höchste Zeit, elixir zu installieren, wobei Erlang auch gleich mitinstalliert wird:

Code: Alles auswählen

# apt install elixir -y

Elixir interaktiv ausprobieren

Die mitinstallierte interaktive Elixir-Shell iex bietet eine REPL, mit der Elixir ausprobiert werden kann:

Code: Alles auswählen

$ iex
iex(1)> Enum.filter(1..10, fn i -> rem(i, 2) == 0 end)
[2, 4, 6, 8, 10]
iex(2)> Enum.map([2, 4, 6, 8, 10], fn i -> i * 2 end)
[4, 8, 12, 16, 20]

Im obigen Beispiel wird eine Sequenz der Zahlen von 1 bis 10 zuerst gefiltert (nach geraden Zahlen). Die geraden Zahlen werden anschliessend verdoppelt. Hierbei kommen die Funktionen höherer Ordnung aus dem Enum-Modul (siehe Dokumentation) zum Einsatz: filter/2 und map/2 (bei Erlang/Elixir werden die Anzahl Parameter ‒ die Arität ‒ jeweils mitangegeben).

Unix-Anwender werden sich über den Pipe-Operator |> freuen, der den linken Ausdruck als ersten Funktionsparameter des rechten Aufrufs verwendet:

Code: Alles auswählen

iex(3)> 1..10 |> Enum.filter(fn i -> rem(i, 2) == 0 end) |> Enum.map(fn i -> i * 2 end)
[4, 8, 12, 16, 20]

Wer die Sprache gründlicher kennenlernen möchte, dem empfehle in Elixir in Action von Saša Jurić oder meine Zusammenfassung davon, die noch ergänzt wird.

Primfaktorenzerlegung

Der Tradition des diesjährigen Adventskalenders, eine neue Technologie anhand des Beispiels der Primfaktorenzerlegung zu demonstrieren, soll hier gefolgt werden. So wird ein neues Elixir-Projekt namens factorizer mithilfe des Werkzeugs mix erstellt:

Code: Alles auswählen

$ mix new factorizer
$ cd factorizer/
$ ls
lib  mix.exs  README.md  test

Das Projekt besteht im Wesentlichen aus einer Projektdatei namens mix.exs und den Ordnern lib/ und test/, welche den Produktiv- bzw. Testcode enthalten.

Das Sieb des Eratosthenes

Zur Primfaktorzerlegung sollen zuerst einmal die Primzahlen gefunden werden. Hierzu soll mit dem Sieb des Eratosthenes ein Algorithmus implementiert werden, der wesentlich effizienter ist als reines Durchprobieren (Bruce Force).

Dem Sieb des Eratosthenes liegt die Erkenntnis zugrunde, dass zur Prüfung ob eine Zahl x eine Primzahl ist oder nicht nur Primzahlen p < x und nicht alle Zahlen i < x durchprobiert werden müssen, ob sie x restlos teilen können.

Beispiel: Wenn 13 nicht durch 2 restlos teilbar ist, wird es auch nicht zweimal durch zwei (d.h. durch 4) teilbar sein. Und da 13 weder durch 2 noch durch 3 teilbar ist, wird es auch nicht durch 2 mal 3 (6) teilbar sein. Es müssen also nur Zahlen durchprobiert werden, die selber nicht weiter in Primfaktoren zerlegt werden können.

Als Optimierung kann man die Obergrenze der durchzuprobierenden Zahlen auf x/2 festlegen, da eine Primzahl p > x/2 keine natürliche Zahl als Ergebnis von x/p haben kann: Das Ergebnis wäre immer kleiner als 1.

Faule Datenströme

Die funktionale Programmierung bietet ein sehr elegantes und effizientes Konstrukt zum Aufbauen von Zahlensequenzen, bei denen ein neues Element auf Basis der bestehenden Elemente berechnet wird: den sogenannten Lazy Stream. Lazy (faul) darum, weil nur so viele Elemente berechnet werden wie wirklich nötig sind.

Eine Zahlenreihe lässt sich mit dem Stream-Modul (genauer: mit Stream.iterate/2 folgendermassen definieren und dann mithilfe von Enum.take/2 konsumieren (hier anhand einer Dreierreihe):

Code: Alles auswählen

$ iex
iex(1)> three_times_table = Stream.iterate(3, fn x -> x + 3 end)
iex(2)> Enum.take(three_times_table, 10)
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30]

Das Startelement wird mit 3 vordefiniert. Jedes weitere Element ist definiert durch den Vorgänger, zu dem 3 addiert wird. Der Stream ist theoretisch unendlich lang, es wird aber nur so viel davon berechnet, wie wirklich verwendet wird: Beispielsweise wenn Enum.take/2 zehn Einträge davon haben möchte.

Möchte man einen Stream von geraden Zahlen erhalten, kann man die Funktionen Stream.iterate/2 und Stream.filter/2 miteinander kombinieren:

Code: Alles auswählen

$ iex
iex(1)> Stream.iterate(1, fn i -> i + 1 end) |> Stream.filter(fn i -> rem(i, 2) == 0 end) |> Enum.take(10)
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Es wird eine Zahlenreihe ausgehend von 1 definiert, bei der jeder Nachfolger als Vorgänger plus 1 definiert ist. Der Stream wird dann gefiltert, sodass nur restlos durch 2 teilbare Zahlen darin verbleiben (rem/2 ermittelt den Rest). Am Schluss wird eine Stichprobe der Grösse 10 genommen.

Ein Strom für Primzahlen

Für die Primzahlenfindung wird ein neues Modul namens PrimeSieve definiert (lib/prime_sieve.ex), welches das Sieb des Eratosthenes implementiert:

Code: Alles auswählen

defmodule PrimeSieve do
  def stream() do
    Stream.unfold([], fn
      [] -> {2, [2]}
      [h | t] -> next(h + 1, [h | t])
    end)
  end

  defp next(n, primes) do
    if Enum.any?(primes, fn p -> rem(n, p) == 0 end) do
      next(n + 1, primes)
    else
      {n, [n | primes]}
    end
  end
end

Das Modul besteht aus einer öffentlichen (da mit def definierten) Funktion stream/0 und einer privaten (da mit defp definierten) Funktion next/2. Stream.unfold/2 “entfaltet” einen Datenstrom anhand eines ersten Elements und einer Funktion, welche deren Nachfolger berechnet (next/2).

Im Gegensatz zu Stream.iterate/2 ist aber die Nachfolgefunktion so beschaffen, dass sie nicht nur das neue Element zurückgibt, sondern einen zusätzlichen Akkumulator, auf Basis dessen dann das nächste Element berechnet wird. Nächstes Element und Akkumulator werden als sogenannte Zweiertupel zurückgegeben, syntaktisch: {Nachfolger, Akkumulator}.

Betrachten wir die anonyme Nachfolgerfunktion einmal isoliert:

Code: Alles auswählen

fn
  [] -> {2, [2]}
  [h | t] -> next(h + 1, [h | t])
end

Die Funktion bietet zwei Klauseln und verwendet Pattern Matching, damit zur Laufzeit anhand des Arguments die richtige aufgerufen wird. (Polymorphe Methoden bei objektorientierten Sprachen bieten einen ähnlichen Mechanismus, der jedoch auf dem Datentyp und nicht auf dem Wert basiert.)

Wird die Funktion mit einer leeren Liste aufgerufen, ist das nächste Element die 2 ‒ die erste Primzahl ‒ und der Akkumulator besteht aus allen Primzahlen <= 2 ‒ die Liste [2].

Wird die Funktion mit einer nicht-leeren Liste aufgerufen ‒ [h | t] spaltet eine Liste in einen Head h (einzelnes Element) und einen Tail t (selber eine Liste) auf ‒ wird der Rückgabewert mithilfe von next/2 berechnet. Dieser wird der Nachfolger der höchsten bisher gefundenen Primzahl h + 1 (Listen werden vom Kopf her aufgebaut) und die Liste der bisher gefundenen Primzahlen (der Akkumulator) übergeben.

Die Funktion next/2 unterscheidet zwei Fälle:

1. Unter den bisher gefundenen Primzahlen primes existiert eine Primzahl (Enum.any?/2), welche den Primzahl-Kandidaten n restlos teilen kann.
   • Der Kandidat n ist keine Primzahl.
   • Es wird der nächste Kandidat n + 1 mit next/2 geprüft.
2. Der Kandidat n ist durch keine bisher gefundene Primzahl aus primes restlos teilbar.
   • Der Kandidat n ist eine Primzahl.
   • Es wird n als nächstes Ergebnis und ein um n am Kopfende erweiterter Akkumulator zurückgegeben.

Startet man iex mithilfe des Skripts mix, kann dieses Modul folgendermassen ausprobiert werden, indem eine Stichprobe der ersten 15 Primzahlen genommen wird:

Code: Alles auswählen

$ iex -S mix
iex(1)> PrimeSieve.stream() |> Enum.take(15)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Die Optimierung, die Teilbarkeit von x nur auf Primzahlen p <= x/2 zu prüfen, würde ein Umdrehen oder Vorfiltern von primes erfordern, da diese Liste vom Kopf her aufgebaut wird und darum das grösste Element am Anfang hat. Darum wird hier auf diese Optimierung verzichtet.

Faktorisierung durch Divisionsprobe

Die eigentliche Faktorisierung wird mit der Divisionsprobe durchgeführt. Der Algorithmus funktioniert folgendermassen:

1. Es wird eine Zahl x gegeben, die faktorisiert werden soll.
2. Es werden alle Primzahlen bis zur Zahl x ermittelt.
   • Als Optimierung genügt die Quadratwurzel von x als Obergrenze, worauf hier nicht näher eingegangen werden soll.
3. Aus der aufsteigend sortierten Liste der gefundenen Primzahlen wird die erste Primzahl p genommen.
   1. Ist x restlos durch p teilbar, ist p ein Primfaktor von x und wird als solcher in die Ergebnisliste aufgenommen.
      • Der Vorgang wird mit dem Quotienten von x/p fortgesetzt (x=x/p).
   2. Ist x nicht restlos durch p teilbar, ist p kein Primfaktor von x und wird nicht in die Ergebnisliste aufgenommen.
      • Der Vorgang wird mit x und der nächsten Primzahl p fortgesetzt.
4. Der Vorgang ist zu Ende, wenn:
   1. Die Zahl x bis auf 1 herunter dividiert worden ist. (1 ist das neutrale Element der Multiplikation, keine Primzahl und gehört somit nicht in die Ergebnisliste.)
   2. Alle Primzahlen durchprobiert worden sind, das verbleibende x offenbar selber eine Primzahl ist und als solche in die Ergebnisliste aufgenommen wird.

Das Module PrimeFactors (lib/prime_factors.ex) setzt diesen Algorithmus mithilfe von Pattern Matching um:

Code: Alles auswählen

defmodule PrimeFactors do
  def factorize(n) do
    sieve = PrimeSieve.stream()
    up_to = :math.sqrt(n)
    primes = Enum.take_while(sieve, fn p -> p <= up_to end)
    next(n, primes, [])
  end

  defp next(1, _, acc) do
    Enum.reverse(acc)
  end

  defp next(n, [], acc) do
    Enum.reverse([n | acc])
  end

  defp next(n, [h | t], acc) do
    if rem(n, h) == 0 do
      next(div(n, h), [h | t], [h | acc])
    else
      next(n, t, acc)
    end
  end
end

Die Funktion PrimeFactors.factorize/1 erwartet die zu faktorisierende Zahl, zu welcher sie die benötigten Primzahlen mithilfe von PrimeSieve.stream/0 ermittelt. Als Obergrenze wird die Quadratwurzel von n verwendet, wozu die sqrt/1-Funktion aus dem Erlang-Modul :math verwendet wird ‒ ein Beispiel für die nahtlose Integration der Host-Sprache. Mithilfe von Enum.take_while/2 werden Primzahlen aus dem Sieb genommen, solange diese nicht grösser als die ermittelte Obergrenze sind. Die Findung der Primfaktoren wird dann an die Funktion next/3 delegiert. Diese erwartet drei Parameter:

1. Die zu faktorisierende Zahl: n.
2. Die Liste der gefundenen Primzahlen: primes.
3. Einen Akkumulator, der die gefundenen Primfaktoren sammelt: zu Beginn die leere Liste [].

Die Funktion next/3 besteht aus drei Klauseln, wovon die ersten beiden den Basisfall und die dritte den allgemeinen Fall der Rekursion definieren:

• Erster Basisfall: Die zu faktorisierende Zahl wurde auf 1 herunterdividiert.
  • Das Ergebnis ist der mit Enum.reverse/1 umgedrehte (da vom Kopfende her aufgebaute) Akkumulator.
• Zweiter Basisfall: Die zu probierenden Primzahlen sind ausgegangen.
  • Das Ergebnis wird um den Rest n ‒ eine Primzahl ‒ am Kopfende ergänzt und umgedreht.
• Allgemeiner Fall: Weder hat n den Wert 1, noch ist die Liste der Primzahlen leer.
  1. Ist die Zahl n restlos durch die erste Primzahl aus der Liste teilbar, wurde ein Primfaktor gefunden. An den rekursiven Funktionsaufruf wird der Quotient von n/h (h ist die erste Primzahl der Liste), die gleiche Liste der Primzahlen und ein um h ergänzter Akkumulator übergeben.
  2. Andernfalls erfolgt der rekursive Aufruf mit der Zahl n, den restlichen Primzahlen (ohne die erste) und dem unveränderten Akkumulator.

Die Reihenfolge der Funktionsklauseln ist wichtig, da beim Pattern Matching bei jedem Aufruf von oben nach unten auf Übereinstimmungen geprüft wird. Dadurch wird ein Stack Overflow verhindert.

Da Elixir keine Schleifenkonstrukte kennt, wird next/3 als tail call aufgerufen: Der rekursive Funktionsaufruf ist das letzte, was die Funktion macht. Die Runtime kann so das Stack-Frame des Aufrufers übernehmen, da dieses nicht mehr gebraucht wird.

Die Primfaktorzerlegung soll nun interaktiv getestet werden:

Code: Alles auswählen

$ iex -S mix
iex(1)> PrimeFactors.factorize(24)
[2, 2, 2, 3]
iex(2)> PrimeFactors.factorize(99)
[3, 3, 11]
iex(3)> PrimeFactors.factorize(1024)
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Das sieht nachvollziehbar aus, kann aber direkt auf Korrektheit überprüft werden, indem die gefundene Sequenz mithilfe von Enum.reduce/2 und der Multiplikationsfunktion Kernel.*/2 aufmultipliziert wird:

Code: Alles auswählen

iex(4)> PrimeFactors.factorize(24) |> Enum.reduce(&Kernel.*/2)
24
iex(5)> PrimeFactors.factorize(99) |> Enum.reduce(&Kernel.*/2)
99
iex(6)> PrimeFactors.factorize(1024) |> Enum.reduce(&Kernel.*/2)
1024

Fazit

Die Primfaktorzerlegung wurde in Elixir implementiert, wozu Konzepte der funktionalen Programmierung wie Streams und Pattern Matching verwendet worden sind. Mithilfe des Streams müssen nur so viele Primzahlen berechnet werden, wie auch tatsächlich nötig sind. Das Pattern Matching drückt die übergeordnete Programmlogik deklarativ aus. Hierbei wurden zwei schlanke Module PrimeSieve und PrimeFactors implementiert, welche sich gut wiederverwenden lassen.

Ausblick

Bisher wurden nur die Primfaktoren einer einzelnen Zahl ermittelt. Im morgigen Türchen soll es einerseits darum gehen, die Primfaktoren mehrerer Zahlen zu berechnen. Andererseits soll diese Berechnung nebenläufig implementiert werden, sodass sie von mehreren Prozessoren Gebrauch machen kann und so (hoffentlich) schneller läuft.

Übungen

Wer Elixir einmal selber ausprobieren und sich in das Thema der Primzahlfaktorisierung vertiefen möchte, kann sich an den folgenden Übungen versuchen:

1. Installiere das Paket elixir und probiere es interaktiv mit iex aus.
2. Erstelle das Projekt factorizer mithilfe von mix und erweitere es wie oben beschrieben.
3. Warum verwendet PrimeFactors.factorize/1 als Obergrenze für die Primzahlen die Quadratwurzel von n und nicht n? Wie kann diese Optimierung begründet werden?
4. Könnte PrimeFactors.next/3 nicht auch direkt mit dem Stream der Primzahlen arbeiten, wodurch weniger davon im Voraus berechnet werden müssten?

Da bin ich mal gespannt, ob sich jemand Elixir, funktionale Programmierung und Mathematik inmitten der Adventszeit antun will…

[paedubucher]

Fürs Archiv habe ich mich noch selber an Aufgabe 4 versucht (Aufgaben 1-2 sind Fleissarbeiten, Aufgabe 3 wird in meinem Paper besprochen.) Hier ist eine Primfaktorzerlegung, welche nicht Primzahlen auf Vorrat generiert, sondern direkt den Stream von Primzahlen abarbeitet:

Code: Alles auswählen

defmodule PrimeFactors do
  def factorize(n) do
    sieve = PrimeSieve.stream()
    next(n, sieve, [])
  end

  defp next(1, _, acc) do
    Enum.reverse(acc)
  end

  defp next(n, sieve, acc) do
    [p | _] = Enum.take(sieve, 1)

    cond do
      p > :math.sqrt(n) -> Enum.reverse([n | acc])
      rem(n, p) == 0 -> next(div(n, p), sieve, [p | acc])
      true -> next(n, Stream.drop(sieve, 1), acc)
    end
  end
end

Der Code ist nicht schöner geworden, da der zweite Basisfall (Primzahlen erschöpft) nicht mehr da ist. Effizienter ist die Ausführung leider auch nicht geworden. Aber interessant war das Experiment allemal.

[dasebastian]

Aber interessant war das Experiment allemal.

Das Lesen deiner Beiträge auch.

Die sind für mich zwar anderer Planet, aber extrem schön und übersichtlich aufbereitet!

[paedubucher]

Aber interessant war das Experiment allemal.

Das Lesen deiner Beiträge auch.

Die sind für mich zwar anderer Planet, aber extrem schön und übersichtlich aufbereitet!

Danke für die Rückmeldung! Ich bin hier offenbar in eine recht enge Nische eingetaucht. Denn hier kommen zwei Themen zusammen, die mich wirklich interessieren: nebenläufige und funktionale Programmierung.