Pellsche Gleichung

Geben Sie D ein, um das kleinste positive ganzzahlige Paar x und y zu erhalten, das die Gleichung erfüllt. Die Berechnung verwendet exakte Ganzzahlarithmetik. Deshalb bleiben auch Ergebnisse korrekt, die den gewöhnlichen Zahlenbereich von JavaScript überschreiten. Das Werkzeug eignet sich für Aufgaben aus der Zahlentheorie, das Studium von Kettenbrüchen, Algorithmustests und Software, die eine zuverlässige kanonische Pell-Lösung benötigt.

Was die Fundamentalslösung bedeutet

Für eine feste positive ganze Zahl D, die keine Quadratzahl ist, sucht die Pellsche Gleichung ganzzahlige Werte mit x² − Dy² = 1. Es gibt unendlich viele positive Lösungen, doch sie entstehen aus einem einzigen kleinsten nicht trivialen Paar. Dieser Rechner gibt genau dieses Paar zurück, die sogenannte Fundamentalslösung: x und y sind positiv, die Identität gilt exakt und kein kleineres positives x löst dieselbe Gleichung. Für D = 2 ergibt sich beispielsweise x = 3 und y = 2, weil 3² − 2 × 2² gleich 1 ist. Die Eingabe muss eine ganze Zahl zwischen 2 und 10,000,000 sein. Eine Quadratzahl D wird abgelehnt, da sich x² − Dy² als (x − √D y)(x + √D y) faktorisieren lässt und keine positive Lösung mit y größer als null existiert. Die Ergebnisse werden als Dezimalzeichenfolgen statt als Gleitkommazahlen ausgegeben. So bleibt jede Ziffer erhalten, wenn die Fundamentalslösung unerwartet groß ist, was bereits bei einigen mäßigen D-Werten vorkommt. Sie können die Antwort daher ohne vorheriges Runden in ein Computeralgebrasystem oder eine Bibliothek für beliebige Genauigkeit übernehmen.

Wie Kettenbrüche die Antwort bestimmen

Der Algorithmus entwickelt √D in einen periodischen einfachen Kettenbruch. Dessen Näherungsbrüche liefern zunehmend genaue rationale Approximationen p/q für √D. Schließlich erfüllen Zähler und Nenner eines Näherungsbruchs die Beziehung p² − Dq² = 1. Der Rechner aktualisiert den Kettenbruchzustand und beide Rekursionen der Näherungsbrüche mit deterministischen Ganzzahloperationen. Nach jedem Schritt prüft er die Pell-Identität mittels BigInt-Arithmetik und gibt sofort die erste positive Lösung zurück. Dieser erste passende Näherungsbruch ist die Fundamentalslösung. Das Werkzeug muss daher weder beliebige Paare ganzer Zahlen durchsuchen noch einen Bereich für x und y erraten. Die Iterationszahl gibt an, wie viele Näherungsbrüche einschließlich des anfänglichen ganzzahligen Anteils von √D geprüft wurden. Damit können Sie Periodenlängen vergleichen oder die Leistung untersuchen; das mathematische Ergebnis ändert sich dadurch nicht. Bei der abschließenden Identitätsprüfung kommt keine numerische Näherung zum Einsatz. Die gewöhnliche Quadratwurzel wird nur zur exakten Bestimmung des ganzzahligen Bodens für das begrenzte D verwendet. Alle potenziell großen Lösungswerte und sämtliche Gleichheitsprüfungen bleiben exakt.

Rückgabewerte verwenden und überprüfen

Senden Sie ein Objekt mit dem Feld d, beispielsweise {"d": 13}. Für Formeln in der üblichen Schreibweise wird auch der großgeschriebene Alias D akzeptiert. Eine erfolgreiche Antwort enthält d, x, y und iterations. Behandeln Sie x und y in Ihrem Anwendungscode als dezimale Ganzzahlzeichenfolgen: Sprachen mit Ganzzahlen beliebiger Genauigkeit können sie direkt einlesen. Systeme, die auf Zahlen fester Breite beschränkt sind, sollten die Zeichenfolgen beibehalten oder eine Bibliothek für große Ganzzahlen einsetzen. Zur unabhängigen Prüfung quadrieren Sie x, ziehen D mal das Quadrat von y ab und bestätigen, dass das Ergebnis exakt eins ist. Verwenden Sie dafür Ganzzahl- und keine Gleitkommaarithmetik. Ungültige Typen, Brüche, Werte außerhalb des veröffentlichten Bereichs und Quadratzahlen erzeugen einen Fehler wegen ungültiger Eingabe statt eines irreführenden Resultats. Der Rechner nutzt weder Netzwerk noch Zufall, gespeicherten Zustand oder aktuelles Datum. Dasselbe D liefert daher immer dieselbe Antwort. Der Browser eignet sich für Einzelberechnungen; die API kostet $0.002 pro Anfrage, wenn Sie sie in ein Skript, einen Lehrdienst oder eine Testsuite integrieren möchten.