En matemáticas , el tamiz de Atkin es un algoritmo moderno para encontrar todos los números primos hasta un número entero especificado. Comparado con el antiguo tamiz de Eratóstenes , que delimita múltiplos de primos, el tamiz de Atkin realiza un trabajo preliminar y luego delimita múltiplos de cuadrados de primos, logrando así una mejor complejidad teórica asintótica . Fue creado en 2003 por AOL Atkin y Daniel J. Bernstein . [1]
Algoritmo
En el algoritmo:
- Todos los restos son de módulo -sixty restos (dividir por el número 60 y devolver el resto).
- Todos los números, incluyendo X e Y , son números enteros positivos.
- Dar la vuelta a una entrada en la lista de tamices significa cambiar la marca (principal o no primaria) a la marca opuesta.
- Esto da como resultado que los números con un número impar de soluciones a la ecuación correspondiente sean potencialmente primos (primos si también están libres de cuadrados), y los números con un número par de soluciones son compuestos.
El algoritmo:
- Cree una lista de resultados, llena de 2, 3 y 5.
- Cree una lista de tamices con una entrada para cada entero positivo; todas las entradas de esta lista deben marcarse inicialmente como no principales (compuestas).
- Para cada número de entrada n en la lista de tamices, con módulo sesenta resto r :
- Si r es 1, 13, 17, 29, 37, 41, 49 o 53, invierta la entrada de cada posible solución a 4 x 2 + y 2 = n . El número de operaciones de volteo como una relación al rango de tamizado para este paso se aproxima4 √ π/15[1] × 8/60 (el "8" en la fracción proviene de los ocho módulos manejados por esta cuadrática y el 60 porque Atkin calculó esto en base a un número par de ruedas de módulo 60), lo que da como resultado una fracción de aproximadamente 0.1117010721276 ....
- Si r es 7, 19, 31 o 43, invierta la entrada para cada posible solución a 3 x 2 + y 2 = n . El número de operaciones de volteo como una relación al rango de tamizado para este paso se aproxima a π √ 0.12 [1] × 4/60 (el "4" en la fracción proviene de los cuatro módulos manejados por esta cuadrática y el 60 porque Atkin calculó esto en base a un número par de ruedas de módulo 60), lo que da como resultado una fracción de aproximadamente 0.072551974569 ....
- Si r es 11, 23, 47 o 59, invierta la entrada para cada posible solución a 3 x 2 - y 2 = n cuando x > y . El número de operaciones de volteo como una relación al rango de tamizado para este paso se aproxima a √ 1,92 ln ( √ 0,5 + √ 1,5 ) [1] × 4/60 (el "4" en la fracción proviene de los cuatro módulos manejados por esta cuadrática y el 60 porque Atkin calculó esto basándose en un número par de ruedas de módulo 60), lo que da como resultado una fracción de aproximadamente 0.060827679704 ....
- Si r es otra cosa, ignórela por completo.
- Comience con el número más bajo en la lista de tamices.
- Tome el siguiente número en la lista de tamices aún marcado como principal.
- Incluya el número en la lista de resultados.
- Eleva el número al cuadrado y marca todos los múltiplos de ese cuadrado como no primos. Tenga en cuenta que los múltiplos que se pueden factorizar por 2, 3 o 5 no necesitan marcarse, ya que se ignorarán en la enumeración final de primos.
- Repita los pasos del cuatro al siete. El número total de operaciones para estas repeticiones de marcar los cuadrados de los números primos como una relación del rango de tamizado es la suma de la inversa de los números primos al cuadrado, que se aproxima a la función zeta primo (2) de 0,45224752004 ... menos 1/2 2, 1/3 2, y 1/5 2 para aquellos primos que han sido eliminados por la rueda, con el resultado multiplicado por dieciséis/60para la proporción de golpes de rueda por rango; esto da como resultado una relación de aproximadamente 0,01363637571 ...
Sumando las relaciones de operaciones anteriores, el algoritmo anterior toma una relación constante de operaciones de volteo / marcado al rango de tamizado de aproximadamente 0,2587171021 ...; A partir de una implementación real del algoritmo, la relación es de aproximadamente 0,25 para rangos de tamizado tan bajos como 67.
Pseudocódigo
El siguiente es un pseudocódigo que combina los algoritmos de Atkin 3.1, 3.2 y 3.3 [1] usando 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 el algoritmos, para una versión sencilla del algoritmo que admite el empaquetado 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's / y's impares / pares para reducir el cálculo 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 la rueda para una rueda 2/3/5 rodada 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 }// Inicializar 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// Poner candidatos primos: // números enteros que tienen un número impar de // representaciones mediante ciertas formas cuadráticas. // Paso del algoritmo 3.1: para n ≤ límite , n ← 4 x² + y² donde x ∈ { 1 , 2 , ...} y y ∈ { 1 , 3 , ...} // todas las y impares de x si n mod 60 ∈ { 1 , 13 , 17 , 29 , 37 , 41 , 49 , 53 } : is_prime ( n ) ← ¬ is_prime ( n ) // alternar estado // Algoritmo paso 3.2: para n ≤ límite , n ← 3 x² + y² donde x ∈ { 1 , 3 , ...} y y ∈ { 2 , 4 , ...} // solo x impares si n mod 60 ∈ { 7 , 19 , 31 , 43 } : // e y pares is_prime ( n ) ← ¬ is_prime ( n ) // alternar estado // Algoritmo paso 3.3: para n ≤ límite , n ← 3 x² - y² donde x ∈ { 2 , 3 , ...} y y ∈ { x -1 , x -3 , ..., 1 } // todos pares / impares si n mod 60 ∈ { 11 , 23 , 47 , 59 } : // combos pares / impares is_prime ( n ) ← ¬ is_prime ( n ) // alternar estado// Elimina los composites 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 : if is_prime ( n ) : // n es primo, omite los 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 : is_prime ( 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 : if is_prime ( n ) : salida n
Este pseudocódigo está escrito para mayor claridad; aunque se han eliminado algunos cálculos redundantes controlando las combinaciones pares / impares x / y, todavía 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 un equivalente rueda factorizada (2/3/5) tamiz de Eratóstenes . Para mejorar su eficiencia, se debe idear un método para minimizar o eliminar estos cálculos no productivos.
Explicación
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 divisibles por ese primo.
Todos los números n con un resto de módulo sesenta 1, 13, 17, 29, 37, 41, 49 o 53 tienen un resto de 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 un resto de módulo sesenta 7, 19, 31 o 43 tienen un resto de 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 el número es libre de cuadrados (demostrado como el teorema 6.2 de [1] ).
Todos los números n con un resto de módulo sesenta 11, 23, 47 o 59 tienen un resto de 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 el número es libre de cuadrados (demostrado como el teorema 6.3 de [1] ).
Ninguno de los números primos potenciales es divisible por 2, 3 o 5, por lo que no pueden ser divisibles por sus cuadrados. Esta es la razón por la que los cheques sin cuadrados no incluyen 2 2 , 3 2 y 5 2 .
Complejidad computacional
Se puede calcular [1] que la serie anterior de tres operaciones de ecuaciones cuadráticas tiene cada una un número de operaciones que es una razón constante del rango a medida que el rango llega al infinito; además, las operaciones de selección libre de cuadrados primos pueden describirse mediante la función zeta primo (2) con compensaciones y factores constantes, por lo que también es un factor constante del rango a medida que el rango llega al infinito. Por lo tanto, el algoritmo descrito anteriormente puede calcular números primos hasta N usando operaciones O ( N ) 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 requisito de memoria a solo el requerido por los números primos base por debajo de la raíz cuadrada del rango de O ( N 1/2 / log N ) bits de memoria. más un búfer de página mínimo. Este es un rendimiento ligeramente mejor con el mismo requisito 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 una página mínima buffer. Sin embargo, un tamiz de este tipo no supera a un tamiz de Eratóstenes con la máxima factorización práctica de la rueda (una combinación de una rueda de tamizado 2/3/5/7 y compuestos de preselección en los búferes de página de segmento utilizando un 2/3/5/7 / 11/13/17/19), que aunque tiene un poco más de operaciones que el Tamiz de Atkin para rangos muy grandes pero prácticos, tiene un factor constante de menor complejidad por operación en 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 segmentado de páginas de Atkin es la dificultad de implementar las secuencias de selección "libres de cuadrados principales" debido a que el intervalo entre los sacrificios crece rápidamente mucho más allá del intervalo de búfer de página; el tiempo invertido en esta operación en la implementación de Bernstein crece rápidamente a muchas veces el tiempo invertido en los cálculos de ecuaciones cuadráticas reales, lo que significa que la complejidad lineal de la parte que de otra manera sería bastante insignificante se convierte en un gran consumidor de tiempo de ejecución. Por lo tanto, aunque una implementación optimizada puede volver a establecerse en una complejidad de tiempo O (n), este factor constante de aumento de tiempo por operaciones significa que el Tamiz de Atkin es más lento.
Una variación especial modificada de "enumeración de puntos de celosía" que no es la versión anterior del Tamiz de Atkin teóricamente puede calcular primos hasta N usando operaciones O ( N / log log N ) con N 1/2 + o (1) bits de memoria [1] pero esta variación rara vez se implementa. Eso es un poco mejor en rendimiento a un costo muy alto en memoria en comparación con la versión segmentada de página ordinaria y con una versión equivalente pero rara vez implementada del tamiz de Eratosthenes que usa operaciones O ( N ) y O ( N 1 / 2 (log log N ) / log N ) bits de memoria. [3] [4] [5]
Pritchard observó que para los tamices de rueda, uno puede reducir el consumo de memoria mientras se preserva la complejidad del tiempo Big O, pero esto generalmente tiene un costo en un factor constante aumentado por el tiempo por operación debido a la complejidad adicional. Por lo tanto, esta versión especial es probablemente más valiosa como ejercicio intelectual que como un tamiz primario práctico con un tiempo real reducido para un rango de tamizado práctico grande dado.
Ver también
Referencias
- ^ a b c d e f g h i j A.OL Atkin, DJ Bernstein, Prime tamices usando formas cuadráticas binarias , Matemáticas. Comp. 73 (2004), 1023-1030. [1]
- ^ Pritchard, Paul, "Tamices lineales de números primos: un árbol genealógico", Sci. Computación. Programming 9 : 1 (1987), págs. 17–35.
- ^ Paul Pritchard, Un tamiz aditivo sublineal para encontrar números primos, Comunicaciones del ACM 24 (1981), 18-23. Señor 600730
- ^ Paul Pritchard, Explicación del tamiz de rueda, Acta Informatica 17 (1982), 477–485. SEÑOR685983
- ^ Paul Pritchard, Tamices de números primos compactos rápidos (entre otros), Journal of Algorithms 4 (1983), 332-344. SEÑOR729229
enlaces externos
- Artículo sobre Sieve of Atkin y su implementación
- Una implementación optimizada del tamiz (en C )