Kettenbruch-Rechner
Dezimalzahlen in Kettenbrüche umwandeln, Konvergenten & beste rationale Näherungen finden
Geben Sie a₀ ein, danach a₁, a₂, ... — das erste Glied darf negativ sein, alle weiteren müssen positive ganze Zahlen sein.
Berühmte Kettenbrüche
Was ist ein Kettenbruch?
Ein Kettenbruch ist eine Möglichkeit, jede reelle Zahl als verschachtelte Folge von ganzzahligen Additionen und Kehrwerten darzustellen. Für eine Zahl x lautet die Kettenbruchform:
Notation: x = [a₀; a₁, a₂, a₃, ...]
Die ganzen Zahlen a₀, a₁, a₂, ... werden Partialnenner genannt. Das erste Glied a₀ = ⌊x⌋ ist der ganzzahlige Anteil (Gaußklammer bzw. Abrundungsfunktion) und kann eine beliebige ganze Zahl sein, auch negativ. Alle folgenden Glieder aₙ (n ≥ 1) sind stets positive ganze Zahlen.
Jede rationale Zahl besitzt einen endlichen Kettenbruch. Jede irrationale Zahl besitzt einen unendlichen Kettenbruch. Quadratische Irrationalzahlen (wie √2, √3, der Goldene Schnitt) haben periodische Kettenbrüche — die Partialnenner wiederholen sich irgendwann zyklisch. Das ist Lagranges berühmtes Theorem von 1770.
Wie wandelt man eine Dezimalzahl in einen Kettenbruch um?
Der Algorithmus ist eine unmittelbare Anwendung des euklidischen Algorithmus:
- Nimm x. Setze a₀ = ⌊x⌋ (Gaußklammer). Berechne den Rest r₀ = x − a₀.
- Ist r₀ ≈ 0, stoppe — x ist eine ganze Zahl oder die gewünschte Genauigkeit ist erreicht.
- Ersetze x durch 1/r₀. Setze a₁ = ⌊1/r₀⌋. Berechne r₁ = 1/r₀ − a₁.
- Wiederhole, bis der Rest unter eine kleine Toleranzgrenze fällt (z. B. 10⁻¹⁰).
Beispielrechnung: π ≈ 3.14159265358979
| Schritt n | Wert | aₙ = ⌊Wert⌋ | Rest |
|---|---|---|---|
| 0 | 3.14159265… | 3 | 0.14159265… |
| 1 | 1/0.14159… = 7.0625… | 7 | 0.06251… |
| 2 | 1/0.06251… = 15.9966… | 15 | 0.99659… |
| 3 | 1/0.99659… = 1.0034… | 1 | 0.0034… |
| 4 | 1/0.0034… = 292.63… | 292 | 0.63… |
Ergebnis: π = [3; 7, 15, 1, 292, 1, 1, 1, 2, ...]
Konvergenten verstehen
Die Konvergenten (auch Näherungsbrüche genannt) pₙ/qₙ erhält man, indem man den Kettenbruch bei jedem Schritt abbricht. Sie bilden die Folge der besten rationalen Näherungen an x. Die Rekursionsformeln lauten:
k₋₁ = 0, k₀ = 1, kₙ = aₙ · kₙ₋₁ + kₙ₋₂
Konvergente n: pₙ/qₙ = hₙ/kₙ
Die entscheidende Eigenschaft: Ist p/q ein Bruch mit q ≤ qₙ, dann gilt |x − pₙ/qₙ| ≤ |x − p/q|. Kein rationaler Bruch mit kleinerem Nenner liefert eine bessere Näherung. Für den Fehler gilt 1/(qₙ(qₙ₊₁+qₙ)) < |x − pₙ/qₙ| < 1/(qₙ·qₙ₊₁).
Konvergenten von π
| n | aₙ | pₙ (Zähler) | qₙ (Nenner) | pₙ/qₙ | Fehler |
|---|---|---|---|---|---|
| 0 | 3 | 3 | 1 | 3 | −0.14159… |
| 1 | 7 | 22 | 7 | 3.142857… | +0.00126… |
| 2 | 15 | 333 | 106 | 3.141509… | −0.0000832… |
| 3 | 1 | 355 | 113 | 3.1415929… | +2.67×10⁻⁷ |
| 4 | 292 | 103993 | 33102 | 3.14159265301… | −5.78×10⁻¹⁰ |
Beachten Sie den Sprung: 355/113 (Nenner 113) erreicht einen Fehler von ~2.67×10⁻⁷, während die nächste Konvergente (Nenner 33102) nur wegen des großen Partialnenners 292 auftaucht. Kein Bruch mit einem Nenner zwischen 114 und 33101 schlägt 355/113 bei der Näherung von π.
Berühmte Kettenbrüche und ihre Muster
Der Goldene Schnitt φ = [1; 1, 1, 1, ...]
Der Goldene Schnitt hat ausschließlich Partialnenner gleich 1 — den kleinstmöglichen Wert. Das bedeutet, jede Konvergente hₙ/kₙ ist so weit von φ entfernt, wie es die Theorie überhaupt zulässt, was φ zur „irrationalsten“ Zahl macht. Ihre Konvergenten sind Verhältnisse aufeinanderfolgender Fibonacci-Zahlen: 1/1, 2/1, 3/2, 5/3, 8/5, 13/8, 21/13, ... Die Fibonacci-Folge ergibt sich direkt aus der Rekursion mit allen aₙ = 1.
Eulersche Zahl e = [2; 1, 2, 1, 1, 4, 1, 1, 6, ...]
e besitzt ein wunderschönes Muster. Nach den ersten Gliedern ist jeder dritte Partialnenner 2, 4, 6, 8, ... (die geraden Zahlen), wobei die Lücken mit Einsen gefüllt werden. Diese elegante Regelmäßigkeit wurde von Euler selbst entdeckt und liefert die kompakteste geschlossene Beschreibung des Kettenbruchs von e.
√2 = [1; 2, 2, 2, ...]
Die Quadratwurzel aus 2 ist der einfachste periodische Kettenbruch jenseits des trivialen Falls. Ihre Konvergenten 1/1, 3/2, 7/5, 17/12, 41/29, ... sind die Pell-Zahlen, die die Gleichung p² − 2q² = ±1 lösen. Die antiken Griechen nutzten diese Näherungen bei ihrer Untersuchung inkommensurabler Größen.
Anwendungen von Kettenbrüchen
- Kalenderberechnung: Die 97 Schaltjahre in 400 Jahren des gregorianischen Kalenders ergeben sich aus Konvergenten des tropischen Jahres. Die Näherung 1/4 = [0; 4] des julianischen Kalenders wurde durch bessere Konvergenten ersetzt.
- Zahnradübersetzungen: Ingenieure nutzen Konvergenten, um Zähnezahlen zu finden, die ein Zielübersetzungsverhältnis mit ganzzahligen Randbedingungen annähern.
- Musiktheorie: Die gleichstufig temperierte Zwölftonskala ergibt sich aus Kettenbruch-Näherungen an log₂(3/2). Die Konvergenten liefern 3-, 5-, 7-, 12-, 17-, 29-, 41- und 53-tönige Skalen.
- Kryptografie: Der Wiener-Angriff auf RSA nutzt Kettenbrüche, um einen RSA-Modulus zu faktorisieren, wenn der private Exponent klein ist.
- Stern-Brocot-Baum: Der Stern-Brocot-Baum ordnet alle positiven rationalen Zahlen an — das Navigieren über Links-/Rechts-Entscheidungen entspricht dem Ablesen eines Kettenbruchs ab der Wurzel.
- Diophantische Approximation: Kettenbrüche stehen im Zentrum von Hurwitz' Theorem und Roths Theorem, die quantifizieren, wie gut sich irrationale Zahlen durch rationale Zahlen annähern lassen.