Hola a todos!
Uno de los posts más exitosos en este blog, ha sido desde su publicación, es «un simple algoritmo para encontrar números primos«. El algoritmo no es tan simple cómo lo mencioné originalmente, aunque aún creo que la idea de almacenar persistentemente los resultados es bastante buena.
Los comentarios giraron mucho en torno a la complejidad del algoritmo. Muchos creen que un algoritmo al ser pequeño (de poco texto) es un algoritmo simple. Sin embargo, no esto no es del todo cierto.
Para detallar lo anterior, he escrito un post donde hablo de la complejidad computacional y porqué es importante. Un problema puede tener muchas soluciones, pero aplicar cada una de ellas puede ser costoso en distintas formas: algunas soluciones tendrán ventajas sobre otras desde distintos puntos de vista.
Por ahora vamos a casarnos con el tradicional punto de vista del tiempo. Queremos resolver un problema en la menor cantidad posible de pasos. En este caso, el problema de encontrar primos.
Empecemos por una solución «fácil»; al menos, fácil a la vista. Para esta parte, quiero estrenar esta forma mostrar código en junto con mis publicaciones en distintos lenguajes de programación. Así, si no estás acostumbrado a mi pseudo-código, a Java o a C; podrás elegir ver el código en el lenguaje que prefieras. Las implementaciones que ofrezco de inicio no son las únicas que podría presentar; se aceptan sugerencias para agregar más implementaciones en otros lenguajes de programación (aunque a mi juicio, ya son bastantes 😛 ).
Desgraciadamente, WordPress.com no permite insertar objetos HTML en los posts directamente, así que me limitaré a dejar el enlace al código.
http://www.nachintoch.mx/code
En fin. Tomando el pseudocódigo como modelo, el algoritmo realiza 11(n /2 -1) +3 operaciones para el peor caso, por lo que el algoritmo tiene una función de complejidad en tiempo lineal. Hasta aquí no se ve tan mal; de hecho el algoritmo «simple» ya incluye algunas optimizaciones: ningún número es divisible por otro más grande que su mitad y excluir al 1 del ciclo nos da otra pequeña ventaja al eliminar sus respectivas 11 operaciones elementales. Pero el algoritmo aún puede mejorarse aún más; ya que por ejemplo, más que la mitad, ningún número es divisible por un número más grande que su raíz.
Además, podemos usar propiedades de números y algunos resultados conocidos en la teoría de números, muestras numéricas o probabilidades para reducir el tiempo del algoritmo. También podríamos a recurrir a la paralelización: crear hilos cada un cierto intervalo de posibles divisores y hacer que todos los hilos concurrentemente («simultáneamente») verifiquen si el número es divisible por algún número en el intervalo que le ha tocado verificar.
Todo esto puede parecer demasiado; el algoritmo (en pseudo-código) es de apenas 6 líneas pequeñas de código ¿no es ya suficientemente bueno, pequeño y rápido? ¡Ni siquiera va a iterar tantas veces como el valor del número que se quiere saber es primo!
Aunque es cierto que se ve pequeño y su complejidad no es tan alta, veamos que pasa en los campos de aplicación del problema.
En la teoría y en como primeras prácticas de programación, este es un problema común que se puede resolver con cualquiera de los algoritmos ya mostrados. Sin embargo, en la práctica; una de las áreas donde determinar si un número es primo o no es crucial, es en la seguridad informática.
Una de las «piedras angulares» de la seguridad informática es la dificultad de encontrar números primos. Pero ¿qué dificultad si ya hemos resuelto el problema con un algoritmo simple? Por ejemplo, los certificados y las capas de encriptación que usa la web con HTTPS; intercambian información cifrada por una llave de 256 bits (comúnmente); es decir, números que pueden ser tan grandes cómo 2²⁵⁶; para darnos una idea, puede ser un número decimal hasta de 78 dígitos. ¿cómo se ve un número de 71 dígitos?
10000000000000000000000000000000000000000000000000000000000000000000000
Y hay muchos más números como ese. ¿cuánto tardaría nuestro programa en determinar si uno de estos números de 71 dígitos es primo?
Considerando el número anterior cómo n, entonces la función de complejidad de nuestro algoritmo T(n) = 11(n /2 -1) +3 nos da 55×10⁶⁹.
Si cada operación elemental pudiera ser realizada en tan solo un milisegundo, entonces el número anterior es la cantidad de milisegundos necesarios para determinar si 1×10⁷⁰ es primo o no (no lo es, porqué es par. Pero seguro algún número cercano a él es primo; y no sólo los cercanos más pequeños, sino también números más grandes). Para ponerlo en perspectiva, los milisegundos anteriores son equivalentes a 1.8945×10⁶⁰ años. Si por el contrario, cada operación se realizara en un nanosegundo, el tiempo que requerimos para determinar si 1×10⁷⁰ es primo son 1.8945×10⁵⁴ años… El tiempo que se estima le queda de vida al son 5 mil millones de años; 5,000’000,000 = 5×10⁹. Nadie; ni si quiera el sol, tienen tiempo de esperar a que nuestro algoritmo determine si estos números son primos.
Usualmente, las nuevas versiones de este tipo de sistemas de seguridad, tienden a aumentar el tamaño de las llaves que usan; normalmente involucrando números primos en alguna forma importante; precisamente porque determinar si un número tan grande como estos es primo, es computacionalmente muy muy costoso. De allí la importancia de buscar nuevos algoritmos para este fin: más rápidos y eficientes.
Desde los días en los que «hablaba con mi hermano» he aprendido que no es trivial crear este tipo de soluciones para estos problemas. Requieren de un profundo estudio y si el lector encuentra curiosidad por esto, los invitaría a buscar y revisar publicaciones académicas donde aparecen propuestas de algoritmos para encontrar primos grandes de forma eficiente y cómo funcionan los algoritmos utilizados en la práctica para este mismo fin.
La moraleja que nos puede quedar, es que por muy simple e inofensivo que parezca un problema; su solución puede ser de grandes implicaciones y puede ser mucho más complicada de lo que aparenta… ¿nunca se ha preguntado cuan difícil es; computacionalmente hablando, resolver una torre de Hanoi de 64 discos? ¿podría el Sol esperar a ver esa solución?
Que el límite sea la imaginación.
Spoiler alert: no, ni el Sol puede esperar a resolver una torre de 64 discos si cada operación toma un milisegundo.
Nachintoch 