Algoritmos matemáticos

Las matemáticas y la computación están fuertemente relacionadas. Es difícil imaginar un mundo donde estos dos campos no estén relacionados uno con otro. Actualmente, una gran cantidad de cálculos de matemáticas aplicadas se realiza en computadoras, como la resolución de largos sistemas de ecuaciones y soluciones de aproximación a ecuaciones diferenciales para las cuales no existe una formula exacta. Las matemáticas son muy usadas en investigaciones de ciencias de la computación, asimismo, son fuertemente aplicadas en algoritmos de grafos y áreas de visión por computadora.

Algunas aplicaciones matemáticas prácticas comunes son: números primos, máximo común divisor (MCD), mínimo común múltiplo (mcm), geometría básica, fracciones y números complejos.

Números primos

Un número primo es aquel que solo es divisible entre uno y sí mismo. Por ejemplo 2, 3, 5, 79, 311 y 1931 son todos primos, mientras que 21 no es primo porque es divisible entre 3 y 7. Para encontrar si un número n es primo simplemente checamos si se puede dividir entre los números inferiores a n. Usamos el operador módulo para checar la divisibilidad:

Podemos mejorar este código si nos damos cuenta que sólo necesitamos checar la divisibilidad en los valores para i que son menores o iguales que la raíz cuadrada de n (a la que llamaremos m). Si n divide a un número que es mayor a m entonces tendremos que el resultado de esa división será un número menor que m y por lo tanto n dividirá un número menor que m. Otra optimización es que no existen primos pares mayores que 2. Una vez que checamos que n es impar, podemos incrementar el valor de i por 2 unidades. Finalmente escribimos el método con las optimizaciones:

Ahora, supongamos que necesitamos encontrar los primos del 1 al 100000. Entonces tendríamos que llamar el método anterior 100000 veces. Sería muy ineficiente repetir los mismos cálculos una y otra vez. En esta situación un mejor método a usar es la criba de Eratóstenes. La criba de Eratóstenes obtendrá todos los primos desde el 2 hasta el número n. Comienza asumiendo que todos los números son primos. Entonces toma el primer número primo y remueve todos sus múltiplos. Entonces se aplica el mismo método al siguiente primo. Continuamos hasta que todos los números son procesados. Por ejemplo, si consideramos encontrar los primos en el rango del 2 al 20:

2 es el primer primo entonces:

El siguiente número sin tachar es el 3, por lo tanto es el siguiente primo. Tachamos los múltiplos de 3:

Los siguientes números son primos  ahí termina el algoritmo. El código de la criba:

En el código anterior, lo que hacemos es crear un arreglo booleano que almacena la primalidad de cada número menor o igual que n en su respectiva posición. Si primos[i] es verdadero entonces i es primo.

Máximo común divisor (MCD), mínimo común múltiplo (mcm)

El MCD de dos números a y b es el número más grande que divide a ambos uniformemente. Podemos comenzar con el más pequeño de los 2 números y de ahí disminuir hasta que encontremos un número que los divida a ambos:

Este método es suficientemente rápido para la mayoría de las aplicaciones, sin embrago existe un método más rápido llamado algoritmo de Euclides. El algoritmo de Euclides itera sobre los dos números hasta que el cero es encontrado. Por ejemplo, supongamos que queremos encontrar el MCD de 2336 y 1314. Comenzamos expresando el número más grande (2336) en términos del más pequeño (1314) más el residuo:

Ahora hacemos lo mismo con 1314 y 1022:

Continuamos el proceso hasta que el residuo sea cero:

El último residuo diferente de cero es el MCD. Entonces el MCD de 2336 y 1314 es 146. Este algoritmo puede ser fácilmente codificado como una función recursiva:

Usando este algoritmo podemos encontrar el mcm de dos números. Por ejemplo el mcm de 6 y 9 es 18, porque 18 es el número más pequeño que los divide a ambos. Aquí el código para el mcm:

En el siguiente artículo continuaremos con geometría básica, fracciones y números complejos.

Por Raúl Alberto Soto Cruz del CTIN