Calculando factoriales de números grandes

El día de ayer por medio del perfil de línea de tiempo del Doctor Juan González observamos el interesante artículo tutorial sobre Python publicado por Juan J. Merelo Guervós el cual incluye retos de programación. Ni tardo ni perezoso, a pesar de llegar cansado a mi hogar, y tras una vigorizante taza de café negro con leche de avena sin azúcar nos dimos a la tarea de practicar algunas cositas para mantener el cerebro en forma y al día con las novedades en programación.

Calculando el factorial de un número.

Definición.

No vamos a hacer esta entrada muy profunda, ya que debemos ir a trabajar para ganarnos el pan de cada día, directo y rápido: el factorial de un número viene expresado por la multiplicación sucesiva de sus antecesores, uno a uno, hasta llegar a uno y se denota por ” n! ” ; así, por ejemplo 5!= 5 x 4 x 3 x 2 x 1 = 120 (las equis indican multiplicación).

El reto.

Pues arroja el guante el sr. Merelo con una función recursiva escrita, por supuesto, en lenguaje Python para calcular un factorial y tras ensayo y error llegamos a una satisfactoria y muy parecida a la ya famosa y escrita por todos lados en internet (para ser honestos en algún momento vimos esta función pero no recordabamos… hasta que el buscador DuckDuckGo acudió en nuestra ayuda, un asistente tan capaz -en memoria- como todas las asistentes que tuvo Albert Einstein -que en paz descansen, Valentine Bargmann y el Doctor Einstein-).

Para ilustraros cómo funciona, aprovechando nuestro mundo tecnológico –y añorando el gis y el pizarrón- os colocamos un gif animado tomado de penjee.com, un sitio web dedicado también a la enseñanza de Python:

Función factorial animada tomada de penjee.com
Función factorial animada tomada de penjee.com
def factorial(num):
  if num == 1:
    return 1
  else:
    return num * factorial(num - 1)

Calculando el factorial de un número grande.

Factorial, fórmula y definición
Factorial, fórmula y definición

Hasta acá todo muy bien, pero el reto no finalizaba allí, una segunda pregunta era ¿qué tal calcula los números grandes? Como bien podéis imaginar, el multiplicar y multiplicar en ordenador pues en algún momento se nos agota la memoria suponíamos nosotros… pues que aquí está la pega del asunto, tras calcular el factorial 120! de manera fácil (en Wikipedia en inglés denotan que normalmente el máximo factorial que se puede calcular con un procesador de 64 bits en una variable de tipo entero es 20! –ya nosotros hemos comentado el poder de cómputo de los procesadores y sistemas operativos de 64 bits-) pues nos envalentonamos a ir “al infinito y más allá”.

python factorial.py con n = 120 (ciento veinte)
python factorial.py con n = 120 (ciento veinte)

Siendo así la cosa le establecemos a 1200 (un mil doscientos) a la función de marras y nos arrojó este lindísimo mensaje de error que os mostramos:

python factorial.py con n = 1200 (mil doscientos)
python factorial.py con n = 1200 (mil doscientos)

Pero leyendo nos percatamos que el problema no es el desbordamiento de memoria, no,  el desbordamiento es un error en la profundidad de recursión:

RecursionError: maximum recursion depth exceeded in comparison

El contrareto.

Ya esto se salía del reto impuesto, es un contrareto que nos presenta Python pues claro, en un entorno de programación uno debe siempre imponer límites considerando que aún no ha llegado la computación cuántica (y aún así ésta tiene límites en este universo). Indagando, y hay bastante material sobre el tema, llegamos a la librería sys encargada de manejar tales asuntos y de hecho el manual en línea de Pyton nos advierte:

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

Que traducimos al castellano:

Establece el límite de la profundidad máxima de la pila del interprete Python. Este límite previene una recursión infinita ocasionando un desbordamiento en la pila (del lenguaje) C y la consecuente falla de Python (Dios nos ampare que alguien crea que Python es falible†). El límite más alto posible es dependiente de la plataforma empleada. Un usuario puede necesitar ajustar el límite superior cuando tenga un programa que requiera una mayor recursión y la plataforma que lo soporta lo permita. Esto debería hacerse con cuidado porque un límite muy alto puede conducir a un fallo (Dios nos ampare que alguien crea que Python es falible†).

†(Nota del traductor en tono de sarcasmo).

Python recursion limit get and set
Python recursion limit get and set

O inventamos o erramos.

Don Simón Rodríguez: "Inventamos o erramos".
Don Simón Rodríguez: “Inventamos o erramos”.

Como nuestro insigne Don Simón Rordríguez nos legó, debemos inventar y a lo sumo fallar (y reintentar y así sucesivamente hasta lograr inventar) nosotros pensamos ¿Y si establecemos el límite superior de la pila de procedimientos (límite de recursión) precisamente de manera recursiva? 🤔

Pues acá vamos entonces:

import sys
def factorial(num):
  '''Return large factorial by Jimmy Olano Sayago
               (GNU General Public License v3.0) '''
  if num<=1:
    return 1
  else:
    sys.setrecursionlimit(sys.getrecursionlimit()+1)
    return num * factorial(num - 1)

file = open('large_factorial_result.txt', 'w')
cad = factorial.__doc__
file.write( cad )
file.write( ' factorial(21700): ' )
file.write( str( factorial( 21700) ) )
file.close

Al tener nosotros establecida la función, por tanteo y utilizando un procesador AMD A8-6600K APU (64 bits, 4 núcleos y 8 gigabytes en RAM) llegamos un valor de 21700! el cual ocupa 86400 digitos. Esencialmente el guion que hicimos basados en la clásica función recursiva de cálculo factorial es aumentar el límite de pila de Python de manera recursiva para luego abrir un archivo de texto y guardar allí el resultado.

El delicado tema de los typos de variables y la memoria disponible.

Consultamos muy diversos reportajes sobre el tema del manejo de la memoria y las variables pero el que fue revelador para nosotros es uno escrito hace más de once años pero que goza de plena vigencia: una comparación sobre cómo trabajan las variables los lenguajes C y Python.

Tiene su teoría y abunda su práctica y probamos los diferentes ejemplos y nos resultó en valore comprobatorios contra lo que se afirma en dicha entrada pero la conclusión es tan excelente que se las traemos en idioma inglés y la traducimos al castellano:

Python removes this confusion, there is only the integer object. Does it have any limits? Very early versions of Python had a limit that was later removed. The limits now are set by the amount of memory you have in your computer. If you want to create an astronomical integer 5,000 digits long, go ahead. Typing it or reading it will be the only problem! How does Python do all of this? It automatically manages the integer object, which is initially set to 32 bits for speed. If it exceeds 32 bits, then Python increases its size as needed up to the RAM limit.

La traducción hecha por nosotros:

Python elimina esta confusión (de variables), hay solo el objeto entero. ¿Tiene algún límite? Muy tempranas versiones de Python tuevieron un límite que luego más tarde fue removido. Los límites ahora son establecidos por el monto de memoria que usted tenga en su computadora. Si quiere crear un entero astronómico de 5 mil dígitos, ¡adelante! ¡Escribirlo o leerlo será el único problema! ¿Cómo Python hace todo esto posible? Pues automáticamente dirige el objeto entero, el cual inicialmente estaba configurada a 32 bits por motivos de velocidad. Si excede los 32 bits, entonces Python incrementa su tamaño tanto como se necesite hasta llegar al límite de la memoria RAM.

Así como lo podéis leer, en el año 2006 se consideraba “astronómico” una cifra de 5000 dígitos, ¡PUES HE AQUÍ QUE CALCULAMOS UN FACTORIAL CON 86400 DÍGITOS! Para nosotros es todo un logro digno de dedicarle una entrada y una pequeña nota en las Wikipedia(s).

Sometido a consideración por la comunidad de programación y comunidad matemática.

De inmediato subimos el guion y su resultado (utilizando el idioma inglés) a Gist mantenido en línea por GitHub.com (¡gracias!) y “tuiteado” con la etiqueta #Python y #1linepy tal como recomienda el sr. Merelo:

Experimento social.

Como experimeto social hemos cometido una torpeza en la fórmula cuando establecemos:

if num<=1:
  return 1

El objetivo es detectar cuántas personas realmente analizan nuestra propuesta y nos hacen llegar sus observaciones (se especula que el mismísimo Leonardo DaVinci codificaba mal sus planos a propósito por si caían en manos enemigas) ya que el cálculo de factoriales está supeditado al campo de los números positivos, ya sean reales o imaginarios (esto es así porque el cálculo factorial es clave en la determinación de combinaciones y permutas, todas ellas en el campo de los números positivos).

También hemos publicado en Wikipedia en inglés nuestra experiencia (y próximamente en castellano, francés, italiano, portugués, alemán y ruso en la medida de lo posible y de nuestro tiempo libre) para determinar cuales sociedades unidas por un idioma común aceptan o rechazan nuestra propuesta (cada idioma Wiki tiene sus wikipedistas que algunas veces nos han “echado para atrás” nuestras ediciones por diversos motivos variopintos).

 

Conclusión: no hemos llegado aún al infinito, menos más allá.

Una inquietud que tenemos es la gran cantidad de ceros al final del resultado y una cosa que nos tranquiliza es la serie de resultados hasta 20! que va aumentado la cantidad de ceros a la derecha. Lo lógico es que si estamos multiplicando pues “corremos la coma hacia la derecha” y se debe, desde luego, rellenar con ceros para ello.

Aún falta por determinar hasta qué punto alcanza nuestro hardware su límite, podremos hacer un ciclo “for” que arranque con este último valor de 21700! e irlo incrementando y guardando en archivos cuyos nombres tengan el valor calculado apara identificarlos hasta que simplemente falle Python, ¡PERO ESPEREN, HAY MÁS!

Pensamos que arrancando nuestro sistema operativo Ubuntu 16.04 LTS en modo terminal, sin cargar interfaz gráfica y “tumbando” los servicios diversos -Apache server, MySQL, etc.- y los más que se puedan de systemd ganaremos más memoria y compararemos resultados a ver si influye y si es así, cuánto influye, ¡SOMOS TODO OÍDOS A VUESTRAS IDEAS AL RESPECTO POR MEDIO DE NUESTRA CUENTA EN TWITTER @KS7000!

Fuentes consultadas.

En idioma castellano.

En idioma italiano.

En idioma inglés.