Pisano-Periode

Der Pisano-Perioden-Rechner ermittelt, wie viele Fibonacci-Reste auftreten, bevor sich die Folge für einen gewählten positiven Modulus wiederholt. Statt beliebig viele Fibonacci-Terme zu erzeugen, verfolgt er aufeinanderfolgende Restpaare bis zur Rückkehr des eindeutigen Anfangszustands und gibt dann die Zykluslänge aus. Das ist in der modularen Arithmetik, bei Programmierwettbewerben, in der Rekurrenzanalyse und in Algorithmen zur sicheren Reduktion sehr großer Fibonacci-Indizes nützlich. Geben Sie einen Modulus von 1 bis 1,000,000 ein, um ein exaktes, deterministisches Ergebnis zu erhalten.

Was eine Pisano-Periode misst

Die Fibonacci-Folge beginnt mit 0, 1, 1, 2, 3, 5 und wird durch Addition der beiden vorherigen Terme fortgesetzt. Wird jeder Term modulo m genommen, ersetzt man jede Fibonacci-Zahl durch ihren Rest bei Division durch m. Da nur endlich viele geordnete Restpaare möglich sind, wiederholt sich diese abgeleitete Folge schließlich.

Bei Fibonacci-Resten führt die Wiederholung zum Anfangspaar zurück; die Anzahl der Schritte bis zu dieser Rückkehr heißt Pisano-Periode. Modulo 2 lauten die Reste beispielsweise 0, 1, 1, danach beginnt das Muster erneut. Die Periode beträgt daher 3.

Modulo 10 beträgt sie 60, was erklärt, warum sich die Endziffern von Fibonacci-Zahlen alle 60 Positionen wiederholen. Dieser Rechner liefert die Zykluslänge selbst, weder eine Liste der Reste noch einen Fibonacci-Term. Der Sondermodulus 1 kennt nur den Rest 0, daher besitzt seine Folge mit einem einzigen Zustand die Periode 1.

Jede unterstützte Berechnung verwendet exakte Ganzzahlarithmetik; Näherungen, Stichproben oder probabilistische Tests kommen nicht zum Einsatz.

Wie der Rechner den Zyklus erkennt

Ein Fibonacci-Wert hängt von den beiden unmittelbar vorherigen Werten ab. Ein einzelner wiederholter Rest reicht deshalb nicht als Beleg dafür, dass die gesamte Folge neu begonnen hat. Der Rechner verfolgt stattdessen ein geordnetes Paar aufeinanderfolgender Reste.

Er startet mit 0 und 1, ersetzt das Paar wiederholt durch das nächste modulare Fibonacci-Paar und zählt jeden Übergang. Sobald das geordnete Paar 0, 1 erneut erscheint, entspricht der Zähler der Pisano-Periode. Diese paarweise Prüfung verhindert falsche Stopps, die entstehen könnten, wenn die Implementierung nur auf eine Null oder einen beliebigen wiederholten Einzelrest achtete.

Der Speicherbedarf bleibt konstant, weil nur das aktuelle Paar und ein Zähler benötigt werden; der gesamte Zyklus wird nicht gespeichert. Der Modulus ist auf 1,000,000 begrenzt, damit die Laufzeit einer interaktiven Anfrage ausdrücklich beschränkt bleibt. Eingaben müssen positive Ganzzahlen sein.

Dezimalbrüche, nicht numerische Zeichenketten, null, negative Werte und Werte oberhalb der veröffentlichten Grenze werden abgewiesen, statt gerundet oder stillschweigend geändert zu werden.

Das Ergebnis in modularen Fibonacci-Berechnungen verwenden

Sobald die Periode p bekannt ist, können Sie Fibonacci-Indizes modulo p reduzieren, wenn nur der Wert modulo m zählt: F(n) mod m ist gleich F(n mod p) mod m. Diese Identität wandelt einen riesigen Index vor einer Berechnung mit schneller Verdopplung oder Matrixpotenzierung in einen wesentlich kleineren gleichwertigen Index um. Das ist besonders hilfreich, wenn ein Index als sehr lange Dezimalzeichenkette vorliegt, eine Rekurrenz in einer kryptografischen Aufgabe vorkommt oder eine Programmieraufgabe nur nach den Endziffern fragt.

Halten Sie die Aufgaben der beiden Moduln getrennt: m bestimmt die Fibonacci-Reste, während die ausgegebene Pisano-Periode die Indexreduktion bestimmt. Eine Periode ist im Allgemeinen nicht gleich m, und Perioden zusammengesetzter Moduln spiegeln das Zusammenspiel ihrer Primzahlpotenzfaktoren wider. Es gibt keine Gebühr pro Term, und der Algorithmus greift weder auf das Netzwerk noch auf externe Daten zu.