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
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]
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]
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 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]
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]
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
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
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:
- 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.
- 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.
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]
Faktorisierung durch Divisionsprobe
Die eigentliche Faktorisierung wird mit der Divisionsprobe durchgeführt. Der Algorithmus funktioniert folgendermassen:
- Es wird eine Zahl x gegeben, die faktorisiert werden soll.
- 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.
- Aus der aufsteigend sortierten Liste der gefundenen Primzahlen wird die erste Primzahl p genommen.
- 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).
- 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.
- Ist x restlos durch p teilbar, ist p ein Primfaktor von x und wird als solcher in die Ergebnisliste aufgenommen.
- Der Vorgang ist zu Ende, wenn:
- 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.)
- Alle Primzahlen durchprobiert worden sind, das verbleibende x offenbar selber eine Primzahl ist und als solche in die Ergebnisliste aufgenommen wird.
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 zu faktorisierende Zahl: n.
- Die Liste der gefundenen Primzahlen: primes.
- Einen Akkumulator, der die gefundenen Primfaktoren sammelt: zu Beginn die leere Liste [].
- 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.
- 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.
- Andernfalls erfolgt der rekursive Aufruf mit der Zahl n, den restlichen Primzahlen (ohne die erste) und dem unveränderten Akkumulator.
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]
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
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:
- Installiere das Paket elixir und probiere es interaktiv mit iex aus.
- Erstelle das Projekt factorizer mithilfe von mix und erweitere es wie oben beschrieben.
- 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?
- Könnte PrimeFactors.next/3 nicht auch direkt mit dem Stream der Primzahlen arbeiten, wodurch weniger davon im Voraus berechnet werden müssten?