Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-738
URL: http://geb.uni-giessen.de/geb/volltexte/1999/73/


Segmentierung und Optimierung von Algorithmen zu Problemen aus der Zahlentheorie

Richstein, Jörg


pdf-Format: Dokument 1.pdf (10.541 KB)
ps gepackt: class="frontdoor">Dokument1.gz (5,388 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Sprache: Deutsch
Tag der mündlichen Prüfung: 06.08.1999
Erstellungsjahr: 1999
Publikationsdatum: 10.08.1999
Kurzfassung auf Deutsch: Die vorliegende Arbeit beschäftigt sich mit der Entwicklung und Optimierung verteilter Algorithmen zu Problemen aus der Zahlentheorie. Speziell werden vier
Probleme behandelt. Zur Vorbereitung auf die Bewertung der jeweils vorzustellenden Algorithmen wird in Kapitel 1 zunächst ein neues Berechnungsmodell
entwickelt, das bestehende Modelle um in der Praxis relevante Eigenschaften erweitert und die formale Grundlage sämtlicher Verfahren darstellt. Berücksichtigt
werden dabei sowohl Unterschiede in den Komplexitäten verschiedener Operationen als auch Kosten für Speicherzugriffe. Beides hat in der Praxis
entscheidenden Einfluß auf die Gesamtkomplexität der Implementierungen von Algorithmen. Der Grundaufbau des Modells wird zunächst formal definiert, den
Instruktionen 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 Angabe
eines übersetzers in Modellmaschinen-Instruktionen auf das Berechnungsmodell zurückgeführt. Sämtliche vorzustellenden Algorithmen werden anhand der
Beschreibungssprache erläutert und mit dem vorher geschaffenen Komplexitätsmaß bewertet. Diese Vorgehensweise läßt eine wesentlich realistischere
Bewertung der Komplexitäten zu als es in herkömmlichen Modellen möglich gewesen wäre. Eine 'Tauglichkeitsuntersuchung' des entstandenen
Komplexitä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 stellt
dabei das über 2000 Jahre alte Sieb des Eratosthenes dar. Zunächst werden daran einige einfache Verbesserungen vorgenommen. An der Analyse der daraus
resultierenden Verfahren zeigt sich, daß selbst feine Unterschiede durch das Komplexitätsmaß der Beschreibungssprache erfaßt werden können. In einem
nächsten Schritt findet dann zur Vorbereitung auf eine spätere Verteilung die Segmentierung des Basissiebes statt. Der Begriff der Segmentierung, der im
Bereich der Primzahlsiebe eine gewisse Tradition hat, wird in dieser Arbeit übernommen. Er ist zum einen als theoretische Vorstufe zu einer praktischen
Verteilung zu verstehen und soll zum anderen vom Begriff der Partitionierung abgrenzen, unter der man häufig eine disjunkte Zerlegung versteht, die hier nicht
immer 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 Implementierung
des resultierenden Primzahlsiebes wird beschrieben. Dabei wurde auf möglichst weitreichende Parametrisierbarkeit geachtet, die sich in späteren Anwendungen
zum 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öglichen
Beweis 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 eines
der beiden Verfahren. Laufzeitkritische Punkte konnten durch mehrere Optimierungen entscheidend verbessert werden. Der resultierende Algorithmus wurde
implementiert und schließlich verteilt. Das Ergebnis der Rechnung - die Verifikation bis 4x1014 - stellt eine Ausdehnung des bisher bestätigten Bereichs auf das
Vierfache dar.


Eine Erweiterung des Goldbachschen Problems ist die Frage nach der Anzahl der Zerlegungen gerader Zahlen als Summe zweier Primzahlen. Das Problem der
Bestimmung dieser Anzahl läßt sich durch einen sequentiellen Algorithmus eigentlich sehr einfach lösen. Allerdings stößt das Verfahren in der Praxis schnell an
seine Grenzen, die vor allem aus dem Mangel an zur Verfügung stehendem Hauptspeicher resultieren. Es wird zunächst gezeigt, daß durch eine Segmentierung
des Basisverfahrens ein Minimum an Speicher genügt. Allerdings führt die beschriebene Vorgehensweise zunächst zu einer deutlichen Erhöhung der
Zeitkomplexitä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 Wachstum
der 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 äquivalente
Frage 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 mit
dem (inzwischen von A. Wiles bewiesenen) letzten Satz von Fermat . Über die Lösungen der Kongruenz oder ihrer Struktur ist relativ wenig bekannt. Es wird
zunächst ein einfacher Algorithmus beschrieben, der jedoch in der Praxis entscheidende Nachteile aufweist. Selbst nach der Ersetzung einiger problematischer
Stellen 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 Idealisierung
auf, 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ölffache
erweitert 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 Basis
a=929 darstellt.


Abschließend wird eine Softwareimplementierung zur Steuerung verteilter Rechnungen vorgestellt. Dabei werden sowohl vernetzte Systeme mit oder ohne
gemeinsamem Speicher unterstützt als auch einzelne Rechner eingebunden, die nur teilweise netzverbunden sind oder auch völlig getrennt arbeiten. Durch die
relativ 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 wurden
unter Verwendung dieser Software auf relativ kleinen Rechnern an unterschiedlichen Standorten durchgeführt.