Segmentierung und Optimierung von Algorithmen zu Problemen aus der Zahlentheorie

Abstract

Die vorliegende Arbeit beschäftigt sich mit der Entwicklung und Optimierung verteilter Algorithmen zu Problemen aus der Zahlentheorie. Speziell werden vierProbleme behandelt. Zur Vorbereitung auf die Bewertung der jeweils vorzustellenden Algorithmen wird in Kapitel 1 zunächst ein neues Berechnungsmodellentwickelt, das bestehende Modelle um in der Praxis relevante Eigenschaften erweitert und die formale Grundlage sämtlicher Verfahren darstellt. Berücksichtigtwerden dabei sowohl Unterschiede in den Komplexitäten verschiedener Operationen als auch Kosten für Speicherzugriffe. Beides hat in der Praxisentscheidenden Einfluß auf die Gesamtkomplexität der Implementierungen von Algorithmen. Der Grundaufbau des Modells wird zunächst formal definiert, denInstruktionen der Modellmaschine dann Kosten zugeordnet. Es folgt die Einführung einer Sprache zur Algorithmenbeschreibung. Diese wird schließlich zum Zwecke der Analyse der folgenden Verfahren durch Angabeeines übersetzers in Modellmaschinen-Instruktionen auf das Berechnungsmodell zurückgeführt. Sämtliche vorzustellenden Algorithmen werden anhand derBeschreibungssprache erläutert und mit dem vorher geschaffenen Komplexitätsmaß bewertet. Diese Vorgehensweise läßt eine wesentlich realistischereBewertung der Komplexitäten zu als es in herkömmlichen Modellen möglich gewesen wäre. Eine 'Tauglichkeitsuntersuchung' des entstandenenKomplexitätsmaßes für Programme über dieser Sprache wird im Zusammenhang des nachfolgenden Kapitels durchgeführt. Kapitel 2 beschäftigt sich mit Primzahl-Sieben, also Algorithmen zur Trennung zerlegbarer Zahlen von Primzahlen eines gegebenen Intervalls. Die Basis stelltdabei das über 2000 Jahre alte Sieb des Eratosthenes dar. Zunächst werden daran einige einfache Verbesserungen vorgenommen. An der Analyse der darausresultierenden Verfahren zeigt sich, daß selbst feine Unterschiede durch das Komplexitätsmaß der Beschreibungssprache erfaßt werden können. In einemnächsten Schritt findet dann zur Vorbereitung auf eine spätere Verteilung die Segmentierung des Basissiebes statt. Der Begriff der Segmentierung, der imBereich der Primzahlsiebe eine gewisse Tradition hat, wird in dieser Arbeit übernommen. Er ist zum einen als theoretische Vorstufe zu einer praktischenVerteilung zu verstehen und soll zum anderen vom Begriff der Partitionierung abgrenzen, unter der man häufig eine disjunkte Zerlegung versteht, die hier nichtimmer gemeint sein muß. Ausgehend von einer ersten segmentierten Version werden schrittweise Verbesserungen entwickelt, die schließlich in einem hochoptimierten Verfahren münden.Es wird gezeigt, daß dieses trotz seiner asymptotisch schlechteren Laufzeit unter realistischen Bedingungen andere Algorithmen übertrifft. Eine Implementierungdes resultierenden Primzahlsiebes wird beschrieben. Dabei wurde auf möglichst weitreichende Parametrisierbarkeit geachtet, die sich in späteren Anwendungenzum Teil erheblich auswirkt. In Kapitel 3 wird eine (Teil-) Verifikation der inzwischen über 250 Jahre alten Goldbachschen Vermutung vorgenommen. Dabei handelt es sich um die Frage,ob sich jede gerade Zahl größer oder gleich 4 als Summe zweier Primzahlen darstellen läßt. Trotz der Einfachheit ihrer Formulierung zählt man einen möglichenBeweis der Goldbachschen Vermutung zu den schwierigsten Problemen der gesamten Mathematik überhaupt. Es werden zunächst zwei Methoden zur Verifikation beschrieben sowie deren Vor- und Nachteile aufgezeigt. Aus diesen Überlegungen folgt die Auswahl einesder beiden Verfahren. Laufzeitkritische Punkte konnten durch mehrere Optimierungen entscheidend verbessert werden. Der resultierende Algorithmus wurdeimplementiert und schließlich verteilt. Das Ergebnis der Rechnung - die Verifikation bis 4x1014 - stellt eine Ausdehnung des bisher bestätigten Bereichs auf dasVierfache dar. Eine Erweiterung des Goldbachschen Problems ist die Frage nach der Anzahl der Zerlegungen gerader Zahlen als Summe zweier Primzahlen. Das Problem derBestimmung dieser Anzahl läßt sich durch einen sequentiellen Algorithmus eigentlich sehr einfach lösen. Allerdings stößt das Verfahren in der Praxis schnell anseine Grenzen, die vor allem aus dem Mangel an zur Verfügung stehendem Hauptspeicher resultieren. Es wird zunächst gezeigt, daß durch eine Segmentierungdes Basisverfahrens ein Minimum an Speicher genügt. Allerdings führt die beschriebene Vorgehensweise zunächst zu einer deutlichen Erhöhung derZeitkomplexität, die jedoch praktisch durch die sich automatisch ergebende Verteilbarkeit aufgefangen werden kann. Das Ergebnis der verteilten Berechnung -der Bestimmung der Anzahlen der Partitionen aller geraden Zahlen bis 5x108 - wird schließlich verschiedenen historischen Vermutungen über das Wachstumder Anzahl der Partitionen gegenübergestellt. Kapitel 5 stellt ein Verfahren zur verteilten Suche nach modulo p verschwindenden Fermat-Quotienten zur Basis a für prime a und p vor. Die dazu äquivalenteFrage der Lösbarkeit der Kongruenz ap-1 = 1 mod p2 wurde erstmals vor etwa 170 Jahren von N. Abel aufgeworfen. Sie steht in engem Zusammenhang mitdem (inzwischen von A. Wiles bewiesenen) letzten Satz von Fermat . Über die Lösungen der Kongruenz oder ihrer Struktur ist relativ wenig bekannt. Es wirdzunächst ein einfacher Algorithmus beschrieben, der jedoch in der Praxis entscheidende Nachteile aufweist. Selbst nach der Ersetzung einiger problematischerStellen verbleiben praktische Schwierigkeiten, die nur durch eine recht komplizierte, aber letztendlich erfolgreiche Vorgehensweise behoben werden können. Das resultierende und schließlich implementierte und verteilte Verfahren zeigt eine praktische Schranke für eine im Berechnungsmodell getroffene Idealisierungauf, die trotz der relativ umständlichen Methode nicht durchbrochen werden mußte. Die getroffene Idealisierung erfährt damit eine weitere Rechtfertigung.Durch eine maschinennahe Implementierung und Verteilung konnten bisherige Berechnungen zum Problem der Fermat-Quotienten um das etwa zwölffacheerweitert werden. Die für alle primen a<1000 und p<1011 durchgeführte Rechnung lieferte acht neue Lösungen, darunter eine, die die erste Lösung zur Basisa=929 darstellt. Abschließend wird eine Softwareimplementierung zur Steuerung verteilter Rechnungen vorgestellt. Dabei werden sowohl vernetzte Systeme mit oder ohnegemeinsamem Speicher unterstützt als auch einzelne Rechner eingebunden, die nur teilweise netzverbunden sind oder auch völlig getrennt arbeiten. Durch dierelativ schlanke Struktur und einfache Konfigurierbarkeit ist es prinzipiell möglich, weltweite Rechnerressourcen in eine verteilte Rechnung einzubinden.Netzkommunikationen werden dabei weitestgehend vermieden, um eine Abhängigkeit von zentralen Servern zu vermeiden. Sämtliche Rechnungen wurdenunter Verwendung dieser Software auf relativ kleinen Rechnern an unterschiedlichen Standorten durchgeführt.