algorithm - El Tamiz de Atkin

math language-agnostic (2)

He estado tratando de aprender algoritmos para generar números primos y encontré Sieve of Atkin en Wikipedia. Entiendo casi todas las partes del algoritmo, excepto algunas. Aquí están las preguntas:

¿Cómo se forman las tres ecuaciones cuadráticas a continuación? 4x ^ 2 + y ^ 2, 3x ^ 2 + y ^ 2 y 3x ^ 2-y2
El algoritmo en wikipedia habla de módulo sesenta, pero no entiendo cómo y dónde se usa en el psudocódigo a continuación.
¿Cómo se encuentran estos recordatorios 1,5,7 y 11?

A continuación se muestra el pseudocódigo de Wikipedia para referencia:

// arbitrary search limit limit ← 1000000 // initialize the sieve for i in [5, limit]: is_prime(i) ← false // put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms for (x, y) in [1, √limit] × [1, √limit]: n ← 4x²+y² if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5): is_prime(n) ← ¬is_prime(n) n ← 3x²+y² if (n ≤ limit) and (n mod 12 = 7): is_prime(n) ← ¬is_prime(n) n ← 3x²-y² if (x > y) and (n ≤ limit) and (n mod 12 = 11): is_prime(n) ← ¬is_prime(n) // eliminate composites by sieving for n in [5, √limit]: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit} print 2, 3 for n in [5, limit]: if is_prime(n): print n

El pseudocódigo de Sieve of Atkin del artículo de Wikipedia que ha citado contiene las respuestas a sus preguntas o la discusión sobre el artículo para el que Will Ness ha proporcionado un enlace, aunque es posible que no pueda reunir la información. Las respuestas cortas son las siguientes:

Las tres ecuaciones provienen de la prueba matemática de Atkin de que todos los primos aparecerán como las soluciones de una o más de esas tres ecuaciones con las condiciones de módulo apropiadas para todos los valores válidos de las variables ''x'' e ''y'', y de hecho demostró más que los números primos verdaderos serán aquellos números que tengan un número impar de soluciones a esas tres ecuaciones (dejado como verdadero cuando se alternó un número impar de veces desde las condiciones iniciales de falso) con las condiciones de módulo para cada uno excluyendo aquellos números que son divisibles por cuadrados de primos encontrados menores o iguales a la raíz cuadrada del número probado.
El verdadero Tamiz de Atkin se basa en un conjunto de condiciones de módulo 60; este pseudo código representa una simplificación donde hay menos rangos de condiciones para cada ecuación usando un conjunto de condiciones de módulo 12 (5 × 12 = 60); sin embargo, esto hace que se realice un trabajo adicional del 20% debido a la redundancia introducida en este Nuevo conjunto de condiciones. También es la razón por la que este pseudo código simplificado debe comenzar su escaneo principal en 5 en lugar del normal 7 y para realizar las eliminaciones libres de cuadrados de primos base a partir de un primo base de 5 a un costo adicional en el tiempo de ejecución como factores de De lo contrario, 5 no se manejan correctamente. El motivo de esta simplificación es tal vez sacrificar cierta sobrecarga de código adicional para facilitar la complejidad del código al tener que verificar los valores, aunque esto se puede hacer con una sola tabla de consulta, mientras que el extra del 30% en el trabajo debido al uso de módulo 12 No se puede reducir.
Los "recordatorios" (se deben escribir los restos ) se encuentran en los pseudo códigos que usted indica que representan el operador de módulo en cualquier lenguaje informático que se pueda usar, a menudo representado por el símbolo "%" en lenguajes informáticos como como C, Java, C #, F #, etcétera. Este operador produce el resto entero después de una división entera del dividendo (el primero de los números, antes del ''mod'') por el divisor (el segundo de los números, después del símbolo ''mod''). La razón por la que los restos son solo cuatro en lugar de los 16 que se utilizan en el algoritmo de módulo 60 completo se debe a las simplificaciones de la reducción a un algoritmo de módulo 12. Notará que con las condiciones de módulo 12, la condición "4x" pasa a 25, que normalmente se eliminaría con las condiciones de módulo 60, por lo que muchos compuestos que contienen 25 como un factor deben eliminarse mediante el número primo adicional de 5 cuadrados de cheques gratis. . De manera similar, 55 pasan la verificación "3x +" y 35 la verificación "3x-" donde no lo harían para el algoritmo de módulo 60 completo.

Como se discutió en la sección "Discusión" del artículo de Wikipedia y se insinuó anteriormente, este pseudo código nunca es mucho más rápido que las implementaciones básicas del Tamiz de Eratóstenes (SoE) solo de probabilidades, y mucho menos una que usa el mismo grado de factorización de la rueda debido a sus ineficiencias : las variables ''x'' y ''y'' no necesitan extenderse en todo el rango hasta la raíz cuadrada del rango cribado para muchos casos (mencionado en el artículo), el uso adecuado de la rueda de módulo 60 recupera las redundancias en la el uso de la simplificación de módulo 12 (como mencioné anteriormente), y hay patrones de red de módulo en las soluciones a las ecuaciones cuadráticas de modo que las condiciones que utilizan las operaciones de módulo (computacionalmente lenta) no necesitan ser probadas mediante el uso de un algoritmo que automáticamente omite aquellas soluciones que no satisfacen esas condiciones de módulo según los patrones de celosía (solo se mencionan de manera muy oscura en el documento completo de Atkin y Bernstein).

Para responder a una pregunta que no hizo pero debería tener: "¿Por qué usar el Tamiz de Atkin?" .

La razón principal por la que se implementa el Tamiz de Atkin (SoA) en lugar del Tamiz de Eratóstenes (SoE) es que es "Conocimiento de Internet" que la SOA es más rápida. Hay dos razones para esta creencia, como sigue:

Se asume que el SoA es más rápido porque la complejidad computacional asintótica es menor para él que para el SoE por un factor de log (log n) donde n es el rango de números primos que se tamizan. En la práctica, pasando de un rango de dos a la potencia 32 (cuatro billones más) a dos a la potencia 64 (aproximadamente 2 seguidos por 19 ceros), este factor es seis sobre cinco es igual a 1.2. Eso significa que el verdadero SoE debería tomar 1.2 veces el tiempo esperado por solo una relación lineal cuando se tamiza al rango de números de 64 bits en comparación con el rango de números de 32 bits, mientras que el SoA tendrá una relación lineal si todos fueran ideales . Puede apreciar que, en primer lugar, este es un factor muy pequeño para una diferencia tan grande en los rangos de números y, en segundo lugar, que este beneficio solo se mantiene si los dos algoritmos tienen el mismo o casi el mismo rendimiento en un rango razonable de números primos.
Lo que no se entiende claramente por ese "conocimiento de Internet" es que estas cifras solo se aplican cuando uno compara la relación de rendimiento en un rango dado en comparación con otro rango dado para el mismo algoritmo , no como una comparación entre diferentes algoritmos. Por lo tanto, es inútil como una prueba de que el SoA será más rápido que el SoE ya que el SoA podría comenzar con una sobrecarga mayor para un rango de tamiz dado de un algoritmo SoE particular como en el siguiente ejemplo de SoE optimizado.
Se cree que el SoA es más rápido debido a la comparación computacional realizada y publicada por Atkin y Bernstein según su artículo vinculado en el artículo de Wikipedia. Si bien el trabajo es preciso, solo se aplica a las limitaciones artificiales que hicieron en el algoritmo SoE que compararon: como el algoritmo SoA se basa en la factorización de módulo 60 que representa dos rotaciones de la rueda de factorización de 2,3,5, también limitaron el SoE. Algoritmo para esa misma factorización de rueda. Al hacer esto, el SoE realiza aproximadamente 424,000 operaciones de sacrificio de números compuestos en el rango de mil millones probado, mientras que un SoA totalmente optimizado como probado tiene alrededor de 326,000 operaciones de sacrificio sin cuadratura combinadas y cuadradas, cada una de las cuales toma aproximadamente el mismo tiempo que cada operación de sacrificio de número compuesto en el SoE por estar escrito en el mismo estilo. Esto significa que el SoA es aproximadamente un 30% más rápido que el SoE para este conjunto particular de condiciones de factorización de la rueda , y eso es exactamente lo que mostraron las pruebas de comparación de Atkins y Bernstein.
Sin embargo, el SoA no responde a niveles adicionales de factorización de la rueda, ya que el nivel 2,3,5 está "integrado" en el algoritmo, mientras que el SoE responde a niveles adicionales: utilizando una rueda 2,3,5,7 La factorización da como resultado aproximadamente el mismo número de operaciones, lo que significa el mismo rendimiento para cada una. Se puede utilizar incluso un nivel de factorización de rueda parcialmente mayor que el nivel de 2,3,5,7 para obtener el número de operaciones para SoE aproximadamente un 16.7% menos que SoA, para un mejor rendimiento proporcional. Las optimizaciones requeridas para implementar estos niveles adicionales de factorización de la rueda son en realidad más simples que la complejidad del código para implementar el SoA original optimizado. La huella de memoria para implementar estas implementaciones segmentadas en páginas comparables es aproximadamente la misma, ya que es el tamaño de los búferes de página más la matriz de primos base.
Además, ambos se beneficiarían de estar escritos en un estilo de "búsqueda de estado de la máquina" que ayudaría a una mejor optimización usando código en línea y desenrollado de bucle extremo, pero el SoE se adapta más a este estilo que el SoA debido a que es un algoritmo más simple.

Por lo tanto, para rangos de tamiz de hasta aproximadamente el rango numérico de 32 bits, el SoE optimizado al máximo es aproximadamente un 20% más rápido (o más con una mayor factorización de la rueda) que el SoA; sin embargo, el SoA tiene esta ventaja de complejidad computacional asintótica, por lo que habrá algún punto en el que se alcance. Ese punto estará aproximadamente en el rango donde la proporción de log (log n) a log (log (2 ^ 32)) o 5 es 1.2 o un rango de aproximadamente 2 veces diez a la decimonovena potencia, un número extremadamente grande. Si la ejecución de SoA optimizada en una computadora de escritorio moderna tomara alrededor de un tercio de segundo para calcular los números primos en el rango de números de 32 bits, y si la implementación fuera ideal, ya que al tomar un aumento de tiempo lineal con un rango en aumento, tomaría alrededor de 45 años para calcular los números primos a este rango. Sin embargo, el análisis de los números primos en estos altos rangos se realiza a menudo en pequeños segmentos, para los cuales el uso del SoA sería teóricamente práctico en comparación con el SoE para tamices de números muy grandes, pero por un factor muy pequeño.

EDIT_ADD: En realidad, ni la página segmentada SoE ni la SoA continúan ejecutándose en tiempo lineal para estos rangos enormes en comparación con los rangos inferiores, ya que ambos tienen problemas con las operaciones de "alternancia" y "selección" y pierden eficiencia debido a tener para saltar grandes cantidades de páginas por salto; esto significa que ambos requerirán algoritmos modificados para manejar este "salto de página" y la muy pequeña ventaja para el SoA puede borrarse completamente si hay alguna ligera diferencia en la forma en que se hace esto. El SoA tiene muchos más términos en las "tablas de salto" que en el SoE por aproximadamente la relación inversa entre el número de primos encontrados hasta la raíz cuadrada del rango a ese rango, y esto probablemente agregará una O (log n) término para ambos en el procesamiento pero un aumento constante de factor constante para el SoA que tiene un mayor número de entradas en la "tabla de salto". Este hecho adicional prácticamente anulará completamente cualquier ventaja de SoA sobre SoE, incluso para rangos extremadamente grandes. Además, el SoA tiene una sobrecarga constante de más bucles individuales requeridos para los muchos más casos en la implementación de las condiciones para las tres ecuaciones cuadráticas separadas más el bucle "cuadrados libres primos" en lugar de un bucle de selección de primos, por lo que nunca puede tener una tiempo de cálculo promedio por operación como SoE cuando está totalmente optimizado. END_EDIT_ADD

EDIT_ADD2: Mi opinión es que gran parte de la confusión sobre el Tamiz de Atkin se debe a las deficiencias del pseudo código del artículo de Wikipedia que se cita en la pregunta, por lo que se ha llegado con una versión algo mejor del pseudo código que aborda al menos algunas de las deficiencias relacionadas con el rango de las variables ''x'' e ''y'' y la confusión entre módulo 12 y módulo 60 de la siguiente manera:

limit ← 1000000000 // arbitrary search limit // Initialize the sieve for i in {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: is_prime(i) ← false // Put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms. while n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // odd y''s if n mod 60 ∈ {1,13,17,29,37,41,49,53}: is_prime(n) ← ¬is_prime(n) while n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd if n mod 60 ∈ {7,19,31,43}: // x''s and even y''s is_prime(n) ← ¬is_prime(n) while n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all if n mod 60 ∈ {11,23,47,59}: // even/odd odd/even combos is_prime(n) ← ¬is_prime(n) // Eliminate composites by sieving, only for those occurrences on the wheel for n² ≤ limit where n ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free while c ≤ limit, c ← n² × k where k ∈ {1,7,11,13,17,19,23,29, 31,37,41,43,47,49,53,59,...}: is_prime(c) ← false output 2, 3, 5 for n ≤ limit when n ← 60 × k + x where k ∈ {0..} and x ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61}: if is_prime(n): output n

Lo anterior parece bastante simple y es un buen algoritmo, excepto que aún no es más rápido que un Tamiz básico de Eratóstenes que usa la misma rueda de factorización 2; 3; 5 porque desperdicia casi la mitad de su bucle interno en las operaciones de conmutación que fallan pruebas de modulo. Demostrar:

A continuación se muestra el patrón repetitivo 4x² + y² del módulo de calificación 60 en un rango de 15 valores de ''x'' verticalmente y 15 valores impares de ''y'' horizontalmente; ambos comenzando en uno. Tenga en cuenta que son simétricos con respecto a un eje vertical, pero solo 128 de 225 o 256 de 450 para un rango completo de 30 valores de "x" son operaciones de alternancia válidas:

0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 37 0 1 0 0 37 0 0 0 37 0 0 1 0 37 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 41 49 0 29 1 41 29 0 29 41 1 29 0 49 41 0 0 49 13 0 0 13 0 13 0 0 13 49 0 0 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 0 0 49 13 0 0 13 0 13 0 0 13 49 0 0 41 49 0 29 1 41 29 0 29 41 1 29 0 49 41 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 37 0 1 0 0 37 0 0 0 37 0 0 1 0 37 17 0 41 0 37 17 0 1 0 17 37 0 41 0 17 0 13 29 53 0 0 53 49 53 0 0 53 29 13 0 1 0 0 49 0 1 49 0 49 1 0 49 0 0 1

A continuación se muestra el patrón repetitivo 3x² + y² de los módulos de calificación 60 en un rango de 5 valores impares de ''x'' verticalmente y 15 valores pares de ''y'' horizontalmente. Observe que son simétricos con respecto a un eje horizontal, pero solo 48 de 75 o 144 de 450 para un rango completo de 30 valores de ''x'' son operaciones de alternancia válidas, ya que 144 de 450 operaciones no válidas, incluso con ''x'' e impar ''y'' ya han sido eliminados:

7 19 0 7 43 0 19 19 0 43 7 0 19 7 0 31 43 0 31 7 0 43 43 0 7 31 0 43 31 0 19 31 0 19 0 0 31 31 0 0 19 0 31 19 0 31 43 0 31 7 0 43 43 0 7 31 0 43 31 0 7 19 0 7 43 0 19 19 0 43 7 0 19 7 0

A continuación se muestra el patrón de repetición 3x²-y² de los módulos de calificación 60 en un rango de 5 valores impares de ''x'' verticalmente y 15 valores pares de ''y'' horizontalmente. Tenga en cuenta que son simétricos con respecto a un eje horizontal, pero solo 48 de 75 o 224 de 450 para un rango completo de 30 valores de "x" son operaciones de alternancia válidas:

59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 23 11 0 23 47 0 11 11 0 47 23 0 11 23 0 11 59 0 11 0 0 59 59 0 0 11 0 59 11 0 23 11 0 23 47 0 11 11 0 47 23 0 11 23 0 59 47 0 59 23 0 47 47 0 23 59 0 47 59 0

A continuación se muestra el patrón repetitivo 3x²-y² de los módulos de calificación 60 en un rango de 5 valores pares de ''x'' verticalmente y 15 valores impares de ''y'' horizontalmente. Tenga en cuenta que son simétricos con respecto a un eje vertical, pero solo 48 de 75 o 224 de 450 para un rango completo de 30 valores de "x" son operaciones de conmutación válidas:

11 0 47 23 0 11 23 0 23 11 0 23 47 0 11 47 0 23 59 0 47 59 0 59 47 0 59 23 0 47 47 0 23 59 0 47 59 0 59 47 0 59 23 0 47 11 0 47 23 0 11 23 0 23 11 0 23 47 0 11 59 0 0 11 0 59 11 0 11 59 0 11 0 0 59

Como se puede determinar mediante la inspección de las tablas anteriores, para el pseudocódigo como el anterior, hay un rango de repetición global de 30 valores de x (incluidos los nivelaciones y las probabilidades) que solo tiene 688 operaciones válidas de un total de 1125 operaciones combinadas; por lo tanto, desperdicia casi la mitad de su procesamiento en solo omitir condicionalmente los valores debido a que las operaciones de omisión no productivas son parte de los bucles más internos. Hay dos métodos posibles para eliminar esa redundancia de "impacto" de manera ineficiente, como sigue:

El método descrito en el documento de Atkin y Bernstein, que utiliza los patrones reconocidos en los módulos combinados de ''x'' e ''y'' para procesar solo los "golpes" de módulo utilizando el hecho de que, una vez, se localiza un módulo determinado en el patrón, luego hay una secuencia infinita de valores en ese modulo (es igual a la posición de bit de rueda) donde cada patrón está separado por un desplazamiento fácil de calcular (variable) que tiene la forma "posición actual más A por el valor actual de ''x'' más B "y" la posición actual más C multiplicada por el valor actual de ''y'' más D "donde A, B, C y D son constantes simples (significado simple, pequeño, fácil de manipular). Bernstein utilizó ese método con la ayuda adicional de muchas tablas de búsqueda (LUT).
El método de creación de tablas de consulta (LUT) de estado de patrón general (una para cada una de las cuatro tablas anteriores más una para el bucle libre de cuadrados primarios menores) indexado por los valores actuales de módulo de ''x'' combinados con el módulo de ''y'' para encontrar los parámetros A, B, C y D para omitir, no al siguiente patrón, sino a la siguiente posición en la secuencia horizontal. Es probable que esta sea la opción de mayor rendimiento, ya que permite una reducción extrema del ciclo de reloj por operación utilizando el código del bucle desenrollado y producirá un código más eficiente para grandes rangos cuando la segmentación de páginas como los saltos por bucle son más pequeños en promedio . Esto probablemente hará que los ciclos de reloj por ciclo sean similares a los de un Tamiz de Eratóstenes altamente optimizado como en primesieve , pero es probable que no alcancen ese nivel debido a tener que calcular los tamaños de paso variables en lugar de poder usar compensaciones primarias fijas para SoE.

Por lo tanto, existen tres objetivos rectores para reducir el tiempo de funcionamiento de un tamiz principal, como se indica a continuación:

Un tamiz exitoso reduce el número de operaciones, en las que incluso el SoA "optimizado por impacto" falla en comparación con un SoE altamente factorizado en la rueda en aproximadamente un 16.7% para rangos de unos pocos miles de millones.
Un tamiz exitoso reduce los ciclos de reloj de la CPU por operación, por lo que el SoA falla en comparación con un SoE altamente optimizado como primesieve debido a que sus operaciones son más complejas debido a los incrementos variables, de nuevo probablemente entre un 20% y un 60%. El primegen (SoA) de Atkin y Bernstein toma aproximadamente 4.5 en comparación con aproximadamente 2.5 ciclos de reloj por operación para primesieve (SoE) para un rango de mil millones para cada uno, pero tal vez el SoA podría acelerarse un poco prestando algunas de las técnicas de optimización de primesieve
Un tamiz exitoso tiene una complejidad de código razonablemente baja, de modo que puede extenderse más fácilmente a rangos más grandes utilizando técnicas como el "tamizado de cubetas" y otras optimizaciones de segmentación de páginas. Para esto, el Tamiz de Atkin falla miserablemente, ya que se vuelve exponencialmente más complejo para la segmentación de páginas de grandes rangos de números. Es extremadamente complejo escribir un programa SoA que compita incluso con el primegen (SoA) de Bernstein y mucho menos con primesieve, mientras que es bastante fácil escribir código que se aproxime al mismo rendimiento que primesieve.
Un tamiz exitoso tiene una complejidad empírica más baja, que el SoA tiene por encima del SoE por un factor de (log (log n) donde n es el rango superior que se debe tamizar, pero esa proporción extra pequeña no es suficiente para compensar para los dos índices de pérdida combinados de arriba, ya que este factor se reduce a medida que aumenta el rango. END_EDIT_ADD2

Así que la respuesta a la pregunta "¿Por qué usar el Tamiz de Atkin?" es "No hay ninguna razón para usarlo si el SoE se implementa con optimizaciones de factorización de rueda máxima hasta que los números cribados sean extremadamente grandes (rango de números de 64 bits y superior) y luego la ventaja de SoA sea muy pequeña y tal vez no sea realizable en Todo depende de ajustes muy pequeños en optimizaciones relativas ". .

Como respuesta a otra pregunta similar sobre el Tamiz de Atkin, publiqué una versión C # segmentada de la página del SoE optimizado según lo anterior en: https://.com/a/20559687/549617 .

En mi respuesta original a esta pregunta , para ayudar a comprender mejor el algoritmo del Tamiz de Atkin, extendí el pseudo código del Tamiz de Atkin (SoA) de Wikipedia para corregir algunas de las deficiencias en el algoritmo simplificado "módulo 12" dado, que muchos encuentran confusos en comparación con el algoritmo completo "módulo 60". Además, el algoritmo original de pseudo código de Wikipedia conduce a implementaciones ineficientes; específicamente, los rangos de las variables ''x'' e ''y'' son cada uno más anchos de lo necesario y la simplificación de módulo 12 resulta en un 20% adicional de trabajo redundante. Sin embargo, como se discutió en esa respuesta, ese pseudo código aún no es eficiente, ya que las pruebas de módulo aún se encuentran en los bucles de solución cuadráticos más internos y, por lo tanto, casi la mitad de esos ciclos de solución no son productivos para aquellas soluciones que no pasan las pruebas de módulo; esto significa que un programa que implemente ese pseudo código probablemente sea el doble de lento que lo necesario, incluso cuando no haya un cuello de botella en la velocidad de acceso a la memoria.

El algoritmo utilizado por Atkin y Bernstein en su programa "primegen" para evitar esa redundancia de bucle se puede entender mejor mediante una progresión a través de las siguientes observaciones basadas en las tablas de "aciertos" en mi respuesta anterior:

La simetría de las tablas de "aciertos" depende de si ''y'' es impar (simetría vertical) o incluso (simetría horizontal).
Por lo tanto, si queremos que el avance de los patrones proceda en la dirección horizontal como se muestra allí, podemos cambiar el orden de los bucles ''x'' e ''y'' para los "3x +" y "3x-; odd x -> incluso y "casos que significan casos" x "impares.
Ahora es fácil eliminar los cero casos para las dos tablas "3x" invertidas que solo tienen cinco repeticiones horizontalmente por una condición en un bucle externo, como aquellos casos donde "y mod 3 es igual a 0" más los tres casos adicionales solo para el medio " eje "columna donde" y mod 5 es igual a 0 ".
Para el último caso "3x-; incluso x -> impar y", es fácil eliminar la mayoría de los cero simplemente filtrando aquellos casos en los que "(y + 2) mod 3 es igual a 0" más los dos casos adicionales solo para el última línea donde "(x mod 60) es igual a 59" donde "(y + 2) mod 5 es igual a 0" (eliminaciones duplicadas para la columna del eje vertical simétrico, que siempre se elimina). Aunque parece que estas "pruebas y" tienen que ocurrir en un bucle interno, ya que solo hay cinco "aciertos" por lado del eje de simetría vertical, pueden ser codificados en línea por el bucle ''x''.
Las eliminaciones más difíciles son para la tabla "4x" donde el patrón es más complejo: hay cinco patrones horizontales distintos donde se puede reconocer cada uno porque el "(x mod 60) para la primera columna" es distinto, con uno de los primeros los patrones de fila cero en la primera tabla anterior tienen un módulo de 5 y el otro un módulo de 25; ahora los cinco patrones diferentes se pueden determinar al "alinear" los casos como compensaciones a cada lado del eje vertical simétrico para cada patrón.
El espacio a la siguiente fila es exactamente 4 × ((x + 1) ² - x²) o 8x + 4 para la primera tabla, (y + 2) ² - y² o 4y + 4 para las dos nuevas tablas (intercambiadas) y 3 × ((x + 2) ² - x²) o 12x + 12 para la última tabla.
Para todas las tablas (ahora) simétricas verticalmente, el desplazamiento del eje central se puede determinar a partir del desplazamiento de la primera columna como (y + 16) ² - y² o 32y + 256 para las filas largas y 3 × ((x + 4) ² - x²) o 24x + 48 para las filas cortas.
De manera similar, los desplazamientos simétricos a ambos lados del eje vertical pueden calcularse fácilmente a partir del desplazamiento del eje vertical, por ejemplo, por el par (y + 2) ² - y² o 4 + 4x con (y - 2) ² - y² o 4 - 4y donde y es el desplazamiento del eje central para los casos de fila larga y más y menos dos posiciones; el caso para la fila corta "x" es similar pero solo se multiplica por tres para la escala general de los valores "3x" ''x''.
Los filtros anteriores determinados por las condiciones de las variables horizontales parecen romper nuestro objetivo de eliminar el código condicional en los bucles internos, pero esa regla no se aplica cuando determinar que el patrón no es el bucle interno, sino que comienza una serie completa de nuevos bucles internos en todos los patrones horizontalmente en la matriz para cada elemento válido del patrón. Esto funciona porque podemos demostrar matemáticamente que cada una de las mismas posiciones equivalentes en el siguiente patrón (que tiene el mismo módulo) se separan de la siguiente manera: Para el patrón horizontal avanza 30 puntos para los casos de fila larga, los patrones están separados por (x + 30) ² - x² o 60x + 900 así que 60 × (x + 15); para el patrón horizontal avanza en 10 para los casos de fila corta, los patrones están separados por 3 × ((x + 10) ² - x²) por lo que 60 * (x + 5). Dado que ambos tienen un módulo 60 de cero, esta es la explicación exacta de por qué hay patrones de repetición del mismo módulo en cada posición. Por lo tanto, una vez que encontramos el desplazamiento para cada posición de la esquina superior izquierda, podemos determinar el módulo y el desplazamiento para las ubicaciones de inicio para las posiciones del patrón que no son cero y simplemente rodar un bucle interno utilizando las relaciones del patrón desde ese punto hasta el límite de la matriz de tamices .
Todos los incrementos de columna y fila anteriores se pueden hacer sin usar una operación de "división" usando la adición de módulo donde el algoritmo realiza un seguimiento de los pares de cocientes y módulos de 60 con solo una operación de "comprobación y ajuste de desbordamiento" en el módulo / cociente emparejarse después de cada operación, pero el código condicional para hacer la "comprobación y ajuste" es probablemente más costoso computacionalmente que la forma en que está escrito, por lo que la mayoría de los compiladores de optimización modernos generarán una operación de multiplicación utilizando las características de truncamiento de desbordamiento para reemplazar la operación de división costosa computacionalmente para la división por enteros pequeños, que generalmente toma menos tiempo que la combinación de operaciones más el código condicional requerido para el método de "verificar y ajustar" o el uso de una operación de división directa.
Los conjuntos de eliminaciones anteriores funcionan muy bien para una representación de bits empaquetados de los primos candidatos, ya que cada uno de los 16 valores de módulo válidos se puede representar como un bit en una palabra de 16 bits y el índice de palabras presenta los índices de cada módulo 60 rueda; por lo tanto, podemos avanzar por incrementos pares divisibles uniformemente por 60 con solo avanzar un número entero de palabras de 16 bits.

Para usarlo como un algoritmo no segmentado de página, como para el pseudo código aquí, es suficiente simplemente mover las comprobaciones de módulo fuera del bucle más interno sin eliminar todos los "fallos de aciertos" para el bucle medio resultante, ya que aunque todavía no son lo suficientemente eficientes en el sentido de que el bucle intermedio aún procesa "fallos de aciertos", lo que no agrega más de un uno por ciento al tiempo de ejecución; sin embargo, para implementaciones paginadas, los "aciertos perdidos" incluso en los bucles externos pueden aumentar considerablemente la sobrecarga computacional ya que estos bucles se ejecutan una vez por página en el rango de valores "x" para esa página, por lo que hay un factor de aproximadamente el logaritmo de la raíz cuadrada del rango tamizado más de los bucles externos para el SoA en comparación con el Tamiz de Eratóstenes (SoE). Una versión de pseudo código más complejo que representa una versión (opcionalmente empaquetada en bits) no segmentada de la página del método Atkin y Bernstein "optimizado para el golpe" se puede escribir de la siguiente manera:

// arbitrary search limit limit ← 1000000000 // the set of base wheel prime candidates s ∈ {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61} // Initialize the sieve as an array of wheels with // enough wheels to include the representation for limit for n ← 60 * w + x where w ∈ {0,...(limit - 7) ÷ 60}, x in s: sieve(n) ← false // start with no primes. // Put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms. while n ≤ limit when n ← 4x²+y² // all x''s and only odd y''s where x ∈ {1,...}, y ∈ {1,31,...}: // skip by pattern width in y for cb ≤ limit when midy ← y + i, cb ← n - y² + midy² where i ∈ {0,2,...28}: // middle level loop to "hit" test modulos cbd ← (cb - 7) ÷ 60, cm ← cb mod 60 if cm in {1,13,17,29,37,41,49,53}: while c ≤ limit when c ← 60 × (cbd - midy² + ((midy + 15 × j) × j)²) + cm where j {0,...}: sieve(c) ← ¬sieve(c) // toggles the affected bit while n ≤ limit when n ← 3x²+y² // only odd x''s and even y''s where x ∈ {1,3,...}, y ∈ {2,32,...}: // skip by pattern width in y for cb ≤ limit when midy ← y + i, cb ← n - y² + midy² where i ∈ {0,2,...28}: // middle level loop to "hit" test modulos cbd ← (cb - 7) ÷ 60, cm ← cb mod 60 if cm in {7,19,31,43}: while c ≤ limit when c ← 60 × (cbd - midy² + ((midy + 15 × j) × j)²) + cm where j {0,...}: sieve(c) ← ¬sieve(c) // toggles the affected bit while n ≤ limit when n ← 3x²-y² //even/odd & odd/even combos where x ∈ {2,3,...}, y ∈ {x-1,x-31,...,1}: // skip by pattern width in y for midy ≥ 1 and cb ≤ limit when midy ← y - i, cb ← n + y² - midy² where i ∈ {0,2,...28}: // middle level loop to "hit" test modulos cbd ← (cb - 7) ÷ 60, cm ← cb mod 60 if cm in {11,23,47,59}: while yn ≥ 1 and c ≤ limit when yn = midy - 30 * j and c ← 60 × (cbd + midy² - ((midy - 15 × j) × j)²) + cm where j {0,...}: sieve(c) ← ¬sieve(c) // toggles the affected bit // Eliminate prime squares by sieving, only for those occurrences on the wheel for sqr ≤ limit where sqr ← n², n in {7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59,61,...}: if is_prime(n): // n is prime, omit multiples of its square; this is // sufficient because composites which managed to get // on the list cannot be square-free if c0 ≤ limit where c0 ← sqr × (m mod 60) where m in s: c0d ← (c0 - 7) ÷ 60, cm ← (c0 - 7) mod 60 + 7 // means cm in s while c ≤ limit for c ← 60 × (c0d + sqr × j) + cm where j ∈ {0,...}: sieve(c) ← false // cull composites of this prime square output 2, 3, 5 for n ≤ limit when n ← 60 × k + x where k ∈ {0..}, x in s: if sieve(n): output n

En particular, observe cómo los bucles cuadráticos más internos son muy simples, pero aumentan en una cantidad variable que aumenta linealmente por bucle, mientras que la eliminación libre de los cuadrados primos, que utiliza un tipo de progresión de Eratóstenes, se incrementa en una cantidad fija "sqr". Estos simples bucles se ejecutarán con bastante rapidez en una CPU moderna, tomando aproximadamente 4 ciclos de reloj de CPU por bucle si el acceso a la memoria es lo suficientemente rápido como para rangos de tamices pequeños o al usar una versión de página segmentada donde las páginas encajan dentro de los cachés de CPU L2 / L1 que tienen tiempos de acceso a memoria de aproximadamente este rango.

Cuando la matriz es grande como en muchos Megabytes, es probable que el tiempo promedio de acceso a la memoria promedie algo entre 20 y más de 100 ciclos de reloj de la CPU (dependiendo de la velocidad de RAM, la eficiencia de acceso a la memoria por parte de la CPU y la eficiencia de uso) de cachés intermedios) y este será el principal factor limitante en la velocidad de ejecución en lugar de la estrechez de los bucles, aparte del número de operaciones de alternar / sacrificar que requiere el algoritmo. Estos algoritmos en particular, tanto SoA como SoE, ponen una tensión particular en la interfaz de memoria para los búferes grandes, ya que saltan a través del búfer incrementando las circunferencias de la rueda por un multiplicador a la vez y se repiten para compensaciones diferentes en lugar de manejar todo el " golpes "de la rueda en secuencia; esto se debe a mover las pruebas de "éxito" a un bucle medio,lo que ahorra las pruebas de "hit" pero, como consecuencia, tiene un "salto" de búfer más grande, con el "salto" promedio para el SoA más alto que para el SoE. Por lo tanto, una estimación del tiempo de ejecución para este algoritmo en el rango de números a mil millones es aproximadamente 60 ciclos de reloj de CPU por operación (que será menor en un factor para el SoE debido a un "salto" promedio más pequeño) multiplicado por número de operaciones de alternar / sacrificar (aproximadamente 260,000 para el Tamiz de Atkin) dividido por la velocidad de reloj de la CPU. Por lo tanto, una CPU de 3.5 GHz ejecutará este algoritmo en un rango de mil millones en aproximadamente cuatro segundos y la principal diferencia entre la velocidad de ejecución para implementaciones no paginadas de SoA y SoE en este estilo es la diferencia en la eficiencia de acceso a la memoria para grandes amortiguadoresdonde un SoE altamente factorizado en la rueda es más eficiente en aproximadamente un factor de dos.

Dado que para los búferes grandes el tiempo de acceso a la memoria es el factor limitante de la velocidad, es muy importante encontrar un algoritmo con un número mínimo de operaciones. El SoA implementado por Atkin y Bernstein en su programa de ejemplo "primegen" toma alrededor de un factor constante de operaciones de "acierto" como una proporción al rango tamizado, y al implementar incluso una versión simple de un programa desde mi primera respuesta, podemos determinar que este factor es aproximadamente 0,26 del rango principal tamizado: lo que significa que hay alrededor de 260,000 operaciones para un rango de tamiz de mil millones.

Para un SoE implementado con una factorización de rueda alta de una rueda de 210 elementos con 48 "golpes" candidatos primarios por rotación (rueda pequeña para números primos de 2; 3; 5; 7) en combinación con un pre-sacrificio por los números primos adicionales de 11 ; 13; 17; 19, el número de operaciones de sacrificio para un rango de tamiz n es aproximadamente n veces (ln ((ln n) / 2) + M - 1 / (ln n) - 1/2 - 1/3 - 1 / 5 - 1/7 - 1/11 - 1/13 - 1/17 - 1/19) * 48/210 donde ''*'' significa multiplicado por, ''/'' significa dividido por, M es la constante de Meissel-Mertens M ≈ 0.2614972128 ... corrigiendo el número de operaciones que surgen de la estimación (ln ln n), el término recíproco "ln n" es el ajuste para el sacrificio que comienza en el cuadrado de los primos base (menor que la raíz cuadrada del rango norte); para n de mil millones, el factor comparado con n es alrededor de 0.250485568 o aproximadamente 250 millones de operaciones de sacrificio para un rango de mil millones.

Esto es aproximadamente el mismo número de operaciones que para el SoA y contrasta con la rueda simple 2; 3; 5 utilizada en la prueba de comparación de Atkin y Bernstein, que tiene un factor de 0.404805008 o aproximadamente 400,000 operaciones para un rango de criba de mil millones. Esta mejor relación para el SoE más altamente factorizado significa que los factores constantes para esta implementación bastante realizable son casi los mismos que para el SoA, excepto por cualquier diferencia en los factores constantes debido a la complejidad del bucle.

EDIT_ADD1: Para comparación, el siguiente es un pseudo código equivalente para un SoE altamente factorizado y precalificado escrito en el mismo estilo que el algoritmo SoA anterior:

// arbitrary search limit limit ← 1000000000 // the set of base wheel primes r ∈ {23,29,31,37,41,43,47,53, 59,61,67,71,73,79,83, //positions + 19 89,97,101,103,107,109,113,121,127, 131,137,139,143,149,151,157,163, 167,169,173,179,181,187,191,193, 197,199,209,211,221,223,227,229} // an array of length 11 times 13 times 17 times 19 = 46189 wheels initialized // so that it doesn''t contain multiples of the large wheel primes for n where n ← 210 × w + x where w ∈ {0,...46189}, x in r: // already if (n mod cp) not equal to 0 where cp ∈ {11,13,17,19}: // no 2,3,5,7 mstr(n) ← true else mstr(n) ← false // factors // Initialize the sieve as an array of the smaller wheels with // enough wheels to include the representation for limit for n where n ← 210 × w + x, w ∈ {0,...(limit - 19) ÷ 210}, x in r: sieve(n) ← mstr(n mod (210 × 46189)) // init pre-culled primes. // Eliminate composites by sieving, only for those occurrences on the // wheel using wheel factorization version of the Sieve of Eratosthenes for n² ≤ limit when n ← 210 × k + x where k ∈ {0..}, x in r if sieve(n): // n is prime, cull its multiples s ← n² - n × (x - 23) // zero''th modulo cull start position while c0 ≤ limit when c0 ← s + n × m where m in r: c0d ← (c0 - 23) ÷ 210, cm ← (c0 - 23) mod 210 + 23 //means cm in r while c ≤ limit for c ← 210 × (c0d + n × j) + cm where j ∈ {0,...}: sieve(c) ← false // cull composites of this prime output 2, 3, 5, 7, 11, 13, 17, 19, for n ≤ limit when n ← 210 × k + x where k ∈ {0..}, x in r: if sieve(n): output n

Observe cuánto menos complejo es este código, a pesar de que está más altamente factorizado en la rueda, de modo que hay una sobrecarga de operaciones más constante que el código SoA, mientras que el bucle de selección más interno es en realidad un poco más simple y, por lo tanto, (en todo caso) un poco más rápido . Observe también la cantidad de bucles externos que se deben ejecutar para el código de SoA, ya que hay un total de aproximadamente el mismo número de bucles externos que la raíz cuadrada del rango de tamizado para el SoA donde solo hay alrededor del rango de tamiz dividido por el logaritmo natural de la raíz cuadrada de los rangos externos de ese rango para el SoE: un factor de aproximadamente diez veces menos para el SoE en comparación con el SoA para rangos de criba de mil millones. Esta es la compensación que hace el SoA: más bucles externos para menos operaciones por bucle interno con "saltos" de búfer más grandes entre operaciones;sin embargo, esto es también lo que hace que el SoA sea menos eficiente por operación, especialmente para rangos de tamices más grandes.END_EDIT_ADD1

En cuanto a la complejidad del código para rangos más grandes, estos siempre se implementan como tamices segmentados de página para evitar la necesidad de tener toda la matriz de tamices en la memoria RAM (las restricciones de memoria limitarían el rango) y para aprovechar la localidad de almacenamiento en caché de la CPU para reducir los tiempos promedio de acceso a la memoria como se discutió anteriormente. Para el SoE, esto puede implementarse fácilmente basándose en una copia guardada de una representación de primos base donde hay aproximadamente la raíz cuadrada del rango dividido por el registro de ese número de raíz cuadrada de ese rango; para el SoA, uno debe referirse a la misma representación de primos base para la eliminación libre de los cuadrados primos, pero también debe usar los valores de los desplazamientos de secuencia más los valores guardados de ''x'' o ''y'' (o guardar los valores actuales de ambos ''x ''y'' y '') para reanudar en la página siguiente el desplazamiento con un número total de secuencias guardadas como sobre la raíz cuadrada del rango (no dividido por el logaritmo natural de la raíz n), o alternativamente se pueden usar nuevas compensaciones de pares ''x'' / ''y'' calculado para el inicio de cada nueva página con una considerable sobrecarga computacional. El primer método agrega mucho a la sobrecarga de uso de la memoria, especialmente para implementaciones de subprocesos múltiples donde se debe mantener una copia para cada subproceso; el segundo no usa más memoria, pero usa más poder de cómputo en comparación con el SoE para estos rangos más grandes.Las compensaciones de pares se pueden calcular para el inicio de cada nueva página con una sobrecarga computacional considerable. El primer método agrega mucho a la sobrecarga de uso de la memoria, especialmente para implementaciones de subprocesos múltiples donde se debe mantener una copia para cada subproceso; el segundo no usa más memoria, pero usa más poder de cómputo en comparación con el SoE para estos rangos más grandes.Las compensaciones de pares se pueden calcular para el inicio de cada nueva página con una sobrecarga computacional considerable. El primer método agrega mucho a la sobrecarga de uso de la memoria, especialmente para implementaciones de subprocesos múltiples donde se debe mantener una copia para cada subproceso; el segundo no usa más memoria, pero usa más poder de cómputo en comparación con el SoE para estos rangos más grandes.

Los algoritmos segmentados por página también son importantes para aprovechar al máximo las modernas CPU de múltiples núcleos que pueden reducir el tiempo de reloj requerido para una tarea dada en la proporción del número de núcleos utilizados, especialmente para los algoritmos divididos en páginas donde se puede procesar cada página. asignado a un hilo separado.

La forma en que la implementación de SoE "primesieve" gestiona los tiempos de operación promedio de aproximadamente 2.5 ciclos de reloj de la CPU en comparación con los aproximadamente 4.5 ciclos de reloj de la CPU para la implementación de ejemplo de Atkin y Bernstein de "primegen" del SoA es mediante un alineamiento extremo del desenrollado del bucle segmentación de páginas; esta técnica también se puede aplicar al SoA, pero este pseudo código en particular no es adecuado para hacer eso y se debe usar una técnica alternativa de optimización de "tasa de aciertos" que maneje todos los módulos en un solo bucle (por bucle de ecuación cuadrática); sin embargo, ese es un algoritmo complejo que parece estar más allá del alcance de esta pregunta. Basta con decir que los saltos en la complejidad hasta el momento no son nada en comparación con lo que se requiere para agregar esta optimización adicional al SoA.e incluso con eso, la proporción de bucles externos todavía hace que el SoE sea mucho más eficiente.

Por lo tanto, si bien es bastante fácil implementar un algoritmo SoA ingenuo como en el pseudo código original de Wikipedia o incluso usar el pseudo código SoA más complejo como en estas dos respuestas, es extremadamente complejo escribir algo que compita incluso con el "primegen" de Bernstein. "(SoA) y mucho menos con el" primesieve "más rápido (SoE), mientras que es bastante fácil escribir código que se aproxime al mismo rendimiento que" primegen "y solo un poco más de trabajo escribir algo que compita con" primesieve " utilizando el algoritmo SoE con las ligeras modificaciones para admitir la segmentación de páginas.

EDIT_ADD2: Para poner esta teoría en términos prácticos, normalmente escribiría un programa de ejemplo para demostrar estos principios; sin embargo, en este caso tenemos todo lo que realmente necesitamos en el código fuente "primegen", que es la implementación de referencia por los inventores de la SoA. En mi máquina (i7-2600K, 3.5 GHz) con el tamaño del búfer ajustado a 32768 desde 8192 para reflejar el tamaño de mi caché L1, esta "velocidad primordial" filtra los números primos a mil millones en aproximadamente 0.365 segundos. De hecho, Atkin y Bernstein hicieron un poco de trampa en su comparación con su algoritmo de tamiz de Eratóstenes en el sentido de que solo le asignaron unos cuatro amortiguadores Kilobyte; ajustar ese tamaño de búfer a aproximadamente el mismo tamaño ("#define B32 1001" a "#define B32 8008") da como resultado un tiempo de ejecución de aproximadamente 0.42 segundos para "eratspeed" a aproximadamente mil millones, lo que lo deja un poco más lento. Sin embargo, como se mencionó anteriormente, está haciendo más trabajo, ya que está realizando alrededor de 0.4048 millones de operaciones de sacrificio, mientras que el SoA solo está haciendo alrededor de 0.26 mil millones de operaciones de alternar / eliminar combinadas. El uso del algoritmo del pseudocódigo SoE anterior para cambiar esto significa tener una factorización máxima de la rueda, lo que significa que el SoE en realidad haría un poco menos de operación que el SoA a aproximadamente 0.2505 mil millones, lo que significa que el tiempo de ejecución se reduciría a aproximadamente dos tercios o más alrededor de 0.265 a 0.3 segundos por lo que es más rápido que "primegen".

Mientras tanto, si se compara "primespeed" con el código de "eratspeed", se ve que el SoE paginado es mucho menos complejo que el código de SoA, tal como lo indica el pseudo código anterior.

Por supuesto, uno podría contrarrestar que el SoA mantiene la proporción de 0.26 veces el rango de cribado a un rango de cribado tan alto como se quiera, mientras que el SoE aumenta según las ecuaciones dadas anteriormente, aproximadamente un 20% extra para un rango de cribado incluso a cien mil millones. Sin embargo, dado un ligero ajuste a ambos algoritmos para aumentar el tamaño del búfer y "subdividirlo" para procesarlo en cortes de tamaño L1 de caché, el SoE funcionará según lo previsto, mientras que la sobrecarga del SoA continúa aumentando debido a la relación extra de media / bucles internos para el SoA en comparación con el SoE. Si bien el SoE tiene un aumento en las operaciones de sacrificio en aproximadamente el 20%, el SoA tiene un aumento en los bucles de procesamiento cuadráticos de aproximadamente el mismo 20% para una ganancia neta muy pequeña, si la hubiera. Si estas optimizaciones se hicieron al SoA, entonces podría solo puede alcanzar el SoE máximo factorizado en la rueda en un rango de tamizado muy grande, como diez a la decimonovena potencia, pero estamos hablando de cientos de años de procesamiento en una computadora de escritorio, incluso utilizando el multiprocesamiento.

El SoA puede ser práctico para tamizar un sub-rango (es decir, un segmento de una sola página) de un rango de desplazamiento muy grande (por ejemplo, diez aumentados a la potencia de veintidós segundos), pero aún existe ese costo de memoria adicional o cómputo al tratar con todos esos valores de ''x'' e ''y'' que no son necesarios con el SoE. END_EDIT_ADD2

Al igual que para mi primera respuesta, la comparación dice que el SoA pierde al SoE altamente factorizado en la rueda en casi todos los frentes, de la siguiente manera:

El código SoA es mucho más complejo y más difícil de escribir y mantener, por lo que es mucho más difícil implementar la segmentación de páginas que es tan importante para rangos más grandes para aprovechar las capacidades máximas de la CPU en lo que respecta a las velocidades de acceso a la memoria.
Es probable que el SoA pierda los ciclos de reloj de la CPU en al menos un 20% debido a un código de bucle interno un poco más complejo y un mayor número de bucles externos.
El SoA tiene un poco más de operaciones en comparación con un SoE altamente factorizado en la rueda (mayor factorización de la rueda que en la discusión anterior) para un rango razonablemente grande de uno a cuatro mil millones.
El SoA gana para rangos muy grandes al tener un factor de mejora de log (log n) a medida que los rangos se hacen más grandes, pero ese factor solo permitiría que el SoA alcance al SoE altamente factorizado en la rueda en un rango de números muy alto (tal vez aproximadamente 10 elevado a la decimonovena potencia) si alguna vez, y solo si la complejidad relativa permanece igual, lo que no es probable que haga.

Entonces, repito: " ¿Por qué usar el Tamiz de Atkin cuando el Tamiz de Eratóstenes es mejor en casi todos los aspectos y, especialmente, es menos complejo y tiene una sobrecarga de factor computacional constante? "Según mis conclusiones aquí, creo que el SoA es un tamiz inferior para cualquier tipo de rango de tamiz razonable y probablemente nunca escribiré una versión segmentada de la página del Tamiz de Atkin, pero he escrito muchos de ellos en varios lenguajes de computadora para el Tamiz de Eratóstenes. Si bien el Tamiz de Atkin es interesante desde el punto de vista intelectual y matemático, no es realmente práctico y la comparación de Atkin y Bernstein fue errónea al restringir excesivamente la factorización de la rueda de su implementación del Tamiz de Eratóstenes utilizada en su comparación para mostrar una ventaja aproximadamente el 30%, que en realidad debería haber sido aproximadamente el 60% excepto por los gastos generales de implementación constante del Tamiz de Atkin.