Mejorando los algoritmos: las matemáticas

El otro día hablábamos de cómo crear algoritmos y de la manera en la que deben evolucionar, para ir mejorando su comportamiento. Hoy queremos proponeros un acercamiento más a este mundo de la algoritmia usando como base las matemáticas.

La algoritmia y las matemáticas

La algoritmia como ciencia, está basada principalmente en las matemáticas, ya que son con estas herramientas con las que podemos medir el comportamiento de un algoritmo u orden de un algoritmo. Pero las matemáticas muchas veces aportan grandes recursos para realizar o mejorar algoritmos.

Las fórmulas matemáticas, progresiones o patrones matemáticos, son ampliamente estudiados en matemáticas y en muchas ocasiones se obtienen métodos más o menos sencillos, para calcular exactamente el problema que queremos resolver, sin tener que realizar un cálculo “a ojo” o por “fuerza bruta”.

La suma de los n primeros números

Gauss, uno de los más importantes matemáticos de la historia, descubrió una sencilla fórmula para sumar los n primeros número de una sucesión, el problema es el siguiente:

Queremos saber cual es la suma de todos los números entre 1 y 100, es decir la siguiente cuenta: 1+2+3+4+5…..+99+100

Hacer la cuenta en papel, tiene su trabajo, pero realizar en un ordenador es muy simple, basta con un bucle for y una variable donde vamos acumulando la suma. Pero y cuando no había ordenadores cómo realizaban este tipo de cuentas, la respuesta es utilizando una fórmula de Gauss:

Gauss pensó, bueno si hago parejas 1+100=101 , 2+99=101, 3+98=101 todas las parejas suman 101 y si hay 100 valores entonces tengo 50 parejas, luego el resultado es 101*50=5050. la fórmula es sencilla:

(A1+An)*n/2  siendo A1 el primer término, An el último, y n el número de casos.

Con esto os invito a buscar, antes de realizar nuestros algoritmos si hay una fórmula exacta con la que obtener directamente la cantidad, pues es el método más optimizado para calcularlo. Si hacemos una pequeña comparación vemos que utilizando la fórmula hacemos 3 operaciones aritméticas, mientras que utilizando nuestro bucle for estamos haciendo más de 100 operaciones aritméticas.

Multiplos de 4 y de 5 entre un rango

Si os acordáis este es el problema que poníamos el otro día, para exponer una manera de mejorar los algoritmos y como bien dijo uno de nuestros usuarios, la manera más sencilla es buscando múltiplos de 20 entre ese rango.

Si no habéis visto la solución de múltiplos de 20, no pasa nada, pero todo esto también tiene una base matemática bastante sencilla:

Si partimos de un número múltiplo de 4, está claro que se puede obtener fácilmente multiplicando 4 por los números enteros, es decir es la serie 4 8 12 16 20 24 … de igual manera sabemos que la de múltiplos de 5 es la serie 5 10 15 20 25. Para calcular números que cumplan las dos propiedades al mismo tiempo, la manera sencilla es buscar el m.c.m (mínimo común múltiplo) de 4 y 5:

Realizamos la descomposición factorial:

4=2*2 y 5=5

para el m.c.m cogemos los factores comunes y no comunes con mayor exponente, es decir tenemos 225=20 luego 20 es el m.c.m de 4 y 5.

Así que calcular los múltiplos de 4 y 5 entre un rango se transforma en buscar los múltiplos de 20 entre ese rango, los primeros son 20 40 60 80 100 …

Agradecimientos:

Queremos agradecer a Roberto, que mostró la solución más optimizada, su comentario ha sido el que nos ha invitado a realizar esta entrada y demostrar, como por si alguien todavía lo dudaba, las matemáticas y la informática tienen una relación muy estrecha.