#ExcelPedroWave

Trilogía para calcular la sucesión de Fibonacci

1. Cálculo iterativo de Fibonacci
2. Cómo calcular números Fibonacci con VBA
3. Calculando números grandes Fibonacci. Artículo dividido en 2 fragmentos:
1. Calculadora de números grandes Fibonacci
2. Diseño de la calculadora Fibonacci

Este es el tercer artículo sobre números Fibonacci, donde veremos cómo calcular números grandes, que ningún tipo de datos de Excel o de VBA puede soportar.

Como el artículo es demasiado extenso, lo he dividido en 2 fragmentos. El primer fragmento es este mismo artículo. En el segundo fragmento explicaré cómo he diseñado esta calculadora de la sucesión de Fibonacci para números grandes...

La división de un problema complejo en fragmentos es una solución elegante y eficaz, como veremos en este artículo fragmentado en dos partes...

Divide y vencerás (DYV) es uno de los principales métodos a seguir para diseñar algoritmos complejos. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual o similar tipo. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.

En esta técnica se basan los algoritmos de ordenamiento, de multiplicación de números grandes, de análisis sintácticos y muchos más.

Para calcular números grandes Fibonacci he usado esta misma técnica, dividiendo los números grandes en fragmentos de números más pequeños, que se puedan sumar, y así poder vencer los límites de los tipos de datos en VBA.

Límites de los tipos numéricos

En los dos primeros artículos hemos comprobado que el límite es de 15 cifras significativas, para un número dentro de una celda de Excel, y que en VBA el límite es de 29 cifras significativas, para el subtipo Decimal del tipo Variant.

Ahora definiremos tipos de datos personalizados con matrices de números fragmentados, para alcanzar más de 29 cifras significativas con lo que, por ejemplo, podremos calcular el número de Fibonacci:

Fibonacci(518) - Wolfram|Alpha (wolframalpha.com) = 

805587367387474993557712643417250666635155463347703764181824844653814375958479581952978891769754733107167209

Que ni siquiera cabe en una línea de texto, de unos 80 caracteres, pues contiene 108 cifras significativas.

En esta imagen se muestra la sucesión de Fibonacci desde Fib(492) hasta Fib(518), todos ellos números de más de 100 cifras significativas.

La pregunta es: ¿Cómo puedo hacer cálculos con números tan grandes?

¡Si no hay ningún tipo de dato numérico, ni en Excel ni en VBA, que admita tantas cifras!

Cómo sobrepasar los límites de cálculo

Lo que me encanta de los ordenadores es que obedecen sin rechistar a cualquier orden que se les dicte mediante un programa.

No como los humanos que, aún dándoles la receta de cocina, no saben cocinar... (me pongo yo mismo como ejemplo)

Siempre que se respeten las reglas del lenguaje de programación, se pueden obtener resultados de salida que a priori son imposibles.

Para demostrarlo vamos a saltarnos las barreras de los límites de los tipos de datos numéricos definidos por el lenguaje VBA.

¿Te imaginas hacer cálculos con números grandes antes de la invención del ordenador?

¿Te imaginas a mi nieto aprendiendo a calcular con un ábaco?

Calculadora humana - Wikipedia, la enciclopedia libre

Cómo los científicos realizaban cálculos complejos antes de la invención de las calculadoras (labrujulaverde.com)

Los inicios de los cálculos computacionales – The Smoke Sellers

Instrumentos de cálculo en la historia - Ciencia (redestrategia.com)

Descarga la calculadora de Fibonacci

Descarga esta calculadora de Fibonacci para números grandes, con la hoja protegida sin contraseña, desde cualquiera de estos enlaces:

• Microsoft OneDrive: Calculando números grandes Fibonacci - PW1.xlsm

• Sites Google Drive: Calculando números grandes Fibonacci - PW1.xlsm

Abre el archivo y habilita la edición y las macros para poder hacer cálculos con números grandes de la sucesión de Fibonacci.

Características de la calculadora

Para calcular un número de Fibonacci se escribe en la celda E1 y se hace clic en la imagen con la espiral de Fibonacci. Haciendo clic en la papelera se borran los números.

Características de la calculadora:

1. Calcula hasta el número Fib(156790), debido al límite máximo de 32767 cifras guardadas como texto en una celda.
2. Visualiza un único número si es mayor que Fib(4901), debido al límite máximo de 1024 caracteres visualizados en una celda.
3. Visualiza todos los números si el Fibonacci máximo a calcular es el número Fib(4901).
4. Permite arrancar, pausar y abortar el cálculo.
5. Muestra el progreso del cálculo en la barra de estado. 
6. Mide los tiempos de cálculo, de transformación y de carga en la hoja.
7. Avisa si se produce un error de memoria o de desbordamiento.
8. Borra datos del cálculo manual y automáticamente.
9. Imprime los números calculados. A partir del Fib(14605) es mejor usar copiar y pegar, pues se imprimen parcialmente.
10. Protege la hoja de cálculo sin contraseña.

Vídeo: Números grandes Fibonacci

En este vídeo presento la plantilla que has descargado y que permite calcular números grandes de la sucesión de Fibonacci, de mucho más que 29 cifras significativas:

Otros algoritmos Fibonacci

El 10 de diciembre publiqué el segundo artículo de esta trilogía, y avisé de su publicación en este enlace a LinkedIn, cuando ya había programado la parte del algoritmo que calcula números grandes de Fibonacci, usando el método divide y vencerás con las matrices de tipo Long fragmentadas, que explicaré en el segundo fragmento de este artículo.

Un comentario de D. Tello, Ph.D. me puso sobre aviso de que Rick Rothstein, excelente Microsoft MVP en Excel, había escrito un código para Fibonacci usando VBA parecido al mío. La sorpresa fue que el mismísimo Rick Rothstein me contestó:

Hace un tiempo publiqué una calculadora de Fibonacci "infinita" que un tal Eric W aceleró ** drásticamente ** usando mi algoritmo, pero intercambiando las manipulaciones de cadenas con manipulaciones de arrays binarias.

Y adjuntaba el algoritmo que Eric W había publicado, con matrices del tipo Byte, en este foro: MrExcel.com - Fibonacci - Eric W

como mejora y en contestación al algoritmo de Rick Rothstein con cadenas del tipo String, de su comentario en el foro: MrExcel.com - Fibonacci - Rick Rothstein

Probando en mi maravillosa tableta (con 2 GB de RAM) a calcular el Fib(99999):

• Con el algoritmo de Eric W tarda unos 489 segundos, más de 8 minutos.
• Con mi algoritmo, incluido en la descarga, tarda unos 204 segundos, menos de 3,5 minutos.
• ¡La mitad de tiempo del algoritmo de Eric W! ¡Y eso que mi calculadora incluye otras funcionalidades, además del cálculo propiamente dicho!

Me gustaría conocer los tiempos de cálculo en otras máquinas...

Y para eso necesito tus comentarios con tus resultados...

Diseño de la calculadora Fibonacci

Dejo pendiente el segundo fragmento de este artículo, con el tutorial de cómo se ha diseñado esta calculadora Fibonacci, que pronto publicaré...