ForschungParalleles Rechnen in der ZahlentheorieMultiplikationDie Multiplikation ist eine der wichtigsten Routinen unseres für massiv parallele Rechner entwickelten Programmpakets.Die Hypercube-Struktur ist ideal für unseren auf der Fouriertransformation basierenden Multiplikationsalgorithmus. Wegen ihrer geringen Kommunikationsanforderungen wird die Fermatzahl-Transformation verwendet. Dabei erfolgen die Teilberechnungen modulo einer Fermatzahl. Die Multiplikation besteht nach der Zerlegung der Eingabe in digits aus der Fouriertarnsformation, der digit-by-digit Multiplikation, der inversen Fouriertransformation und der Normalisation. Die Abbildung zeigt den Datenfluß während der
Fouriertransformation, der digit-by-digit Multiplikation und der inversen
Fouriertransformation.
Kommunikation bei der Fouriertransformation
Das Waring'sche ProblemTheoretischer HintergrundIm Jahre 1770 behauptete E. Waring, daß man jede natürliche Zahl als Summe von vier Quadraten, von neun Cuben, von neunzehn Biquadraten, usw. darstellen kann. Bezeichne g(k) die kleinste Zahl n, so daß sich jede ganze Zahl als Summe von n ganzen nichtnegativen Zahlen darstellen läßt, die k-te Potenzen sind. 1772 fand J. A. Euler eine untere Schranke für g(k), nämlich g(k) >= [ 3k / 2k] + 2k - 2. Hilbert zeigte 1909, daß g(k) für jedes k endlich ist. Ein Ergebnis von L. E. Dickson und Pillai von 1935 ermöglicht, daß man eine strenge Form der Waring'schen Vermutung g(k) = [ 3k / 2 k] + 2k - 2 mit Hilfe von Rechnern überprüfen kann.Resultate1964 wurde g(k) = [ 3k / 2k] + 2k - 2 für k <= 200.000 auf einen IBM 7090 mit einer Rechenzeit von 240 Stunden von R. M. Stemmler bewiesen. 1988 hat M. C. Wunderlich die Vermutung auf einer 65536-Prozessor-Maschine für k <= 175.000.000 nachgeprüft. 1990 hat Kubina mit Hilfe einer speed-up Methode von J. R. Deshouillers und J. Selfridge die Vermutung für alle k <= 471.000.000 untersucht.1995 konnten wir auf der massiv parallelen GCel-Architektur mit 1024
Transputern im Paderborn Center for Parallel
Computing - unter Verwendung unserer Multiplikationsroutinen - die
Waring'sche Vermutung für k <= 5.368.709.120 bestätigen.
Die Rechenzeit betrug ca. 4 Stunden.
Resultate aus dem Projekt: "Massive parallele Rechner in der Computational Number Theory". |