Aproximaciones racionales óptimas de dígitos fijos de $\pi$

Question

¿Existe una forma sistemática de encontrar aproximaciones racionales óptimas a $\pi$ cuyo numerador y denominador tienen como máximo $n$ ¿dígitos?

Más concretamente:

Dejemos que $D_n$ sea el conjunto de todos los enteros positivos con a lo sumo $n$ y definir la relación de equivalencia $\sim$ en $D_n\times D_n$ por $(x,y) \sim (x',y')$ si $\frac{x}{y} = \frac{x'}{y'}$ . Para cada uno de los fijos $n$ ¿existe una forma sistemática de decidir qué clase de equivalencia $[x,y]$ en $D_n\times D_n/\sim$ minimiza el residuo $R(x,y) = \left|\frac{x}{y} - \pi\right|$ ?

Por ejemplo, el óptimo $D_1$ la aproximación es $[3,1] = \{(3,1),(9,3)\}$ .

Nota: se ha señalado que siempre se puede hacer esto con un algoritmo de fuerza bruta. Eso es obvio y no es interesante. Lo que es interesante es un algoritmo eficiente para hacer esto.

Un punto filosófico: claramente tenemos muy, muy, muy buenas aproximaciones decimales de $\pi$ por lo que las aproximaciones racionales tienen un interés práctico limitado. Se trata, pues, de una cuestión que surge del disfrute de las matemáticas por sí mismas y no por su aplicación práctica.

Answer 1

Las mejores aproximaciones de cualquier número irracional vienen dadas por la convergentes finitos de su fracción continua . Para $\pi$ su fracción continua comienza $$[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]\;\;\;\;. $$ No se sabe que tenga ningún patrón, pero ha sido ampliamente tabulado. Los numeradores de estas fracciones también se han tabulado y los primeros son $$3, 22, 333, 355, 103993, 104348, 208341, 312689, 833719, 1146408, ...$$ Para encontrar el óptimo $D_n$ aproximación de $\pi$ simplemente elige el número más grande de esta lista con $n$ o menos dígitos y ese será el numerador de la fracción. Tenga en cuenta que esto significa que el óptimo $D_3$ , $D_4$ , y $D_5$ aproximaciones de $\pi$ son todos $355/113$ .

Answer 2

Lo hay. Sólo tienes que utilizar cualquier método de aproximación que quieras para $\pi$ y luego calcula las diferencias entre estas aproximaciones y las fracciones que tienes, y toma la fracción con la menor diferencia.

Pero lo que sospecho es que querías un rápido algoritmo para hacerlo. Si alguien conociera un método que fuera más rápido que nuestro algoritmo más rápido conocido para calcular los dígitos de pi, bueno, eso es una pequeña contradicción.

Si no es así, puedes volver a utilizar la aproximación más rápida para pi que tenemos. Una vez que tengas un número suficiente de dígitos, utiliza el método de cálculo de fracciones continuas y, por tanto, convergentes para encontrar las mejores aproximaciones para pi.

Espero que eso haya ayudado.