Indivisible

«Si una casa está dividida contra sí misma, esa casa no podrá subsistir.»
✝ Santo Evangelio según san Marcos 3,25



El Algoritmo - 2021-04-19

Si uno mira el código C de la versión legacy de Indivisible, verá que el algoritmo ha pasado por algunas optimizaciones durante su desarrollo. No quiero pasar por toda la historia de su desarrollo, ya que actualmente no forman parte de la nueva versión escrita en Rust, mas sí me gustaría exponer cómo funciona el algoritmo actual y los principios que usa, y cómo difiere del algoritmo común al que todos estamos acostumbrados.

Para empezar, sabemos que un número primo es aquel que no es divisible (o que es indivisible) por ningún otro número salvo 1 y sí mismo. Por lo tanto el pseudo-código de un programa que determina si un número es primo o no suele ser de manera siguiente:

Este algoritmo funciona perfectamente, pero es bastante ineficiente ya que consulta muchas variables que sabemos a priori que no serán divisibles, y para otros estamos comprobando de forma redundante debido a la propiedad conmutativa de la multiplicación. Sabemos que cualquier número mayor que n/2 es imposible que sea divisor de n. Lo cual ya podemos cambiar la condición de parada a i <= n/2. Pero esto lo podemos optimizar aún más, conociendo que por la propiedad conmutativa a*b = b*a. Es decir, nunca nos hará falta probar un número mayor que sqrt(n). E.g. si estamos probando si 29 es primo, cuya raíz cuadrada es aproximadamente 5, no tiene sentido comprobar si es divisible por 6, ya que 5*6 = 30, que es igual que 6*5. Por lo tanto ya la condición de parada la podemos actualizar a i <= sqrt(n).

Pero esto aún se puede optimizar un poco más, ya que sabemos que todo número par es divisible por dos, y que todo número que es divisible por un número par también es divisible por dos. Ergo, ¿qué sentido tiene comprobar si n es divisible por los demás números pares? Con esto terminamos con el siguiente algoritmo:

Con este algoritmo optimizado tenemos una complejidad de tiempo, en peor caso, de O(√ n  / 2), que en realidad simplemente se dice O(√ n ).

Pero esta última propiedad de los números compuestos puede ayudar para hacer otra optimización más al algoritmo, sobre todo considerando que Indivisible es principalmente un generador de números primos: todo número compuesto está compuesto por números primos (e.g. 30 = 5*2*3). De este modo, si tenemos una lista de números primos ya generados, tan sólo nos hace falta probar si n es divisible por un primo menor o igual a su raíz cuadrada. De tal modo que:

Distinguimos estos dos algoritmos diciendo que el último es con memoria y el penúltimo es sin memoria. En Indivisible es necesario implementar ambos algoritmos, ya que es posible que el usuario quiera comprobar si un número n es primo, y no dispone de una lista de primos que lleguen a sqrt(n).

Finalmente, en cuanto a la generación de primos, sabemos que simplemente podemos saltar los números pares. De este modo, asumimos que 2 es primo, y empezamos con n = 3.

Cuando finalmente se paralelice la computación de Indivisible, será necesario modificar el algoritmo un poco para evitar las condiciones de carrera, en particular cuando se quiere probar si un n es primo, pero aún no se ha generado un primo mayor o igual que n. Pero ya cuando llegue a esto publicaré otro artículo sobre el asunto.

Última actualización: