De hecho, se puede implementar un Tamiz de Atkin ilimitado (SoA) sin utilizar la segmentación en absoluto ya que he hecho here in F#. Tenga en cuenta que esta es una versión funcional pura que ni siquiera utiliza matrices para combinar las soluciones de las ecuaciones cuadráticas y el filtro libre de cuadrados y por lo tanto es considerablemente más lento que un enfoque más imperativo.
Las optimizaciones de Berstein usando tablas de búsqueda para rangos óptimos de 32 bits harían el código extremadamente complejo y no adecuado para la presentación aquí, pero sería bastante fácil adaptar mi código F # para que las secuencias comiencen en un límite inferior establecido y se usan solo en un rango para implementar una versión segmentada y/o aplicar las mismas técnicas a un enfoque más imperativo usando matrices.
Nota que la aplicación de la SOA, incluso de Berstein no es realmente más rápido que la criba de Eratóstenes con todas las optimizaciones posibles según Kim Walisch's primesieve pero sólo es más rápido que una versión equivalentemente optimizada de la criba de Eratóstenes para el rango seleccionado de números según su implementación.
EDIT_ADD: Para aquellos que no quieren que vadear a través de pseudo-código de Berstein y el código C, estoy añadiendo a esta respuesta en añadir un método de pseudo-código para utilizar la SOA en un rango de BAJO a ALTO, donde el delta de BAJO a ALTO + 1 podría estar restringido a un módulo par 60 para usar el módulo (y el potencial de empaquetado de bits solo para las entradas en la rueda 2,3,5).
Esto se basa en una posible implementación utilizando los cuadráticos SoA de (4 * x^2 + y ^), (3 * x^2 + y^2) y (3 * x^2 -y^2) para ser expresado como secuencias de números con el valor de x para cada secuencia fija a valores entre uno y SQRT ((ALTO - 1)/4), SQRT ((ALTO - 1)/3) y resolver el cuadrático para 2 * x^2 + 2 * x - ALTO - 1 = 0 para x = (SQRT (1 + 2 * (ALTO + 1)) - 1)/2, respectivamente, con las secuencias expresadas en mi código F # según el enlace superior . Las optimizaciones de las secuencias usan que cuando se criban solo compuestas impares, para las secuencias "4x", los valores y solo necesitan ser impares y que las secuencias "3x" solo necesitan usar valores impares de y cuando x es par y viceversa. La optimización adicional reduce el número de soluciones a las ecuaciones cuadráticas (= elementos en las secuencias) al observar que los patrones de módulo sobre las secuencias anteriores se repiten en rangos muy pequeños de xy también se repiten en rangos de y de solo 30, que se usa en el código Berstein pero no (todavía) implementado en mi código F #.
Tampoco incluyo las optimizaciones bien conocidas que podrían aplicarse al descarte principal "sin cuadrados" para usar la factorización de las ruedas y los cálculos para la dirección del segmento inicial como uso en my implementations of a segmented SoE.
Para calcular las direcciones de segmento de inicio de secuencia para "4x", "3x +" y "3x-" (o con "3x +" y "3x-" combinados como lo hago en el código F #), y de haber calculado los intervalos de x para cada uno como por lo anterior, la pseudo-código es el siguiente:
calcular el rango LOW - FIRST_ELEMENT, donde FIRST_ELEMENT es con el valor aplicable más bajo de y para cada valor dado de x o y = x - 1 para el caso de la secuencia "3x-".
Para la tarea de calcular cuántos elementos hay en este rango, esto se reduce a la pregunta de cuántos de (y1)^2 + (y2)^2 + (y3)^2 ... hay donde cada número y está separado por dos, para producir 'y' pares o impares según sea necesario. Como es habitual en el análisis de secuencia cuadrada, observamos que las diferencias entre cuadrados tienen un incremento constante creciente ya que en delta (9 - 1) es 8, delta (25 - 9) es 16 para un incremento de 8, delta (49 - 25) es 24 para un aumento adicional de 8, etcétera. de modo que para n elementos, el último incremento es 8 * n para este ejemplo. Al expresar la secuencia de elementos usando esto, obtenemos que es uno (o lo que uno elija como el primer elemento) más ocho veces la secuencia de algo así como (1 + 2 + 3 + ... + n). Ahora la reducción estándar de secuencias lineales se aplica donde esta suma es (n + 1) * n/2 o n^2/2 + n/2. Esto podemos resolver la cantidad de n elementos que hay en el rango al resolver la ecuación cuadrática n^2/2 + n/2 - rango = 0 o n = (SQRT (8 * rango + 1) - 1)/2.
Ahora, si FIRST_ELEMENT + 4 * (n + 1) * n no es BAJO como dirección inicial, agregue uno a n y use FIRST_ELEMENT + 4 * (n + 2) * (n + 1) como la dirección inicial. Si se utilizan optimizaciones adicionales para aplicar el descarte de factorización de rueda al patrón de secuencia, las matrices de búsqueda pueden usarse para buscar el valor más cercano de n usado que satisfaga las condiciones.
El módulo 12 o 60 del elemento de inicio se puede calcular directamente o se puede producir mediante el uso de tablas de búsqueda basadas en la naturaleza repetitiva de las secuencias de módulo.
Cada secuencia se utiliza para alternar los estados compuestos hasta el límite ALTO. Si se agrega la lógica adicional a las secuencias para saltar valores solo entre los elementos aplicables por secuencia, no es necesario un uso adicional de las condiciones del módulo.
Lo anterior se hace para cada secuencia "4x" seguida por las secuencias "3x +" y "3x-" (o combina "3x +" y "3x-" en un solo conjunto de secuencias "3x") hasta los límites x calculados anteriormente o como probados por ciclo.
Y ahí lo tienes: dado un método apropiado de dividir el rango de tamiz en segmentos, que es el más utilizado como tamaños fijos que están relacionados con los tamaños de caché de CPU para una mejor eficiencia de acceso a memoria, un método de segmentación el SoA tal como lo usa Bernstein, pero con una expresión algo más simple, ya que menciona, pero no combina, las operaciones de módulo y el empaquetado de bits.
He estudiado el tamiz Atkin/Bernstein durante años y nunca he averiguado cómo hacerlo segmentado, es decir, comenzar en un número arbitrariamente grande, con tal vez un poco de precomputación. Me interesaría ver si alguien lo hizo. – librik