Nicht-triviale praktische Algorithmen

More about the book

Eine der in der Praxis am häufigsten verwendeten Aufgaben ist die Berechnung des größten gemeinsamen Teilers. In der heutigen Zeit geben wir eine neue Behandlung dieses wissenschaftlichen Zweiges. Aus historischen Quellen ist bekannt, dass der griechische Mathematiker Euklid ein solches Iterationsverfahren beschreibt. Seine ursprüngliche Beschreibung verwendet die arithmetische Operation "Differenz". Viele Jahre später, als numerische Methoden und insbesondere Computer entwickelt wurden, gibt Knuth einen Computeralgorithmus zur Berechnung des größten gemeinsamen Teilers mit Hilfe der Operation "Rest" an. Schnellere Algorithmen können durch die Kombination von zwei Ansätzen erzielt werden, wie z. B. der Algorithmus des kleinsten absoluten Restes, der Stein'sche Algorithmus, der Harris'sche Algorithmus und der Tembhurne-Sathe'sche Algorithmus. Unsere Untersuchungen zeigen, dass die besten Rechenergebnisse durch die in diesem Buch vorgestellten neuen Realisierungen des Algorithmus des kleinsten absoluten Restes für reguläre ganze Zahlen und des Tembhurne-Sathe-Algorithmus für lange ganze Zahlen erzielt werden.