Zum Inhalt springen
Topos Uranos
Deutsch

Numerische Algorithmen

Zusammenfassung

Die vorigen Lektionen der Einheit haben gelehrt, Schleifen zu schreiben und mit einer Invariante und einer Variante über sie zu argumentieren; diese Lektion wendet diese Überlegungen auf vier klassische numerische Algorithmen an, die älter sind als die Computer und noch immer im Gebrauch. Der Primzahltest durch Probedivision, der aus einem Grund, der bewiesen wird, bei n\sqrt{n} aufhört und dessen Abbruchbedingung überläuft, wenn man sie nachlässig schreibt. Der euklidische Algorithmus für den größten gemeinsamen Teiler, mit seiner Invariante, seiner Terminierung, seiner Falle bei negativen Zahlen und seinem Vergleich mit std::gcd. Der Basiswechsel durch fortgesetzte Division und das Horner-Schema, das eine Zahl aus ihren Ziffern wieder aufbaut und ein Polynom nach demselben Schema auswertet. Und die Bisektion (Intervallhalbierung), die eine Nullstelle annähert, indem sie ein Intervall in zwei Hälften teilt, abgesichert durch den Zwischenwertsatz, mit einer Zahl von Durchläufen, die man im Voraus berechnet. Jeder Algorithmus wird als mathematisches Objekt vorgestellt: mit einem Beweis, dass er tut, was er verspricht, einem Beweis, dass er terminiert, und einer ersten Zählung seiner Schritte.

Lernziele

  1. Den Primzahltest durch Divisionen bis n\sqrt{n} implementieren und begründen, warum es genügt, bis n\sqrt{n} zu gehen.
  2. Den euklidischen Algorithmus implementieren, seine Invariante angeben (der größte gemeinsame Teiler ändert sich nicht) und ihn mit std::gcd vergleichen.
  3. Eine Zahl durch fortgesetzte Division in eine andere Basis umrechnen und eine Stellenwertdarstellung oder ein Polynom mit dem Horner-Schema auswerten.
  4. Eine Nullstelle mit der Bisektion bis auf eine Toleranz annähern und berechnen, wie viele Iterationen sie erfordert.

Teiler und Primzahlen

Probedivision

Eine ganze Zahl n≥2n \geq 2 ist eine Primzahl, wenn ihre einzigen positiven Teiler 1 und nn sind; hat sie einen anderen, ist sie zusammengesetzt; 0 und 1 sind weder das eine noch das andere. Die Definition legt sofort einen Algorithmus nahe: jeden Kandidaten dd zwischen 2 und n−1n - 1 durchprobieren und die Zahl für zusammengesetzt erklären, sobald einer sie teilt. Das ist die Schleife des kleinsten Teilers aus der Lektion Schleifen, und sie ist korrekt. Für eine zehnstellige Primzahl führt sie jedoch fast zehn Milliarden Divisionen aus, und fast alle sind nutzlos, aus folgendem Grund.

PropositionEs genügt, bis n\sqrt{n} zu prüfen

Ist n≥2n \geq 2 zusammengesetzt, so hat sie einen Teiler dd mit 2≤d≤n2 \leq d \leq \sqrt{n}.

Beweis

  1. n=a⋅b,2≤a≤bn = a \cdot b, \quad 2 \leq a \leq b

    Ist nn zusammengesetzt, so lässt sie sich als Produkt zweier Faktoren schreiben, von denen keiner gleich 1 oder nn ist. Mit aa wird der kleinere der beiden bezeichnet.

  2. a2≤a⋅b=na^2 \leq a \cdot b = n

    Multipliziert man a≤ba \leq b mit der positiven Zahl aa, erhält man a2≤ab=na^2 \leq ab = n, woraus a≤na \leq \sqrt{n} folgt: Der kleinere Faktor jeder Faktorisierung liegt links von n\sqrt{n}.

  3. d≤n  ⟺  nd≥nd \leq \sqrt{n} \iff \frac{n}{d} \geq \sqrt{n}

    Die Teiler treten also in Paaren (d,n/d)(d, n/d) auf, gespiegelt um n\sqrt{n}: Mit n=36n = 36 sind die Paare (2,18)(2, 18), (3,12)(3, 12), (4,9)(4, 9) und (6,6)(6, 6). Teilt kein Kandidat bis n\sqrt{n} die Zahl nn, so teilt sie auch keiner darüber hinaus, denn sein Partner wäre vorher aufgetreten.

Daraus folgt, dass die Zahl der Divisionen von etwa nn auf etwa n\sqrt{n} sinkt: für nn nahe zwei Milliarden von zwei Milliarden auf sechsundvierzigtausend. Das Programm verwendet das Flag-Muster aus der Lektion Korrekte Schleifen entwerfen: isPrime beginnt mit wahr, und die Schleife schaltet es aus, wenn sie einen Teiler findet.

C++-Programm
#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{} ist eine Primzahl", n);    } else {        std::println("{} ist keine Primzahl", n);    }}
Programmeingabe
2147483647
Ausgabe
2147483647 ist eine Primzahl

Drei Entscheidungen verdienen einen Kommentar. Das Flag wird mit n >= 2 initialisiert, sodass 0, 1 und die negativen Zahlen ohne Eintritt in die Schleife für keine Primzahl erklärt werden: Diesen Fall zu vergessen ist der typische Fehler, denn mit n=1n = 1 macht die Schleife keinen Durchlauf, und das Programm würde die 1 für eine Primzahl erklären. Die Bedingung des for hat zwei Teile: das Flag, das die Schleife beim ersten Teiler anhält, und die Schranke. Und die Schranke ist als d <= n / d geschrieben, was für positive ganze Zahlen zu d2≤nd^2 \leq n äquivalent ist (die ganzzahlige Division schneidet ab, aber dd übersteigt den abgeschnittenen Quotienten genau dann nicht, wenn es n/dn/d nicht übersteigt, weil dd ganzzahlig ist). Die Zahl der Eingabe, 231−12^{31} - 1, ist der größte int-Wert und eine Primzahl; das Programm entscheidet dies mit 46 33946\,339 Resten, denen der Kandidaten von 2 bis 46 34046\,340.

Die Schleifeninvariante lautet: Keine ganze Zahl von 2 bis d−1d - 1 teilt nn, solange das Flag wahr bleibt. Sie gilt beim Eintritt, wenn das Intervall von 2 bis 1 leer ist; sie bleibt erhalten, denn wenn dd die Zahl nn nicht teilt, wächst das Intervall um eine Zahl, die sie nicht teilt; und beim Austritt mit wahrem Flag sagen die Invariante und die falsche Bedingung, d2>nd^2 > n, zusammen, dass kein Kandidat bis n\sqrt{n} die Zahl nn teilt, und genau das verlangt der Satz. Die Variante ist die Anzahl der noch zu prüfenden Kandidaten, das heißt der ganzen Zahlen zwischen dd und n\sqrt{n}: Sie sinkt um eins pro Durchlauf und fällt nicht unter null.

Die Bedingung, die überläuft

Die natürliche Art, die Schranke zu schreiben, ist d * d <= n, und sie ist ein Fehler. Mit der vorigen Eingabe erreicht die Schleife d=46 341d = 46\,341, und dann übersteigt das Produkt 46 3412=2 147 488 28146\,341^2 = 2\,147\,488\,281 das Maximum von int.

C++-Programm
#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("Primzahl? {}", isPrime);}
Programmeingabe
2147483647
Ausgabe
main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

Das Programm endete mit dem Code 1.

Der Sanitizer für undefiniertes Verhalten hält das Programm beim Produkt an. Ohne ihn ist der vorzeichenbehaftete Überlauf undefiniertes Verhalten, und der Standard sagt nicht, was geschieht. Was man mit GCC unter Linux beobachtet, mit und ohne Optimierung, ist lehrreich: Das Produkt schlägt um und wird negativ oder kleiner als nn, und da kein int das Maximum übersteigt, hört die Bedingung d * d <= n nie mehr auf, erfüllt zu sein; die Schleife prüft rund zwei Milliarden Durchläufe lang Kandidaten, bis sie d=nd = n erreicht, das nn teilt, und das Programm erklärt eine Primzahl für zusammengesetzt. Ein Überlauffehler zeigt sich nicht als Überlauf, sondern als falsche Antwort. Die Form d <= n / d kann nicht überlaufen, weil sie dividiert, statt zu multiplizieren; die Lektion Bits und Mathematikbibliothek bot einen anderen Ausweg, die Schranke einmal mit std::sqrt zu berechnen, aber dann hängt die Genauigkeit der Schranke von der Gleitkommarundung ab, und die ganzzahlige Division hat dieses Problem nicht.

Die Lektion „Primzahlen und der Fundamentalsatz der Arithmetik“ aus dem Kurs Algebra und Geometrie I beweist, dass jede ganze Zahl größer als 1 auf genau eine Weise ein Produkt von Primzahlen ist; die Probedivision ist der direkteste Weg, dieses Produkt zu finden, indem man nn durch jeden gefundenen Teiler dividiert und mit dem Quotienten fortfährt.