icon - Tamiz de Atkin-Explicación y ejemplo de Java
my icon java (1)
He leído acerca de Sieve of Atkin en Wikipedia, pero el wiki está limitado en este momento. Estaba buscando una explicación de Sieve of Atkin a un alto nivel y un ejemplo en Java.
Gracias.
Puede (y probablemente sepa) algunas de las ideas básicas que se dan aquí sobre los números primos, los números compuestos y los tamices, pero pueden beneficiar a otros lectores en la comprensión de la naturaleza del algoritmo. Parte de esta respuesta se acerca peligrosamente a la pertenencia en el equivalente matemático de , pero creo que parte es necesaria para establecer la conexión entre lo que hace el algoritmo y cómo lo hace.
Los tres pares ariteméticos y cuadráticos modulares en el artículo de Wikipedia sobre este tamiz se derivan de los tres pares en el documento de Atkin y Bernstein que publicaron el núcleo de este tamiz con teoremas (y sus pruebas) y muestran que colectivamente forman un tamiz de número primo. Cualquiera solo dará solo números primos, pero no dará todos los números primos. Se necesitan los tres para producir todos los números primos.
Aquí hay un programa java que implementa el algoritmo de Wikipedia. No hago afirmaciones sobre la eficiencia de la implementación, solo que es una implementación directa de Java del algoritmo del artículo de Wikipedia.
// SieveOfAtkin.java
import java.util.Arrays;
public class SieveOfAtkin {
private static int limit = 1000;
private static boolean[] sieve = new boolean[limit + 1];
private static int limitSqrt = (int)Math.sqrt((double)limit);
public static void main(String[] args) {
// there may be more efficient data structure
// arrangements than this (there are!) but
// this is the algorithm in Wikipedia
// initialize results array
Arrays.fill(sieve, false);
// the sieve works only for integers > 3, so
// set these trivially to their proper values
sieve[0] = false;
sieve[1] = false;
sieve[2] = true;
sieve[3] = true;
// loop through all possible integer values for x and y
// up to the square root of the max prime for the sieve
// we don''t need any larger values for x or y since the
// max value for x or y will be the square root of n
// in the quadratics
// the theorem showed that the quadratics will produce all
// primes that also satisfy their wheel factorizations, so
// we can produce the value of n from the quadratic first
// and then filter n through the wheel quadratic
// there may be more efficient ways to do this, but this
// is the design in the Wikipedia article
// loop through all integers for x and y for calculating
// the quadratics
for (int x = 1; x <= limitSqrt; x++) {
for (int y = 1; y <= limitSqrt; y++) {
// first quadratic using m = 12 and r in R1 = {r : 1, 5}
int n = (4 * x * x) + (y * y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
sieve[n] = !sieve[n];
}
// second quadratic using m = 12 and r in R2 = {r : 7}
n = (3 * x * x) + (y * y);
if (n <= limit && (n % 12 == 7)) {
sieve[n] = !sieve[n];
}
// third quadratic using m = 12 and r in R3 = {r : 11}
n = (3 * x * x) - (y * y);
if (x > y && n <= limit && (n % 12 == 11)) {
sieve[n] = !sieve[n];
} // end if
// note that R1 union R2 union R3 is the set R
// R = {r : 1, 5, 7, 11}
// which is all values 0 < r < 12 where r is
// a relative prime of 12
// Thus all primes become candidates
} // end for
} // end for
// remove all perfect squares since the quadratic
// wheel factorization filter removes only some of them
for (int n = 5; n <= limitSqrt; n++) {
if (sieve[n]) {
int x = n * n;
for (int i = x; i <= limit; i += x) {
sieve[i] = false;
} // end for
} // end if
} // end for
// put the results to the System.out device
// in 10x10 blocks
for (int i = 0, j = 0; i <= limit; i++) {
if (sieve[i]) {
System.out.printf("%,8d", i);
if (++j % 10 == 0) {
System.out.println();
} // end if
if (j % 100 == 0) {
System.out.println();
} // end if
} // end if
} // end for
} // end main
} // end class SieveOfAtkin
Tengo una copia del artículo original de Atkin (en coautoría con Bernstein) en el que describe los teoremas a partir de los cuales se construye el tamiz. Ese documento está disponible aquí: http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf . Es una lectura densa para no matemáticos y tiene toda la concisión típica de un artículo de la American Mathematical Society.
Lo que sigue a continuación es una explicación más profunda de cómo se deriva el algoritmo de la descripción y el documento de Atkin y Bernstein.
Atkin y Bernstein (justificadamente) asumen que sus lectores comprenden a fondo los tamices de números primos, la aritmética modular y la factorización de la rueda utilizando la aritmética modular. Desafortunadamente, la descripción y el algoritmo del artículo de Wikipedia asumen cosas similares, aunque en menor grado. Atkin y Bernstein no afirman que sus tres pares de factorizaciones de rueda y sus cuadráticas irreducibles sean los únicos que podrían usarse y dan ejemplos pasados de otros pares que podrían usarse sin más comentarios sobre cómo. Por lo tanto, los tres para los cuales Atkin y Bernstein dan teoremas y pruebas son los tres utilizados en algoritmos basados en su trabajo. Atkin y Bernstein tampoco afirman que sus tres pares sean óptimos. Son, al parecer, los más convenientes.
Los símbolos matemáticos funky realmente útiles para este tipo de discusión de manera concisa no están disponibles aquí. A los efectos de esta respuesta, utilizaré
{algún conjunto o propiedad enumerada que define uno}
para representar un conjunto
Nat0
para representar el conjunto de números naturales incluyendo cero, es decir, Nat0 = {0, 1, 2, ...},
Nat
para representar el conjunto de números naturales que no incluyen cero, es decir, Nat = {1, 2, 3, ...} y la siguiente construcción para definir un conjunto y un símbolo para un elemento de él:
{símbolo para el elemento de un conjunto: criterios que definen el conjunto en términos del símbolo}
#
para representar el conjunto de cardinalidad, es decir, el número de elementos en un conjunto
^
para representar la exponenciación, es decir, x al cuadrado escrito como x ^ 2
La aritmética modular utilizada en las factorizaciones de rueda en descripciones, teoremas y algoritmos aparece en dos formas equivalentes:
n = (k * m) + r para k en Nat0 y r en R = {r: r en Nat0 y r <m}
n mod m = r donde r en R = {r: r en Nat0 y r <m}
Aquí están las definiciones dadas en los teoremas en su artículo junto con algunas notas sobre las formas aritméticas modulares:
n siempre es primo donde # {(x, y): n = (4 * x ^ 2) + (y ^ 2), n en {n: (Nat0 * 4) + 1}, donde x e y> = 1 y n no tiene un factor cuadrado perfecto} es impar. Es decir, si y solo si hay un número impar de pares (x, y) que resuelven los n = cuadráticos = (4 * x ^ 2) + (y ^ 2) donde x e y enteros> = 1, n mod 4 = 1 y n no tiene factores cuadrados perfectos, entonces n es primo. Tenga en cuenta que la forma n mod m = r donde r está en R tiene m = 4 y R = {r: 1}.
n siempre es primo donde # {(x, y): n = (3 * x ^ 2) + (y ^ 2), n en {n: (Nat0 * 6) + 1}, donde x e y> = 1 y n no tiene un factor cuadrado perfecto} es impar. Es decir, si y solo si hay un número impar de pares (x, y) que resuelven los n = cuadráticos = (3 * x ^ 2) + (y ^ 2) donde x e y enteros> = 1, n mod 6 = 1 y n no tiene factores cuadrados perfectos, entonces n es primo. Observe aquí que la forma n mod m = r donde r está en el conjunto R tiene m = 6 y R = {r: 1}.
n siempre es primo donde # {(x, y): n = (3 * x ^ 2) - (y ^ 2), {n: (Nat0 * 12) + 11}, x> y> = 1 y n tiene ningún factor cuadrado perfecto} es impar. Es decir, si y solo si hay un número impar de pares (x, y) que resuelven los n = cuadráticos (3 * x ^ 2) - (y ^ 2) donde x, y enteros donde x> y> = 1 , n mod 12 = 11 y n no tiene factores cuadrados perfectos, entonces n es primo. Observe aquí que la forma n mod m = r donde r está en el conjunto R tiene m = 12 y R = {r: 11}.
Una propiedad de las factorizaciones de rueda que el artículo y la Wikipedia suponen que el lector conoce bien es que la aritmética modular se puede usar para elegir selectivamente solo números enteros que no tienen ciertos factores primos. En la forma
n mod m = r, r en R = {r: Nat0, r <m},
si uno elige solo elementos de R que son relativamente primos a m, entonces todos los enteros n que satisfacen la expresión serán un número primo o primos relativos a m.
m relativamente primo a n significa que no tienen un divisor entero común> 1. Los ejemplos de números primos relativamente son: 2 es relativamente primo a 3, 4 es relativamente primo a 9, 9 es relativamente primo a 14. Entender esto es esencial para entender el los residuos (residuos) utilizados en la aritmética modular y cómo son equivalentes en las distintas versiones de las explicaciones y algoritmos.
Lo siguiente ahora explicará cómo se relacionan los teoremas, algoritmos y explicaciones.
Para la primera cuadrática, n = (4 * x ^ 2) + (y ^ 2):
El teorema usa la forma:
n = (k * 4) + r donde r en R1 = {r: 1} y k en Nat0
que es lo mismo que escribir
n mod 4 = r donde r en R1 = {r: 1}
Tenga en cuenta que define n como tener que ser cualquier otro número impar en Nat0 a partir de 1, es decir, {1, 5, 9, 13, ...}.
Para los algoritmos, se pueden hacer varias elecciones para m y, con el conjunto correcto R, las propiedades mostradas por el teorema conservado. Los autores del artículo y el artículo de Wikipedia suponen que los lectores ya saben todo esto y lo reconocerán de inmediato. Para los otros valores de m utilizados en el artículo de Wikipedia y el artículo, los equivalentes son:
n mod 12 = r donde r en R1a = {r: 1, 5, 9}
n mod 60 = r donde r en R1b = {r: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57}
Ciertos elementos en los conjuntos R1a y R1b pueden eliminarse por dos razones explicadas más adelante y el teorema seguirá vigente.
Para la segunda cuadrática, n = (3 * x ^ 2) + (y ^ 2):
El teorema usa la forma:
n = (k * 6) + r donde r en R2 = {r: 1} y k en Nat0
de nuevo esto es lo mismo que
n mod 6 = r donde r en R2 = {r: 1}
Tenga en cuenta que este es cada tercer número impar en Nat0 a partir de 1, es decir, {1, 7, 13, 19, ...}
Los equivalentes en el papel y el artículo son:
n mod 12 = r donde r en R2a = {r: 1, 7}
n mod 60 = r donde r en R2b = {r: 1, 7, 13, 19, 25, 31, 37, 43, 49, 55}
Nuevamente, los valores en un conjunto R2a y R2b pueden eliminarse por dos razones que se explican más adelante y el teorema seguirá vigente.
Para la tercera cuadrática, (3 * x ^ 2) - (y ^ 2):
El teorema usa la forma:
n = k * 12 + r donde k en Nat0 y r en R3a = {r: 11}
De nuevo, esto es lo mismo que:
n mod 12 = r donde r en R3a = {r: 11}
Tenga en cuenta que este es cada sexto número impar en Nat0 a partir de 11, es decir, {11, 23, 35, 47, ...}
Equivalentes n el papel y el artículo son:
n mod 60 = r donde r en R3b = {r: 11, 23, 35, 47, 59}
Nuevamente, un valor en el conjunto R3b puede eliminarse por una razón explicada más adelante y el teorema aún se aplicará.
En los diversos algoritmos y explicaciones, para los valores de m = 12 y m = 60, los elementos de los conjuntos R se eliminan sin afectar la validez del teorema o los algoritmos. Hay dos razones por las que algunos valores de los conjuntos R pueden descartarse.
La primera razón es que cualquier valor de r en un conjunto R que no sea relativamente primo a la m con el que está emparejado solo servirá para incluir valores para n que sean enteros compuestos con uno o más factores primos de m, ninguno de los cuales Serán los números primos. Esta característica de la aritmética modular es la razón por la cual las factorizaciones de rueda se utilizan para filtrar grandes cantidades de números no primos de otras pruebas, generalmente más complejas y menos eficientes, ya sea que sean primos. En este tamiz, la prueba más compleja es si el número de soluciones a una cuadrática irreducible específica es un número impar. Eso significa que podemos descartar inmediatamente todos los valores en el conjunto R para este algoritmo que no es primo de forma repetitiva al valor de m que se utiliza con ese conjunto R.
La segunda razón es que en el papel, las factorizaciones de rueda crean conjuntos de enteros que se superponen, incluidos los primos de superposición. Si bien eran convenientes y la superposición no importaba para los teoremas, en un algoritmo es inútil si se puede evitar fácilmente. En este caso, se evita trivialmente. Además, si el conjunto de enteros de las factorizaciones de rueda se superponen, entonces un número impar de soluciones en una cuadrática más un número impar de soluciones en otra cuadrática se convertirá en un número par acumulativo de soluciones (un número impar más un número impar es SIEMPRE un número par). En muchas implementaciones, incluida la implementación de Wikipedia, esto identificará que un número primo no es primordial, ya que implementaciones como la Wikipedia detrminan la primalidad de las soluciones acumulativas para todos los cuadráticos y no segregan las soluciones de cada cuadrático. En esos casos, es imperativo que los enteros de las factorizaciones de rueda sean subconjuntos exclusivos de enteros.
Una implementación no quiere probar el mismo número en más de una cuadrática si eso no es necesario, y no lo es. Un valor para r en un conjunto R usado en los tres aspectos cuadráticos, asumiendo que se está utilizando la misma m, solo necesita estar en uno de ellos. Si está en más de uno, entonces el mismo valor para n aparecerá más de una vez y se pondrá a prueba con más de una cuadrática. Para el mismo valor de m en uso, garantizar que el mismo elemento de R no aparezca en la R durante más de una cuadrática eliminará la superposición. En el caso del artículo de Wikipedia, la superposición evitada por la factorización de la rueda evita resultados erróneos que se producirían con soluciones cuadráticas acumulativas que, en una sola cuadrática son impares, pero en dos cuadráticas, se acumulan hasta un número par.
Un algoritmo diferente podría evitar la superposición antes de calcular los aspectos cuadráticos. En las pruebas empíricas de la cuadratura y la factorización de la rueda, la factorización de la rueda donde m = 12 produce valores significativamente menores para n que la resolución de la cuadrática. El uso de factorizaciones de rueda donde m = 60 aumenta la diferencia significativamente. Si un algoritmo de solución cuadrática para valores específicos de n fuera altamente eficiente, entonces podría haber una mejora significativa utilizando solo los valores que provienen de la factorización de la rueda para probar los aspectos cuadráticos.
Aquí están las factorizaciones de la rueda después de eliminar elementos que no son relativamente primos. Para la primera cuadrática:
n mod 12 = r donde r en R1a = {1: 1, 5} (9 tiene el divisor 3 común con 12)
n mod 60 = r donde r en R1b = {r: 1, 13, 17, 29, 37, 41, 49, 53} (5, 25 y 45 tienen el divisor 5 común con 60; 9, 21, 33, 45 y 57 tienen el divisor 3 común con 60) y esta es la forma en el algoritmo en el documento de Atkin y Bernstein.
Para la segunda cuadrática:
n mod 12 = r donde r en R2a = {1, 7} (ningún elemento de R tiene un divisor común con 12}
n mod 60 = r donde r en R2b = {r: 1, 7, 13, 19, 31, 37, 43, 49} (25 y 55 tienen el divisor 5 común con 60) y esta es la forma del algoritmo en el El papel de Atkin y Bernstein.
Para la tercera cuadrática:
n mod 12 = r donde r en R3a = {r: 11} (ningún elemento de R tiene un divisor común con 12}
n mod 60 = 4 donde r en R3b = {r: 11, 23, 47, 59} (35 tiene el divisor 5 común con 60) y esta es la forma del algoritmo en el documento de Atkin y Bernstein.
Observe que algunos de los mismos elementos se muestran en los conjuntos R1a y R2a para la primera y segunda cuadráticas. Lo mismo es cierto para los conjuntos R1b y R2b. Cuando m es 12, el conjunto de elementos comunes es {1}; cuando m es 60, el conjunto de elementos comunes es {1, 13, 37, 49}. Asegurarse de que se incluya un elemento de R para una sola cuadrática crea los siguientes formularios que ahora debe reconocer en el artículo de Wikipedia.
Para la primera cuadrática:
n mod 12 = r donde r en R1a = {r: 1, 5} (no se eliminan duplicados) (esta es la forma que se muestra en el algoritmo de Wikipedia)
n mod 60 = r donde r en R1b = {r: 1, 13, 17, 29, 37, 41, 49, 53} (no se eliminan duplicados) (esta es la forma que se muestra en la explicación de Wikipedia)
Para la segunda cuadrática:
n mod 12 = r donde r en R2a = {r: 7} (elemento 1 eliminado porque ya está en R1a) (esta es la forma que se muestra en el algoritmo de Wikipedia)
n mod 60 = r donde r en R2b = {r: 7, 19, 31, 43} (elementos 1, 13, 37 y 49 eliminados porque ya están en R1b) (esta es la forma que se muestra en la explicación de Wikipedia)
Para la tercera cuadrática:
n mod 12 = r donde r en R3a = {r: 11} (sin duplicados)
n mod 60 = r donde r en R3b = {r: 11, 23, 47, 59} (sin duplicados)
Una pregunta restante podría hacerse acerca de por qué los valores de m oscilan entre 4, 6, 12 y 60. Esto tiene que ver con la cantidad de números compuestos (es decir, no primos) que uno quiere excluir de pruebas más complejas por ser primos usando el Cuadrática frente a la complejidad de la factorización de la rueda utilizada.
El valor de m utilizado puede determinar qué compuestos pueden eliminarse inmediatamente sin eliminar los números primos. Si m = 4 y R1 = {r: 1}, como en el teorema para la primera cuadrática, todos los números con factores primos de 2 se eliminan porque 1 es primo a todos los números y 4 tiene factores primos de 2. Es importante para observar que debido a que 3 no está en este conjunto R, una factorización de rueda que use m = 4 y el conjunto R1 también excluirá un gran número de números primos, tal vez la mitad de ellos.
Si m = 6 y R2 = {r: 1} como en el teorema para la segunda cuadrática, todos los números compuestos con factores primos de 2 o 3 se eliminan porque 1 es primo relativo a todos los números y 6 tiene factores primos de 2 y 3 De nuevo, con m = 6 y el conjunto R2, que no contiene 5, se excluirá una gran cantidad de números primos, tal vez la mitad de ellos.
Si m = 12 y R3 = {r: 11} como en el teorema para la tercera cuadrática, todos los números compuestos con factores primos de 2 o 3 se eliminan porque 11 es primo relativo a 12 y 12 tiene factores primos de 2 y 3. Nuevamente, con m = 12 y el conjunto R3, que no contiene 1, 5 o 7, se excluirá una gran cantidad de números primos, tal vez más de la mitad de ellos.
Una de las cosas que Atkin y Bernstein muestran informalmente en su artículo es que, aunque los factores de rueda en los teoremas excluyen individualmente los primos de sus respectivas cuadráticas, colectivamente, las tres factorizaciones de rueda permiten todos los números primos y, en el caso de las factorizaciones de rueda en La primera y segunda cuadráticas, permiten un solapamiento significativo. Aunque no eliminan la superposición en sus algoritmos donde m = 60, el artículo de Wikipedia hace donde establece m = 12 en el algoritmo del artículo y m = 60 en la explicación del artículo.
Para los cuadráticos que Atkin y Bernstein usaron en sus teoremas, debilitar las factorizaciones de la rueda que los acompañan invalidará que operarán de acuerdo con los teoremas. Sin embargo, podemos fortalecerlos de manera que solo eliminen más compuestos pero que mantengan los mismos números exactos. Para las formas donde m = 4, (4 = 2 * 2) se filtra cada entero par. Para las formas donde m = 12 (12 = 2 * 2 * 3), cada entero con factores primos de 2 o 3 se filtra. Para las formas donde m = 60 (60 = 2 * 2 * 3 * 5), cada entero con factores primos de 2, 3 o 5 se filtra. Podríamos usar filtros potenciales con m = 6 para el mismo efecto que m = 12 y m = 30 para el mismo efecto que m = 60, pero tendríamos que tener cuidado de que lo que creamos sea equivalente a los utilizados en el teoremas
Aquí hay algunas estadísticas útiles sobre la factorización de la rueda. El 50% de los enteros en Nat0 son pares y, aparte de 2, no son primos. El 33% de los enteros en Nat0 tienen 3 como factor primo y no son primos. El 20% de los enteros en Nat0 tienen 5 como factor primo y no son primos. En conjunto, el 67% de los enteros en Nat0 tienen factores primos de 2 o 3 y no son primos. En conjunto, alrededor del 75% de los enteros en Nat0 tienen factores primos de 2, 3 o 5 y no son primos. Un método simple para eliminar 1/2, 2/3 o 3/4 de los enteros en Nat0 de pruebas más complejas para ser primo es muy atractivo y es el motivo para usar la factorización de ruedas como un filtro preliminar en los tamices de números primos. También es una motivación para usar valores de m con un conjunto R acompañante que puede filtrar todos los compuestos con factores primos que representan grandes cantidades de materiales compuestos.
Como mínimo absoluto, uno querría eliminar los compuestos con un factor primordial de 2 (es decir, todos los números pares) y luego agregar 2 al final. Al menos uno querría eliminar compuestos con factores primos de 2 o 3. Preferiblemente, uno querría eliminar compuestos con factores primos de 2, 3 o 5. Más allá de eso, las estadísticas muestran rendimientos decrecientes. m = 4 con R1 logra el mínimo m = 12 con R1a, R2a y R3a logra lo menos que uno quisiera. m = 60 con R1b, R2b y R3b logran un resultado muy deseable.
Hay algunas cosas más que se deben considerar al trabajar con valores para m y para los conjuntos R. Tome nota de que las dos formas NO son equivalentes para la primera cuadrática:
n mod 12 = r donde r en R1a = {r: 1, 5}
y
n mod 6 = r donde r en R = {r: 1, 5}
porque la forma donde m = 6 no es equivalente a
n mod 4 = r donde r en R1 = {r: 1}
Tenga en cuenta que:
n mod 6 = r donde r en R = {r: 1}
es equivalente a
n mod 12 = r donde r en R = {r: 1, 7}
y la forma donde m = 6 podría usarse con la segunda cuadrática. Es, de hecho, la forma utilizada con la segunda cuadrática en el teorema. Si tuviéramos que usarlo en lugar de los ejemplos ya considerados, podríamos eliminar el elemento 1 del conjunto R para la primera cuadrática cuando su m = 12 para eliminar la superposición.
Al ajustar el algoritmo, se debe utilizar la diligencia debida para mantener las condiciones que requieren los teoremas. Al elegir valores para my conjuntos para R, uno debe asegurarse de que la forma sea equivalente a la que no introduce ningún valor nuevo para n en la cuadrática que no se produjo con la factorización de rueda en el teorema.
Para las implementaciones, las elecciones se realizan en función de las complejidades y eficiencias de las estructuras de datos, la aritmética, las capacidades del procesador (especialmente con respecto a la multiplicación y la división), la memoria caché del procesador disponible, la memoria y el tamaño de las estructuras de datos. Existen compensaciones entre los valores de my el número de residuos (residuos) en los conjuntos R que deben verificarse. Algunas de estas pueden ser razones para ver m = 60 en la explicación y m = 12 en el algoritmo. Definitivamente son las razones por las que Atkin y Bernstein usaron formas con m = 60 en los algoritmos de su artículo.
En el documento de Atkin y Bernstein, también proporcionan algoritmos para encontrar soluciones a los aspectos cuadráticos de valores específicos de n utilizando celosías. Estos algoritmos adicionales permitieron a Atkin y Bernstein crear algoritmos de tamiz que se filtraron simultáneamente en las cuadraticas y las factorizaciones de la rueda. Ninguno de los algoritmos para soluciones derivadas de celosía a los aspectos cuadráticos con las factorizaciones de rueda fue considerado en el algoritmo del artículo de Wikipedia. En el artículo de Wikipedia, se utiliza una técnica exhaustiva de valores x, y con los aspectos cuadráticos y las factorizaciones de rueda se aplican después de que los valores cuadráticos devuelvan n. Nuevamente, este es un problema de eficiencia que debe ser decidido por los implementadores.