En matemáticas , la criba de Atkin es un algoritmo moderno para hallar todos los números primos hasta un entero especificado. En comparación con la antigua criba de Eratóstenes , que marca los múltiplos de los primos, la criba de Atkin realiza un trabajo preliminar y luego marca los múltiplos de los cuadrados de los primos, logrando así una mejor complejidad asintótica teórica . Fue creada en 2003 por AOL Atkin y Daniel J. Bernstein . [1]
En el algoritmo:
El algoritmo:
Sumando las proporciones de operaciones anteriores, el algoritmo anterior toma una proporción constante de operaciones de volteo/marcado para el rango de tamizado de aproximadamente 0,2587171021...; a partir de una implementación real del algoritmo, la proporción es de aproximadamente 0,25 para rangos de tamizado tan bajos como 67.
El siguiente es un pseudocódigo que combina los algoritmos de Atkin 3.1, 3.2 y 3.3 [1] mediante el uso de un conjunto combinado "s" de todos los números módulo 60 excluyendo aquellos que son múltiplos de los números primos 2, 3 y 5, según los algoritmos, para una versión sencilla del algoritmo que admite el empaquetamiento de bits opcional de la rueda; aunque no se menciona específicamente en el documento de referencia, este pseudocódigo elimina algunas combinaciones obvias de x/y impares/pares para reducir los cálculos donde esos cálculos nunca pasarían las pruebas de módulo de todos modos (es decir, producirían números pares o múltiplos de 3 o 5):
límite ← 1000000000 // límite de búsqueda arbitrario // conjunto de posiciones de "golpe" de rueda para una rueda 2/3/5 lanzada dos veces según el algoritmo de Atkin s ← { 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 49 , 53 , 59 } // Inicializa el tamiz con suficientes ruedas para incluir el límite: para n ← 60 × w + x donde w ∈ { 0 , 1 ,..., límite ÷ 60 }, x ∈ s : is_prime ( n ) ← falso // Coloque en candidatos primos: // números enteros que tienen un número impar de // representaciones mediante ciertas formas cuadráticas. // Paso 3.1 del algoritmo: para n ≤ límite , n ← 4 x² + y² donde x ∈ { 1 , 2 ,...} e y ∈ { 1 , 3 ,...} // todas las x son y impares si n mod 60 ∈ { 1 , 13 , 17 , 29 , 37 , 41 , 49 , 53 } : is_prime ( n ) ← ¬ is_prime ( n ) // alternar estado // Paso 3.2 del algoritmo: para n ≤ límite , n ← 3 x² + y² donde x ∈ { 1 , 3 ,...} e y ∈ { 2 , 4 ,...} // solo x impares si n mod 60 ∈ { 7 , 19 , 31 , 43 } : // y pares y's is_prime ( n ) ← ¬ is_prime ( n ) // alternar estado // Paso 3.3 del algoritmo: para n ≤ límite , n ← 3 x² - y² donde x ∈ { 2 , 3 ,...} e y ∈ { x -1 , x -3 ,..., 1 } // todos pares/impares si n mod 60 ∈ { 11 , 23 , 47 , 59 } : // combinaciones pares/impares is_prime ( n ) ← ¬ is_prime ( n ) // alternar estado // Eliminar los compuestos por tamizado, solo para aquellas ocurrencias en la rueda: para n² ≤ límite , n ← 60 × w + x donde w ∈ { 0 , 1 ,...}, x ∈ s , n ≥ 7 : si es_primo ( n ) : // n es primo, omitir múltiplos de su cuadrado; esto es suficiente // porque los compuestos sin cuadrados no pueden entrar en esta lista para c ≤ límite , c ← n² × ( 60 × w + x ) donde w ∈ { 0 , 1 ,...}, x ∈ s : es_primo ( c ) ← falso // un barrido para producir una lista secuencial de primos hasta el límite: salida 2 , 3 , 5 para 7 ≤ n ≤ límite , n ← 60 × w + x donde w ∈ { 0 , 1 ,...}, x ∈ s : si is_prime ( n ) : salida n Este pseudocódigo está escrito para mayor claridad; aunque se han eliminado algunos cálculos redundantes al controlar las combinaciones x/y pares/impares, aún desperdicia casi la mitad de sus cálculos cuadráticos en bucles no productivos que no pasan las pruebas de módulo, de modo que no será más rápido que una criba de Eratóstenes factorizada en rueda equivalente (2/3/5) . Para mejorar su eficiencia, se debe idear un método para minimizar o eliminar estos cálculos no productivos.
El algoritmo ignora por completo cualquier número con resto módulo 60 que sea divisible por dos, tres o cinco, ya que los números con un resto módulo 60 divisible por uno de estos tres primos son a su vez divisibles por ese primo.
Todos los números n con resto módulo sesenta 1, 13, 17, 29, 37, 41, 49 o 53 tienen un resto módulo cuatro de 1. Estos números son primos si y solo si el número de soluciones de 4 x 2 + y 2 = n es impar y el número no tiene cuadrados (demostrado como el teorema 6.1 de [1] ).
Todos los números n con resto módulo sesenta 7, 19, 31 o 43 tienen un resto módulo seis de 1. Estos números son primos si y solo si el número de soluciones de 3 x 2 + y 2 = n es impar y el número no tiene cuadrados (demostrado como el teorema 6.2 de [1] ).
Todos los números n con resto módulo sesenta 11, 23, 47 o 59 tienen un resto módulo doce de 11. Estos números son primos si y solo si el número de soluciones de 3 x 2 − y 2 = n es impar y el número no tiene cuadrados (demostrado como el teorema 6.3 de [1] ).
Ninguno de los posibles primos es divisible por 2, 3 o 5, por lo que no pueden ser divisibles por sus cuadrados. Por eso, las comprobaciones de cuadrados libres no incluyen 2 2 , 3 2 y 5 2 .
Se puede calcular [1] que la serie anterior de tres operaciones de ecuación cuadrática tiene cada una un número de operaciones que es una relación constante del rango a medida que el rango tiende a infinito; así mismo, las operaciones de selección libre de primos cuadrados se pueden describir mediante la función zeta de primos (2) con compensaciones y factores constantes, por lo que también es un factor constante del rango a medida que el rango tiende a infinito. Por lo tanto, el algoritmo descrito anteriormente puede calcular primos hasta N utilizando O ( N ) operaciones con solo O ( N ) bits de memoria.
La versión segmentada de páginas implementada por los autores tiene las mismas operaciones O ( N ) pero reduce el requerimiento de memoria a solo lo requerido por los primos base por debajo de la raíz cuadrada del rango de O( N 1/2 /log N ) bits de memoria más un buffer de página mínimo. Este es un rendimiento ligeramente mejor con el mismo requerimiento de memoria que el tamiz segmentado de páginas de Eratóstenes que usa operaciones O( N log log N ) y los mismos O( N 1/2 /log N ) bits de memoria [2] más un buffer de página mínimo. Sin embargo, un tamiz de este tipo no supera a un Tamiz de Eratóstenes con una factorización de rueda práctica máxima (una combinación de una rueda de tamizado 2/3/5/7 y compuestos de preselección en los buffers de páginas de segmentos usando un patrón 2/3/5/7/11/13/17/19), que aunque tiene ligeramente más operaciones que el Tamiz de Atkin para rangos muy grandes pero prácticos, tiene un factor constante de menor complejidad por operación de aproximadamente tres veces al comparar el tiempo por operación entre los algoritmos implementados por Bernstein en ciclos de reloj de CPU por operación. El principal problema con el Tamiz de Atkin Segmentado por Página es la dificultad para implementar las secuencias de selección "libres de cuadrados primos" debido a que el lapso entre las selecciones crece rápidamente mucho más allá del lapso del buffer de páginas; el tiempo empleado para esta operación en la implementación de Bernstein crece rápidamente a muchas veces el tiempo empleado en los cálculos de ecuaciones cuadráticas reales, lo que significa que la complejidad lineal de la parte que de otro modo sería bastante insignificante se convierte en un importante consumidor de tiempo de ejecución. Por lo tanto, aunque una implementación optimizada puede nuevamente establecerse en una complejidad de tiempo O(n), este factor constante de aumento del tiempo por operación significa que la criba de Atkin es más lenta.
Una variante especial modificada de "enumeración de puntos de red" que no es la versión anterior de la criba de Atkin puede calcular teóricamente números primos hasta N utilizando operaciones O ( N /log log N ) con N 1/2 + o(1) bits de memoria [1], pero esta variante rara vez se implementa. Esto es un poco mejor en rendimiento a un costo muy alto en memoria en comparación con la versión segmentada de página común y con una versión equivalente pero raramente implementada de la criba de Eratóstenes que utiliza operaciones O( N ) y O( N 1/2 (log log N )/log N ) bits de memoria. [3] [4] [5]
Pritchard observó que, en el caso de los tamices de rueda, se puede reducir el consumo de memoria y, al mismo tiempo, conservar la complejidad temporal de Big O, pero esto generalmente tiene como costo un factor constante mayor para el tiempo por operación debido a la complejidad adicional. Por lo tanto, es probable que esta versión especial tenga más valor como ejercicio intelectual que como tamiz principal práctico con un tiempo real reducido empleado para un rango de tamizado práctico grande determinado.