Ich habe keine Zeit für eine vollständige Antwort, aber hier ist eine Teilantwort. Diese Technik verwendet die Konzepte der fortlaufenden Brüche - es gibt viel über sie online. Ich werde Ihren Wert dmin ignorieren, der unten nicht verwendet wird.
Holen Sie sich die continued fraction expansion of pi an so viele Orte wie Sie brauchen. Für Ihre Schranke von dmax < = 1E15 müssen Sie nur die ersten 28 Nummern, die
[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13]
eine kurze Schleife verwenden, sind die convergents für pi zu finden, die Nenner knapp unter und knapp über Dmax hat. In Python, die
pi_cont_frac = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1,
3, 1, 14, 2, 1, 1, 2, 2, 2, 2,
1, 84, 2, 1, 1, 15, 3, 13]
denomlo, denomhi = 1, 0
numlo, numhi = 0, 1
for q in pi_cont_frac:
denomlo, denomhi = denomhi, q * denomhi + denomlo
numlo, numhi = numhi, q * numhi + numlo
if denomhi > dmax:
break
Einige Software wie Microsoft Excel, verwenden würde den Anteil numlo/denomlo, wäre aber es kann als die bessere Annäherung sein. Finden Sie nun den Wert der natürlichen Zahl r, die denomhi - r * denomlo knapp unter (oder gleich) dmax macht.
Dann ist entweder numlo/denomlo oder (denomhi - r * denomlo)/(denomhi - r * denomlo) Ihre gewünschte nächste Fraktion zu Pi. Überprüfen Sie einfach, welcher näher ist.
Dieser Algorithmus ist von logarithmischer Reihenfolge (dmax), und aufgrund der Eigenschaften von Pi ist es normalerweise viel niedriger. Für dmax < = 1e15 braucht es 28 Schleifen, aber ein paar mehr Clean-up-Anweisungen.
Sie können einen schnelleren Algorithmus erstellen, indem Sie die Konvergente vorberechnen und speichern (Werte von numhi und denhi) und eine Suche nach dem Wert von deni kurz oberhalb von dmax durchführen. Dies benötigt auch nur 28 Zahlen, aber Sie benötigen dies sowohl für die Zähler als auch für die Nenner. Eine binäre Suche würde höchstens 5 Schritte benötigen, um sie zu finden - praktisch sofort. Eine weitere Möglichkeit, mehr Speicher und weniger Berechnungen zu verwenden, wäre die Speicherung aller Zwischenfraktionen. Dieser Speicher würde in die Hunderte gehen, mindestens dreihundert. Wenn Sie diese gespeicherte Liste für die fortgesetzte Fraktionserweiterung von pi nicht mögen, könnten Sie den Wert von pi verwenden, um dies im laufenden Betrieb zu berechnen, aber mit doppelter Genauigkeit (in C) würden Sie nur zu den 28 Zahlen kommen, die ich Ihnen gezeigt habe .
Für weitere Forschung, schauen Sie weiter Fraktionen und Zwischenfraktionen.
Ist '44/14 'eine akzeptable Antwort für' dmin = 13' und 'dmax = 15'? –
Oder, um es anders auszudrücken: Was motiviert die "dmin" -Bedingung? Wenn der einzige Grund dafür ist, sicherzustellen, dass die Näherung "gut genug" ist, könnte das Problem leichter sein, wenn es auf eine andere Art und Weise wiederholt wird. z.B.es gibt einen ziemlich einfachen Algorithmus, um das einfachste Rational in einem gegebenen rationalen Intervall zu finden, das leicht angewendet werden könnte, wenn die Einschränkung tatsächlich ist, dass die Approximation und pi sich um höchstens 1/dmin unterscheiden, was eine etwas andere Einschränkung ist. –