Calcular números irracionales

Question

Estoy genuinamente curioso, ¿cómo calculan las personas los dígitos decimales de números irracionales en general, y $\pi$ o raíces n-ésimas de enteros en particular? ¿Cómo alcanzan una precisión arbitraria?

Answer 1

Aplaudo tu auténtica curiosidad. No hay un método general. Para calcular los dígitos decimales de un número irracional en particular, comienzas con una definición del número.

Para $\pi$ hay muchos métodos conocidos. La respuesta de @GregoryGrant señala uno de los más antiguos y famosos. Arquímedes comenzó con hexágonos regulares inscritos y circunscritos, luego duplicó el número de lados varias veces para aumentar la precisión de su estimación. (Ver http://en.wikipedia.org/wiki/Pi#Polygon_approximation_era).

Buscar "cálculo de dígitos de pi" te llevará a información sobre métodos modernos.

Para raíces de polinomios (como raíces enésimas de enteros), el método de Newton es eficiente.

Para muchos irracionales, las fracciones continuas son una buena opción, como señala @Arteom.

Para algunos irracionales en particular, trucos ingeniosos (basados en teorías profundas) te dan muchos dígitos rápidamente. Por ejemplo, las fracciones 3/2, 7/5, 17/12, 41/29, ... son aproximaciones cada vez mejores a $\sqrt{2}$. Deberías poder adivinar el patrón.

Answer 2

Normalmente necesitas usar aritmética de precisión arbitraria para calcular grandes cantidades de dígitos de números irracionales típicos. La excepción son cosas atípicas como la constante de Champernowne 0.12345678910111213141516… :)

Existen varios paquetes de aritmética de precisión arbitraria disponibles. Internamente, utilizan grandes matrices o listas para almacenar grupos de dígitos de los números que manipulan. La computadora puede hacer aritmética simple en números representados de esta manera utilizando algoritmos similares a los enseñados en la escuela primaria, lo que te permite hacer aritmética en números de varios dígitos dado la habilidad de hacer aritmética en números de un solo dígito.

Sin embargo, para números muy grandes los algoritmos de multiplicación y división ingenuos son bastante ineficientes, por lo que se utilizan técnicas más sutiles. La multiplicación de números enormes puede realizarse eficientemente utilizando la Transformada Rápida de Fourier. La división puede realizarse multiplicando por el recíproco del divisor; los recíprocos pueden ser calculados usando el método de Newton.

Una vez que tienes esos algoritmos a tu disposición, es bastante sencillo calcular raíces de $n$ usando el método de Newton, como mencionó Lucian en los comentarios.

Sin embargo, no es necesario tener un paquete de aritmética de precisión arbitraria completo para calcular grandes cantidades de dígitos de algunos de los números irracionales bien conocidos. Es trivial en la mayoría de los lenguajes de programación sumar o restar grandes números almacenados como un array de bloques de dígitos. También es muy fácil multiplicar dichos números por un número de tamaño normal; la división por un número de tamaño normal es igualmente fácil de implementar. Y eso es todo lo que necesitas para calcular grandes cantidades de términos de muchas series de Taylor con una gran precisión.

Un ejemplo algo famoso de esta técnica es esta joya escrita en C por el difunto Dik T. Winter de CWI, que calcula $\pi$ con 800 dígitos decimales.

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;
     for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,
     f[b]=d%--g,d/=g--,--b;d*=b);}

Desafortunadamente, ese pequeño programa críptico no se puede ampliar para obtener más dígitos (correctos) debido a problemas de desbordamiento.

Pero aquí tienes un programa que escribí hace algunos años que puede generar grandes cantidades de dígitos de $e$; puede calcular 10,000 dígitos en un par de segundos. La versión original de este programa fue escrita en C, esta versión es en Python 2; como podrás imaginar, la versión en C es significativamente más rápida :). Esperanzadamente, los comentarios explican el algoritmo, aunque no estés familiarizado con Python. La idea principal es tratar la serie de Taylor de $e$ como un número escrito en base factorial y simplemente convertir ese número en notación decimal.

#! /usr/bin/env python

"""
    ECalc - Calculadora grande de e

    Genera dígitos de e, usando notación de base factorial
    Inspirado por Dik T. Winter

    Creado por PM 2Ring 2003.12.26
    Convertido de C a Python 2007.12.10
"""

import sys, math

# Constantes globales
N = 50                            # Número predeterminado de dígitos
W = 5                             # Dígitos por bloque
A = 10 ** W
LR2P = .5 * math.log(2.*math.pi)  # Logaritmo de Raíz 2 Pi
L10 = math.log(10.)               # Logaritmo de 10

def invlfact(n):
    """ Aproximación inversa de Stirling para logaritmo factorial n, usando el método de Newton """
    x = y = n * L10 - LR2P
    for i in xrange(3):
        x = (y + x) / math.log(x)
    return int(round(x))

def bigE(n):
    """ Genera n dígitos de e usando notación de base factorial """
    kmax = invlfact(n) + 1
    print "Calculando e a %d lugares, usando %d celdas" % (n, kmax)

    # Tabla para los dígitos de la base factorial, inicializada con la serie para e-2 = 1/2! + 1/3! + ...
    # Ignoramos las dos primeras entradas
    d = [1] * kmax
    print "e ~= 2."

    j = 1
    while n > 0:
        # Obtiene los próximos W dígitos multiplicando d por A, propagando los acarreos hacia abajo en la matriz,
        # luego imprimiendo la parte entera y eliminándola.
        kmax = invlfact(n)    # Número de celdas necesarias para este ciclo
        c = 0                 # Limpia acarreo
        for k in xrange(kmax, 1, -1):
            d[k] = d[k] * A + c
            c = d[k] // k
            d[k] -=  c*k

        # Imprime bloque y separador de campo. Puede necesitar modificarse si se aumenta W considerablemente
        jj = (j%10 and 1  or  j%50 and 2  or  j%200 and 3  or  4) - 1
        print "%0*d%s" % (W, c, "\n" * jj),

        j += 1; n -= W

def main():
    # Obtener número de dígitos
    n = len(sys.argv) > 1 and int(sys.argv[1]) or N
    bigE(n)

if __name__ == '__main__':
    main()  

Según MathWorld

Aproximadamente en 1966, el hacker del MIT Eric Jensen escribió un programa muy conciso (que requería menos de una página de lenguaje ensamblador) que calculó e convirtiendo de base factorial a decimal.

Espero que el algoritmo de Eric fuera sustancialmente el mismo que el que está en mi código, el cual derivé de un programa C obfuscado escrito por el difunto Dik Winter.

Answer 3

Así es como lo hizo Arquímedes hace 2.500 años. $\pi$ es la circunferencia de un círculo con diámetro uno. Lo que hizo Arquímedes fue inscribir un polígono con $n$ lados dentro del círculo. Así para $n=5.

Luego calculó la circunferencia del polígono. Esto da una aproximación a $\pi$ para cada $n$ y a medida que $n$ crece se acerca cada vez más a $\pi$.

Answer 4

Para algunos números irracionales, como $\pi$, existen series infinitas convenientes que convergen a ellos. Así por ejemplo $$\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}$$ Al sumar más y más términos de esta serie te acercas más y más a $\pi^2/6$. Puedes tomar una estimación para algún valor de $n$, multiplicar por $6$ y luego sacar la raíz cuadrada. Eso te dará una aproximación de $\pi$. Esto ilustra la idea, pero en la práctica nadie usa esta serie porque hay series que convergen a $\pi$ mucho más rápido.

Answer 5

Las fracciones continuas se utilizan comúnmente para obtener el valor decimal con suficiente precisión. Por ejemplo, la secuencia A001203 en la enciclopedia en línea de Sloan representa $\pi$ en forma de fracción continua (de hecho, todos los números racionales infinitos pueden descomponerse en una fracción continua finita, mientras que los números irracionales no pueden).