A partir del ejemplo en libro Classic Computers Science Problems de David Kopec
fuente: calculating_pi.py
Donde presenta una solución del tipo secuencia para calcular el número Pi, series infinitas de Gregory-Leibniz
ej: 4/1 - 4/3 + 4/5 - 4/7 + 4/9 - 4/11 + .... - 4/1000000
dando como resultado tras el 1 millon de iteraciones: 3.14159
Se realiza propuesta de mejora al algoritmo de cálculo
dando como resultado a las 29 iteraciones y 18 promedios: 3.1415926535897
- Enfocarse en el objetivo
- Comprender el algoritmo y el cálculo
- Analizar los resultados parciales
- Generar una analogía para mejor comprensión
- Reducir el problema
- Las series infinitas de Gregory-Leibniz es una de las tantas formas de obtener el número Pi, sin embargo es considerada ineficiente por la cantidad de Iteraciones requeridas.
- Pero es también una de las más simples de implementar y fáciles de entender.
# Calcula Pi utilizando las series infinitas de Gregory-Leibniz #
def pi_leibniz(n_terms: int) -> float:
pi = 0
sum_res = 1
for i in range(1, n_terms, 2): # serie impar
pi += (4 / i) * sum_res # acumula diferencias cada vez mas pequeñas
sum_res *= -1 # intercala suma y resta
return pi
- Calcula Pi en una secuencia con promedios escalonados y en cascada.
- Reduce considerablemente el número de iteraciones y aumenta la precisión rápidamente.
- Aporte realizado por Antonio Molina el 2023 para el 14 de marzo, 3.14 día de Pi.
- Calcula la serie para una cantidad muy reducida de Iteraciones.
- Reserva los N últimos promedios escalonados de la serie.
- Promedios Escalonados: cuando sube una escalera, mantiene ambos pies en los escalones, en ese momento promedia ambos, luego sube un peldaño, manteniendo un escalón en común con el estado anterior y nuevamente promedia ambos, eso es escalonado.
- Una vez calculados los N promedios pasa al siguiente nivel, realizando un promedio en Cascada, reduciendo nivel por nivel los resultados en uno, hasta que solo quede un número.
- Promedio en Cascada: teniendo N resultados, estos son promediados escalonados, obteniendo N-1 resultados, e iterando con el siguiente nivel, asi hasta llegar a obtener solo un resultado N=1.
-
Debido a que la iteración suma y resta fracciones del número 4 cada vez más pequeñas, que son divisiones de números impares, esta ira generando por cada ciclo una diferencia hacia arriba con las sumas y hacia abajo con las restas, así hasta aproximarse al número final, el límite de la función, que en este caso el Pi.
-
Lo que se plantea es promediar estas diferencias que se generan al tirar hacia arriba y hacia abajo, llegando más rápido al resultado.
-
El truco esta en realizar promedios escalonados (de a pares y solapados), aprovechando la diferencia entre un número sumado y uno restado, luego el restado con el siguiente sumado y así sucesivamente, cada par dará una rápida aproximación al número limite, si se promedia un set de N números, con sus resultados obtendremos N-1 números, cada vez perderemos un número y seguir así hasta que solo queda un solo número, este será la aproximación más cercana que podremos tener con muy pocas iteraciones.
-
Tras iterar una cantidad pequeña definida por los parámetros n_iter - n_prom, ej. n_iter=16 y n_prom=9, comienza a guardar los últimos n_prom cálculos de la iteración.
-
Los datos guardados serán promediados escalonados, aquí existe una diferencia entre números que sumaron y los que restaron en la secuencia, su promedio tiende a ser el resultado.
-
Luego los promedios resultantes que son uno menos que al inicio, vuelven a ser promediados y siguen iterando los promedios hasta que solo queda un número como resultado.
def calcula_pi(n_iter: int, n_prom = 1) -> float:
Pi = 0
denominator = 1
operation = 1
dato = []
prom = []
#calcula serie Leibniz
for i in range(n_iter):
pi += operation * (numerator / denominator)
denominator += 2.0
operation *= -1.0
#acumula ultimos N resultados para promediar
if(i>=n_iter-n_prom): dato.append(pi)
#calcula promedios en cascada
while(len(dato) > 1):
prom = []
#calcula promedio escalonado
for i, num in enumerate(dato[0:-1]):
prom.append( (num + dato[i+1]) /2 )
dato = prom.copy()
return dato[0]
Pi = 3.141592653589793
iter, prom, error, result
9, 6 err:5e-5 3.1415 3820036173
11, 7 err:-6e-6 3.14159 86833943497 <- el original requirio 1 millon de iter para alcanzar esto
13, 10 err:5e-7 3.141592 1043704067
16, 9 err:3e-8 3.1415926 186270062
17, 11 err:-6e-9 3.14159265 9926378
20, 11 err:4e-10 3.141592653 10039
21, 14 err:6e-11 3.1415926535 244623
23, 14 err:9e-12 3.14159265358 0177
25, 18 err:7e-13 3.141592653589 0586
27, 18 err:7e-14 3.1415926535897 16
29, 18 err:9e-15 3.1415926535897 833
30, 18 err:-6e-15 3.14159265358979 93
31, 20 err:-4e-16 3.141592653589793 6 <- alcanza 15 dígitos de precisión la máxima capacidad de float
- Un detalle importante es que para lograr un buen promedio, las mejores alternativas fue dejar fuera del cálculo las primeros resultados de la serie 1..9, ya que son valores muy extremos, lo pueden notar en el grafico reducción de error.
- El resultado de 9 iteraciones en la serie y los últimos 6 números promediados nos da un resultado de 3,1415 clásico.
- Con 11 iteraciones y 7 promedios alcanzamos un digito más.
- Pero con solo 29 iteraciones y 18 promedios logramos un número con bastante precisión de 14 dígitos 3.1415926535897.
- El costo del algoritmo original de Leibniz estaba en la cantidad de Iteraciones que requería, esto se debía a la diminuta corrección a medida que crecía el Iter
- En este algoritmo se ha reducido drásticamente la cantidad de Iteraciones a solo unas pocas, por lo que, el costo se ve reducido
- Pero hemos agregado el cálculo de los promedios escalonados y en cascada, lo que tiene un costo de NxN/2 donde N es la cantidad de Promedios
- Costo final es ===> Iter + Prom * Prom/2 ej: 31 Iter y 20 Prom ==> 31 + 20 * 10 ===> 231 para 15 decimales correctos
- Desconozco la cantidad de Iteraciones que requeriría la solución original para 15 decimales, pero requería 1millon para el equivalente a 11 Iter y 7 Prom ==> 11 + 7 * 3,5 = 36 ==> 1.000.000 vs 36 creo que es buena la reducción del costo
En cuanto a cantidad de iteraciones necesarias, esta solución deja a Leibniz a la par con las series de Newton, Madhava y Viete, aunque la serie de newton parte de haber conocido la solución de Pi en función trigonométrica, y luego la formula fue traspasada a una serie, lo que es como haber hecho trampa. Si de eso se trata tomaría el numero A=0,78539816339744830961566084581988 y lo multiplicaría por 4, y obtendría Pi, el numero A parte de conocer Pi o la relación entre en cuadrado y un circulo inscrito.
Existen otros métodos de aceleración de convergencia: pero la simplicidad es lo que más se extraña.
Y si de Rapidez hablamos nada superara a Euler, ni menos a Ramanujan con sus variadas soluciones impresionante y entre las más sencillas encontramos: 3+16/113 = 3,141592920 o 355/113 = 3,141592920 o 103993/33102 = 3,14159265301
Merece al menos un análisis la optimización del esfuerzo computacional, hay una gran reducción y permite alcanzar una muy alta precisión con muy poco esfuerzo, aunque sabemos que PI es una constante conocida en todo entorno de desarrollo, es la optmización de la solución la que se plantea y su simplicidad, como si estuviéramos en la era pre computadoras, ya que, este algoritmo permite acelerar la convergencia en series alternadas como esta.
mas detalles: Wiki Pi
Utilizaremos como ejemplo:
iter, prom, error, result
16, 9 err:3e-8 3.1415926 186270062
Primero obtenemos la serie, en este caso será de 16 Iteraciones y 9 promedios
Las últimas 9+1 secuencias de 16 Iteraciones (+1 para obtener 9 promedios)
Iter 4/i i S/R Result
7 0,307692308 13 1 3,283738484
8 0,266666667 15 -1 3,017071817
9 0,235294118 17 1 3,252365935
10 0,210526316 19 -1 3,041839619
11 0,19047619 21 1 3,232315809
12 0,173913043 23 -1 3,058402766
13 0,16 25 1 3,218402766
14 0,148148148 27 -1 3,070254618
15 0,137931034 29 1 3,208185652
16 0,129032258 31 -1 3,079153394
S/R: Suma o Resta
i: secuencia números impares
Result: resultado anterior secuencia con suma o resta de 4/i
Ahora se promedian en cascada los N=9 últimos resultados obtenidos de la secuencia
Promedios de los Resultados de las N últimos resultados
promedio escalonado: entre dos números y avanza uno
promedio en cascada -> siguiente nivel realiza promedios del anterior, reduciendo en uno sus resultados
nivel 1 nivel 2 nivel 3 nivel 4 nivel 5 nivel 6 nivel 7 nivel 8 nivel 9
3,15040515
3,134718876 3,142562013
3,147102777 3,140910826 3,14173642
3,137077714 3,142090245 3,141500536 3,141618478
3,145359288 3,141218501 3,141654373 3,141577455 3,141597966
3,138402766 3,141881027 3,141549764 3,141602069 3,141589762 3,141593864
3,144328692 3,141365729 3,141623378 3,141586571 3,14159432 3,141592041 3,141592952
3,139220135 3,141774413 3,141570071 3,141596725 3,141591648 3,141592984 3,141592512 3,141592732
3,143669523 3,141444829 3,141609621 3,141589846 3,141593285 3,141592467 3,141592725 3,141592619 3,141592675
NOTA: si lo pueden notar en este ejemplo por cada nivel aprox. gana un decimal de precisión
El último número de la cascada de promedios es el resultado 3,141592675
Grafico de comparación de los distintos niveles en la optimización de Leibniz realizados por el algoritmo de Antonio Molina
A continuación se presenta una comparación realizada entre algunos métodos que pueden competir entre sí, dejando fuera las series aceleradas, que no darían posibilidad alguna para comparación, además su alta complejidad las hace poco comprensibles.
Se comparan las siguientes series: Leibniz, Newton, Wallis, Beeler, Nilakantha, Viete, Madhava y finalmente se incluye Leibniz optimizado (nivel 6 por Antonio Molina en rojo)
