Qbi's Weblog

Kürzlich ging eine Erschütterung durch die Welt der Kryptografie. Das Paper Quantum Algorithms for Lattice Problems versprach einen neuen Angriff gegen bestimmte Algorithmen. Diese heißen Learning-With-Errors (LWE) und bilden eine Grundlage für Algorithmen, die gegen Quantencomputer sicher sein sollen. Hier spielt eine Menge Mathematik mit hinein. Als Beispiel seht ihr eine halbe Seite aus dem Paper:

Das Thema klang hinreichend interessant und ich wollte mich ein wenig einlesen. Zum konkreten Paper muss man sagen, dass mittlerweile ein Fehler im Algorithmus gefunden wurde und die Autoren schreiben:

Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold.

Beim Lesen fiel mir wieder etwas auf, was mir schon früher auffiel. Es gibt Sätze, die kommen recht unschuldig daher und klingen leicht verständlich. Dennoch steckt soviel Theorie dahinter, dass es eine Weile dauern könnte, um diese zu durchdringen.

Gleich in der Einführung findet sich ein Beispiel: An n-dimensional lattice L is a discrete additive subgroup of ℝⁿ. (Ein n-dimensionales Gitter L ist eine diskrete additive Untergruppe von ℝⁿ.)

Welche Begriffe muss man verstehen oder interpretieren können, um die Definition zu verstehen?

1. n-dimensional
2. diskrete additive Untergruppe
3. ℝⁿ

Das heißt, nahezu jedes Wort ist erklärungsbedürftig und mit Schulwissen kaum zu durchdringen. Wenn wir jetzt die Wikipedia konsultieren, kommen wir ein Stück weiter. Dort findet sich auch eine Definition des Gitters als diskrete Untergruppe eines euklidischen Raums sowie einige Beispiele. Wenn wir beide Definitionen vergleichen, steht in dem Paper zusätzlich das Wort additiv und anstatt euklidischer Raum wird von ℝⁿ gesprochen. Aus der Wikipedia-Seite zum euklidischen Raum wird schnell klar, dass ℝⁿ ein euklidischer Raum ist. Also sind beide Definitionen ähnlich. Das heißt, mit kleinen Einschränkungen können wir mit der Wikipedia-Definition weiterarbeiten.

Um den Satz nun zu verstehen, sollten wir uns dem zweiten Begriff, der diskreten additiven Untergruppe, zuwenden. Beim Aufdröseln ergeben sich neue Begriffe, die man entweder kennen oder lernen muss.

• Untergruppe
  • Eine Untergruppe hat eine Verknüpfung (Addition, Multiplikation etc.) und bildet eine Gruppe.
    • Eine Gruppe ist eine Menge mit einer Verknüpfung (Addition, Multiplikation etc.). Bei der Verknüpfung ist es egal, wie man Klammern setzt (Assoziativgesetz), es gibt ein so genanntes neutrales Element und ein inverses Element. Wenn man ein neutrales Element verknüpft, ändert sich nichts, so wie bei einer Addition mit 0. Wenn man ein Element der Menge mit dessem inversen Element verknüpft, erhält man das neutrale Element (12-12=0 bei der Addition, -12 ist das inverse Element).
• Additive Untergruppe
  • Das ist eine Untergruppe, wo die Verknüpfung Addition heißt.
• Diskrete Untergruppe
  • Eigentlich geht es hier um diskrete Teilmengen eines Raumes mit der zusätzlichen Eigenschaft, dass diese Teilmenge eine Untergruppe bildet.
  • Eine Teilmenge ist, wie der Name schon sagt, ein Teil der Menge.
  • Diskret bedeutet nun, dass jedes Element der Menge eine Umgebung hat, dass kein weiteres Element der Teilmenge enthält. Das heißt, die einzelnen Elemente der Menge sind isolierte Punkte.
  • Die ganzen Zahlen …, -2, -1, 0, 1, 2, … sind als Teilmenge der reellen Zahlen eine solche Menge. Denn bei jeder Zahl gibt es nach links und rechts einen Abstand, wo sich keine andere Zahl drin findet. Bei den Brüchen (rationale Zahlen) ist das anders. Dort finden sich keine zwei Zahlen mit einem kleinen Abstand, dass keine andere rationale drin läge. Daher ist das keine diskrete Teilmenge.
• ℝⁿ
  • ℝⁿ ist der n-dimensionale Raum der reellen Zahlen. Aus der Schule kennt man ℝ¹ (Zahlenstrahl), ℝ² (Zahlenebene) und ℝ³ (dreidimensionaler Raum).

Damit haben wir alle Bauteile zusammen, um den obigen Satz zu verstehen. Wobei ich zugeben, muss, dass ich oben einige Abkürzungen genommen habe und auf intuitives Verständnis gesetzt habe. Dennoch reicht das in der Mathematik oftmals nicht. Es ist sinnvoll, sich Beispiele auszudenken. Diese sollten sowohl den positiven Fall abdecken (erfüllt die Definition), aber auch den negativen Fall (erfüllt die Definition nicht). Das sorgt dann wirklich für ein Verständnis des Ganzen.

Das war es auch, was ich am Anfang meinte, als ich von dem kleinen unschuldig klingenden Satz schrieb. Um den zu verstehen, muss man entweder tief im irgendwann mal Erlernten graben oder neues lernen und es dauert eine längere Zeit, bis man ein Paper einmal durchgearbeitet hat. Noch viel länger dauert es, bis man es verstanden hat.

Der obige Satz war der Einstieg in das Paper und nur die Einleitung. Später geht es um gaussche Funktionen und Fouriertransformationen. Das sind Konzepte über die es semesterlange Vorlesungen gibt. Das heißt, um das zu verstehen, kann man wirklich aus den Tiefen der Mathematik schöpfen. Ich wünsche euch viel Spaß bei der Lektüre.

Mit dem Paper haben sich einige andere auseinandergesetzt. Hier findet ihr interessante Lektüre dazu:

• Implications of the Proposed Quantum Attack on LWE
• A quick post on Chen’s algorithm

Die Nachrichten über die schlimmen Terroranschläge in Brüssel ziehen am Nachrichtenticker vorbei und schon beginnen wieder die üblichen Diskussionen. Die Innenpolitiker fordern mehr Überwachung, andere machen die Flüchtlinge oder Angela Merkel verantwortlich, wieder andere weisen darauf hin, dass Flüchtlinge gerade vor dem Terror geflohen sind etc. Es tauchen auch, wie bei anderen Anschlägen, Meldungen auf, dass die Kriminellen schon vorab den Behörden bekannt waren und es wird die Frage gestellt, warum nichts gemacht wurde. Einer der Gründe ist die Mathematik, die gegen die Behörden spielt. Warum ist das so?

Zu Anfang treffe ich ein paar Annahmen: Ich verwende Belgien als Beispiel. Das Land hat ca. 11 Millionen Einwohner. Weiterhin bräuchte ich eine Zahl potenzieller Terroristen. Jetzt nehme ich mal an, es gäbe nur islamistischen Terrorismus. In Deutschland meldet das Bundesamt für Verfassungsschutz ein islamistisches Personenpotenzial von knapp 44.000 Menschen. Angenommen die Zahl lässt sich 1:1 auf Belgien übertragen, so leben dort gerundet 5.500 Menschen mit einem islamistischen Personenpotenzial. Das Ziel der Behörden ist nun, diese Personen zuverlässig zu filtern und ggf. zu beobachten.

Dazu werden Überwachungs-, Datenauswerte- und Kontrollmaßnahmen installiert. Das System ist so leistungsfähig, dass es 99,9% aller Terroristen erkennt. Also nur in einem Tausendstel der Fälle wird ein Terrorist nicht als solcher erkannt. Aber es erkennt auch Normalbürger in einem Prozent der Fälle fälschlicherweise als Terroristen.

Das System ist in Betrieb und bringt einen Alarm, dass es einen Terroristen erkannt hat. Aber ist dies wirklich einer und wie hoch ist die Wahrscheinlichkeit? Geht mal in euch und versucht, eine Schätzung abzugeben.

Um die Frage zu beantworten, stellen wir uns vor, dass System würde ganz Belgien durchleuchten. Es würden also 5.495 Terroristen erkannt werden. Daneben erkennt das System auch 110.000 Einwohner als Terroristen, die keine sind. Das heißt, insgesamt wird 115.495 Mal Alarm geschlagen. Aber der Alarm war nur in 4,7 % der Fälle korrekt. Das heißt, das System schlägt in mehr als 95 % der Fälle falschen Alarm.

Das heißt, dass zwar viele Personen und besonders viele Terroristen von so einem System erkannt würden. Dennoch sind auch hier die Mehrzahl unbescholtene Bürger und die Strafverfolger haben die Arbeit, korrekt zu filtern. Diese Arbeit sieht im Nachhinein sehr einfach aus. Aber üblicherweise fehlen bei der Suche vor einem Anschlag viele konkrete Hinweise. Letztlich müssen wir akzeptieren, dass es perfekte Sicherheit nicht herstellbar ist. Ich bin der Meinung, dass nicht mehr Überwachung, Datenaustausch und Repression die Lösung ist, sondern die Politik (»wir«) sollte sich Gedanken machen, wo die Gründe liegen und diese beseitigen.

Von Primzahlen geht für viele eine große Faszination aus das Thema wird aus verschiedenen Richtungen gern beleuchtet. Sehr alt ist dabei die Fragestellung, wie viele Primzahlen es denn gibt. Euklid fand neben anderen die Antwort auf diese Frage: Es gibt unendlich viele Primzahlen. Sein Beweis ist recht einleuchtend.

Stellen wir uns vor, es gäbe nur endlich fünf Primzahlen (In der Regel sagt man: endlich viele) p1, p2, p3, p4 und p5. Dann berechnet man eine neue Zahl z = p1*p2*p3*p4*p5+1, d.h. alle Primzahlen werden multipliziert und anschließend wird die Zahl 1 addiert. Keine der bisherigen Primzahlen teilt diese Zahl z. Da aber jede natürliche Zahl einen Primteiler besitzt, muss der außerhalb der bisher bekannten Primzahlen liegen, d.h. es gibt mindestens eine neue Primzahl p6. Die Aussage lässt sich dann wieder anwenden und so ergibt sich, dass die Zahl der Primzahlen nicht endlich sein kann.

Bei Mathoverflow wurden diverse Fehleinschätzungen diskutiert. Unter anderem zählte dazu, dass die oben konstruierte Zahl z eine Primzahl sei. Wenn man den Beweis oberflächlich liest (siehe auch die Skripte zu Algebra 1 oder Zahlentheorie), könnte man in der Tat zu dem Schluss kommen. Die Zahlen 2, 3, 5, 7, 11 und 13 liefern jedoch ein Gegenbeispiel.

Schlimm finde ich dann die in dem Posting angegebenen Beispiele von Leerern (sic!), die ihre Schülern unter Beschimpfungen vor die Tür stellen, weil sie auf den obigen Umstand hinweisen und den auch noch beweisen.

Falls ihr euch schon immer mal gefragt habt, wie man ein reguläres 17-Eck mit Zirkel und Lineal konstruiert. Hier ist die Lösung:

Bei Holgi fand ich folgendes wunderbare Video. Es erzählt die Geschichte des Mathematikers Cantors, des Physikers Boltzmann sowie weiterer Größen. Ich finde das bisher (bin noch nicht am Ende) sehr sehenswert.

Stell dir vor, du schreibst einen mathematischen Text und musst einen Ausdruck der Form df/dt (als richtigen Bruch) schreiben. Der einfachste Weg, dies zu realisieren, wäre mittels \frac{df}{dt}. Das d muss jedoch aufrecht stehen. Also müsste man ein Konstrukt mit \mathrm{} oder ähnlichem basteln. Ähnlich sieht die Situation bei partiellen Ableitungen aus.

Ich stolperte vor kurzem über das Paket esdiff. Dies macht es sehr einfach, die obigen Konstrukte zu setzen. Für den obigen Ausdruck existiert der Befehl \diff{}{} und man würde schreiben: \diff{f}{t}. Für partielle Ableitungen lässt sich \diffp{}{} nutzen.

Insgesamt vereinfacht das Paket den Satz von Ableitungen und wird ab sofort zu meinem Standardrepertoire gehören.

In einem Rätsel fragte ich vor kurzem nach der Lösung zu folgendem Problem:

Wenn man das Ganze nun 29mal macht, also 2²⁹, erhält man eine neunstellige Zahl. Diese neun Zahlen sind voneinander verschieden. Da wir im normalen Leben mit 10 Zahlen (0, ..., 9) rechnen, muss hier also eine fehlen. Die Frage ist, welche Zahl ist das?

Nach den Kommentaren zu urteilen, haben viele ihre Lieblingsprogrammiersprache angeworfen, gerechnet und hatten das Ergebnis. Der Witz an dem Rätsel ist aber, die Lösung ohne solche Hilfsmittel und ohne explizites Errechnen zu ermitteln. Wie sieht nun ein möglicher Weg aus?

Überlegt euch zunächst mal ein paar Eigenschaften einer Zahl, die alle Ziffern von 0 bis 9 (im folgenden mal Oberzahl genannt) genau einmal enthält. Ist diese durch 2, 3, 4 usw. teilbar?

Was relativ schnell klar sein sollte, ist, dass die Zahl sowohl durch 3 als auch durch 9 teilbar ist. Die Teilbarkeitseigenschaft wird in beiden Fällen über die Quersumme ermittelt. Das Ergebnis von 0+1+2+3+4+5+6+7+8+9 wusste bereits der kleine Herr Gauß (und brachte damit seinen Lehrer zur Verzweiflung) und ist 45 (9*(9+1)/2). Da diese Zahl durch 3 und 9 teilbar ist, muss auch die ursprüngliche durch 3 und 9 teilbar sein. Wenden wir uns insbesondere der Teilbarkeit durch 9 zu.

Stellt euch vor, wir ziehen von der Oberzahl (also der, die alle Zahlen von 0 bis 9 einmal enthält) 1 ab und schauen, ob das Ergebnis durch 9 teilbar ist. Dies ist natürlich nicht mehr der Fall. Dividieren durch 9 ergibt irgendetwas mit Rest 8 (oder auch mit Rest -1). Auch die Quersumme ist nun 44, also eine Zahl, die den Rest 8 (oder auch -1) ergibt, wenn man sie durch 9 teilt. Andererseits könnte man von der Oberzahl einfach eine Zahl weglassen und schauen, was Division durch 9 ergibt. Wenn ihr also die 1 aus der Zahl entfernt, ist die Quersumme wieder 44, also eine Zahl mit Rest 8 (modulo 9). Das heißt, mit diesem Wissen müssen wir uns nun anschauen, welchen Rest die Zahl 2²⁹ bei der Division mit 9 hat.

Im einfachsten Fall kann man sich dazu die ersten Glieder der Folge ausrechnen und schauen, ob es Regelmäßigkeiten gibt:
2⁰=1?=1 (mod 9)
2¹=2?2 (mod 9)
2²=4?4 (mod 9)
2³=8?8 (mod 9)
2⁴=16?7 (mod 9)
2⁵=32?5 (mod 9)
2⁶=64?1 (mod 9)
2⁷=128?2 (mod 9)
2⁸=256?4 (mod 9)
Wer die Notation nicht kennt: n (mod 9) bedeutet, geteilt durch 9 mit Rest n.

Es ist hier also ein Zyklus 1, 2, 4, 8, 7, 5 zu erkennen. Wenn man den Zyklus bis 29 betrachtet, erhält man das Ergebnis 2²⁹=5 (mod 9).

Der eher mathematische Weg wäre, den Satz von Euler geeignet auszunutzen. Da muss man die obigen Schritte nicht mühselig per Hand rechnen, sondern bekommt das Ergebnis gleich präsentiert.

Im obigen Beispiel war das Ergbnis Rest 8, da von der Oberzahl 1 abgezogen wurde. Hier erhalten wir als Ergebnis 5. Also fehlt in 2²⁹ die Zahl 4.

Bild von eqqman

Zu Anfang der Woche habe ich ein kleines Rätsel für alle Freunde der Mathematik. Ich fand das bei God Plays Dice und habe es unten mal ins Deutsche gebracht.

Die Potenzrechnung dürfte euch allen noch aus der Schule bekannt sein. Freunde der Bits und Bytes rechnen gern zur Basis 2. Das heißt zum Beispiel 2¹=2, 2²=2·2=4, 2³=2·2·2=8 usw. Wenn man das Ganze nun 29mal macht, also 2²⁹, erhält man eine neunstellige Zahl. Alle dDiese neun Zahlen sind voneinander verschieden. Da wir im normalen Leben mit 10 Zahlen (0, ..., 9) rechnen, muss hier also eine fehlen. Die Frage ist, welche Zahl ist das? Wer hat eine Idee?

Update: Satzbau oben nach dem Kommentar von Sven geändert.

Im Rahmen eines Seminars an der Uni hielt ich kürzlich einen Vortrag über AES und eine Einführung in Public-Key-Kryptografie. Die Unterlagen sind als PDF-Dokument verfügbar. Zum Grundverständnis finde ich auch diese Animation interessant. Sie enthält aus mathematischer Sicht nur ein paar Unzulänglichkeiten.

Der Vortrag verlief aus meiner Sicht sowie der der Teilnehmer gut. Nur der betreuende Professor meinte, er finde es schade, dass so wenig Mathematik dabei ist.

Mittlerweile gibt es einen neuen Angriff auf den Algorithmus. Bruce Schneier verweist im Beitrag New attack on AES auf die Veröfentlichung. Die Autoren haben auch eine FAQ zu den wichtigsten Fragen des Angriffs. Ich muss das demnächst mal lesen und verstehen.

Viele scheint die Frage zu bewegen, wie man Brüche und insbesondere große Brüche in LaTeX schreiben kann. Üblich ist die Verwendung von \frac{}{}. Das führt zu der gewohnten Darstellung eines Bruches. Manchmal ist es besser, den Bruch mit einem Schrägstrich zu setzen (so wie 1/2). Hierzu muss mittels \usepackage{nicefrac} das Paket nicefrac eingebunden werden. Danach steht der Befehl \nicefrac{}{} zur Verfügung. Wie bei \frac{}{} kommt in die erste geschweifte Klammer der Term oberhalb des Bruchstriches und in die zweite der Term unterhalb des Bruchstriches.

Für eine Seminararbeit zu AES werte ich unter anderem auch Angriffe gegen den Algorithmus aus. Die Forscher Ferguson, Schroeppel und Whiting stellten 2001 in A simple algebraic representation of Rijndael (PDF) AES als Kettenbruch dar:

Wie macht man das mit LaTeX? Eigentlich ganz einfach! Man könnte den Ausdruck mittels \frac{}{} verschachteln. Das sieht aber recht unschön aus, da der Abstand im Nenner gleich bleibt und so die Ausrdrücke unlesbar werden. Das AMS-Paket bietet den Befehl \cfrac{}{} (steht für continued fractions). Damit kann man das obenstehende erreichen. In der erweiterten Ansicht des Artikels habe ich den kompletten Quelltext für obiges Beispiel.

Zum meinem Geburtstag bekam ich recht viele Bücher geschenkt. Eines davon war Der Mathematikverführer von Christoph Drösser. Das Buch hatte ich bereits vor einigen Wochen in einer Buchhandlung gesehen. Nach kurzem Durchblättern entschied ich mich damals gegen den Kauf.

Um was geht es? Der Autor erklärt mathematische Problemstellungen anhand praktischer Beispiele. Zunächst geht es um das Rechnen allgemein. Es wird erklärt, ob es sich für den Chef der Deutschen Bank lohnt, einen Fünf-Euro-Schein, der vor seiner Tür liegt, aufzuheben (Wenn er länger als fünf Sekunden für den Gang braucht, hat er in derselben Zeit mehr verdient), wieviele Hartz-IV-Empfänger von den Kosten eines Eurofighters bezahlt werden können etc. Das erste Kapitel bot für mich ein Aha-Erlebnis. Folgendes “Spiel” wird beschrieben:

Stellen Sie sich ­ [...] ­ folgendes Spiel vor: Jemand hat am Rand der Autobahn von Hamburg nach Berlin eine zwei Zentimeter breite und zwei Meter hohe Latte in den Boden geschlagen. Irgendwo zwischen Hamburg und Berlin, Sie haben keine Ahnung, wo. Sie fahren die Strecke nachts mit dem Auto und haben eine Pistole dabei. Zu einem beliebigen Zeitpunkt, den Sie frei wählen können, kurbeln Sie die Fensterscheibe herunter und schießen in Richtung Straßenrand. Einmal. Wenn Sie die Latte treffen, haben Sie gewonnen.

Das Spiel beschreibt natürlich die Lottovariante 6 aus 49. Ich denke, hiermit lässt sich vielen die Chance beim Lotto greifbar machen. Für einen Sechser mit Zusatzzahl muss es dann eine zwei Millimeter dicke Latte sein.

Das folgende Kapitel beschreibt bedingte Wahrscheinlichkeiten am Beispiel von DNA-Tests und es folgt ein Kapitel zum Dreisatz. Die Anordnung dieser wie auch anderer Kapitel könnte besser sein. Denn der Dreisatz ist vergleichsweise leichter Stoff. Immerhin wird der schon in der Schule behandelt. Wahrscheinlichkeiten kommen nach meiner Beobachtung als Schulstoff eher zu kurz und könnten daher von der Mehrzahl der Leser als schwieriges Thema beurteilt werden. Ich finde es besser, wenn sich der Schwierigkeitsgrad langsam steigert.

Die weiteren Kapitel bringen eine Einführung in das Gerrymandering, zum simpsonschen Paradoxon, zum Problem des Handlungsreisenden und einigem mehr. Die meisten der diskutierten Problemstellungen waren mir bekannt. Daher habe ich meist nur die Geschichte zur Einführung gelesen und die Erklärungen übersprungen. Die Geschichten fand ich recht unterhaltsam. Sie haben gut in das jeweilige Thema eingeführt und auch Interesse geweckt, was denn nun kommt. Die Stellen mit den Erklärungen, die ich las, hatten wieder den üblichen Mangel. Der Autor versuchte sämtliche ernsthafte Mathematik wegzulassen. Gerade bei den Extremwertaufgaben wurde irgendwo im Kleingedruckten der Lösungsweg präsentiert. Der eigentliche Text ließ diesen aus.

Insgesamt ist das Buch eine gute Zusammenstellung verschiedener mathematischer Phänomene. Die Geschichten zur Motivation sind gut geschrieben und ich kann mir gut vorstellen, dass das Buch bei einem Mathematikinteressierten mehr Interesse weckt. Diejenigen, die sich auch sonst mit Matheproblemen beschäftigen, wird das Buch wohl nicht vom Hocker hauen. Denn größtenteils steht Bekanntes drin.

In der Vorlesung Gruppentheorie wurde kürzlich das direkte Produkt von Gruppen definiert. Neben dem üblichen Produktzeichen ∏ verwendete der Vorlesende auch ein großes ×. Intuitiv verwendete ich bei meiner LaTeX-Mitschrift \bigtimes. Das resultierte im einem Fehler, da es dieses Zeichen in den eingebundenen Paketen nicht gab. Ein Blick in die The Comprehensive LaTeX Symbol List (PDF) sagte mir, dass es im Paket txfonts die Anweisung \varprod gibt und die Pakete MnSymbol sowie mathabx mein intuitiv gewähltes Zeichen vorrätig haben.

Da alle Varianten für mich mehr Nach- als Vorteile bringen, habe ein wenig gegoogelt und bin auf den Beitrag von Roland Illig gestossen. Seine Lösung baute ich mir zu \newcommand*{\bigtimes}{\mathop{\raisebox{-.5ex}{\hbox{\huge{$\times$}}}}} um. Das passt erstmal recht gut in meinen Text:

Falls jemand andere/bessere Lösungen weiß, dann immer her damit.

Meine Leser kennen sicher meine Vorliebe für das Project Euler. Bereits seit längerem beschäftigt mich das zwölfte Problem. Dort soll der Wert der ersten Dreieckszahl berechnet werden, die mehr als 500 Teiler hat. Im Rückblick betrachtet, ist diese Aufgabe relativ klar. Ich habe jedoch sehr viel Zeit daran verschwendet, das Problem zu verkomplizieren, theoretische Ober- und Untergrenzen zu berechnen. Nachdem ich nicht weiterkam, habe ich das Problem liegen lassen. Gerade eben kam es mir wieder in den Sinn. Als setzt ich mich hin und programmierte die Aufgabe einfach naiv und ohne Nachzudenken. Viola, das Ergebnis war richtig.

Bislang konnte ich die Eulerschen Probleme mit einem naiven Programmieransatz lösen. Das heißt, die erste Idee, die mir in den Kopf kam, schrieb ich runter und bekam eine Lösung. Das zehnte Problem warf mir einen Stock zwischen die Beine. Erstmals musste ich mir Gedanken über die Optimierung des Codes machen.

Das zehnte Problem klingt erstmal ganz harmlos: Finden Sie die Summen aller Primzahlen, die kleiner als 2 000 000 sind.. Ha, das ist ja eine einfache Fingerübung:

sieb = [ i for i in xrange(2,2000000) ]
for i in xrange(2,2000000):
  for j in xrange(2,2000000):
    if i*j in sieb:
      sieb.remove(i*j)

Die Werte in sieb müssen dann nur noch addiert werden und fertig. Jedoch kam ich gar nicht soweit. Denn das Programm lief und lief und lief.

Das brachte mich zum Nachdenken, woran das liegen könnte. Letztlich ist die Ursache offensichtlich. Denn der Code berechnet jedes Produkt. Dafür werden schon 2 000 000 * 2 000 000 = 4 000 000 000 000 Berechnungen durchgeführt. Wenn man von der (viel zu optimistischen) Variante ausgeht, dass jede Berechnung ein CPU-Zyklus ist, würde das Programm auf aktuellen Architekturen länger als eine halbe Stunde laufen. In der Realität lief es 15 Stunden. Wie lässt sich die Laufzeit nun verbessern?

Es ist recht offensichtlich, dass das Programm zuviel berechnet. Im ersten Schleifendurchlauf gibt es die Multiplikationen: 2*2, 2*3, 2*4, ..., 2*1999999 = 3999998. Beim zweiten Schleifendurchlauf: 3*2, 3*3, 3*4, ..., 3*1999999 = 5999997. Am klarsten fällt es im letzten Durchlauf auf: 1999999*2, 1999999*3, ..., 1999999*1999999 = 3999996000001. Die Berechnung 3*2 wurde schon im ersten Schritt (nur umgekehrt mit 2*3) durchgeführt. Hier wirkt das Kommutativgesetz. Also kann die Schleife im zweiten Durchlauf erst bei drei beginnen. Im dritten Durchlauf würde nach obigem Algorithmus 4*2, 4*3, 4*4 usw. berechnet werden. Verallgemeinert lässt sich also sagen, dass die Variable der zweiten Schleife genausogroß oder größer als die erste Variable sein muss. Dieser Schritt halbiert die Zahl der Berechnungen.

In der obigen Darstellung wird klar ersichtlich, dass das Programm nicht in jedem Fall bis zum Maximum von 2 000 000 laufen muss. Schon im ersten Durchlauf werden Werte über 2 000 000 berechnet. Das heißt, das Produkt i*j muss kleiner oder gleich 2 000 000 sein. Umformen nach j ergibt: j?2 000 000/i. Eine weitere oft genutzte Optimierung ist es, die erste Schleifenvariable nur bis ?2000000 laufen zu lassen.

Weiterhin fiel mir auch ein, dass man schon die initiale Liste nicht mit Zahlen von 2 bis 2 000 000 füllen muss. Denn es ist bekannt, dass alle Vielfachen von 2 sofort ausfallen. Man kann sogar soweit gehen, dass man nur Zahlen nach dem Muster 6*n-1 und 6*n+1 aufnimmt. Denn die Zahlen 6*n+0, 6*n+2 und 6*n+4 sind gerade und damit keine Primzahlen. Die Zahl 6*n+3 entspricht 3(2*n+1) und ist somit durch drei teilbar. Es verbleibt das obige Muster.

Theoretisch hätetn die obigen Anpassungen schon reichen sollen, um die Laufzeit unter eine Minute zu drücken. Jedoch lief das Programm immer nach weitaus länger. Nach einigem Stöbern fiel mir dann auf, dass in Python die Listenoperationen in und remove die Listen von Beginn an durchsuchen. Das bringt natürlich nochmal eine extreme Pessimierung der Laufzeit. Stattdessen sollte man hier Sets oder Dictionaries nutzen. Ich habe es mit Sets probiert und prompt lief das Programm schnell genug.

sieb = {}
for i in xrange(2, 2000000):
  sieb[i] = True
for x in xrange(2,int(math.sqrt(2000000))+1):
  if sieb[x] == True:
    for y in xrange(2000000/x, x-1,-1):
      t = x * y
      sieb[t] = False

Grundsätzlich lassen sich weitere Möglichkeiten der Optimierung ausdenken. Jedoch reichte mir das obige Ergebnis, um das Ziel zu erreichen. Wahrscheinlich benötige ich in späteren Aufgabe noch eine weitere Verbesserung.

Jetzt ist an den Unis Prüfungszeit ausgebrochen, so auch in Jena. Ich lerne gerade für die Vorlesung zu Funktionalanalysis oder, wie es hier heißt, Höhere Analysis. Zum Lernen habe ich mir ein paar Flashcards gebastelt. Wer das vielleicht ebenfalls zum Vorbereiten nutzen will, findet die Lernliste online.

Also dann: sei ε positiv und beliebig ...