La prueba de prueba más rápida para números pequeños

Question

Estoy jugando con el proyecto Euler en mi tiempo libre, y ha llegado al punto en el que necesito hacer algunas refacciones. Implementé Miller-Rabin, así como algunos tamices. He oído antes que los tamices son más rápidos para números pequeños, como en algunos millones. ¿Alguien tiene información sobre esto? Google no fue muy útil.

Answer 1

Sí, encontrará con la mayoría de los algoritmos que puede intercambiar espacio por tiempo. En otras palabras, al permitir el uso de más memoria, la velocidad aumenta en gran medida ^{* a}.

Yo en realidad no sé el algoritmo de Miller-Rabin, pero, a menos que sea más simple que un solo agregar y extracción de desplazamiento a la izquierda/memoria, se sopla fuera del agua por un tamiz calculada de antemano.

Lo importante aquí es precalculado. Es una buena idea, en términos de rendimiento, precalcular cosas como esta ya que es poco probable que el primer millón de primos cambie en el futuro cercano :-)

En otras palabras, crea tu colador con algo como:

unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1}; 
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x)) 

con todas las advertencias habituales sobre no pasar cosas como a++ en macros. Esto le ofrece lo mejor de ambos mundos, una búsqueda de tablas deslumbrantemente rápida para números primos "pequeños", volviendo a un método de cálculo para aquellos fuera del rango.

Obviamente, usted escribiría un programa usando uno de los otros métodos para generar esa tabla de búsqueda; realmente no desea tener que escribirlo todo a mano.

Pero, como con todas las preguntas de optimización, medida, ¡no adivine!

---

^{* a} Un caso clásico de esto fue que algunas funciones trigonométricas Una vez tuve que escribir para un sistema embebido. Esta fue una oferta de contrato competitivo y el sistema tenía un poco más de almacenamiento que CPU gruñido.

En realidad ganamos el contrato ya que nuestras cifras de referencia para las funciones hicieron estallar la competencia.

¿Por qué? Porque precalculamos los valores en una tabla de búsqueda calculada originalmente en otra máquina. Mediante el uso juicioso de la reducción (bajando los valores de entrada por debajo de 90 grados) y las propiedades trigonométricas (el hecho de que el coseno es solo un cambio de fase de seno y que los otros tres cuadrantes están relacionados con el primero), conseguimos la tabla de búsqueda 180 entradas (una por medio grado).

Las mejores soluciones son aquellas que son elegantes y :-) tortuosa

---

Por lo que vale la pena, el siguiente código C generará una tabla de este tipo para usted, todos los primos por debajo de los cuatro millones (283,000 de ellos).

#include <stdio.h> 

static unsigned char primeTbl[4000000]; 

int main (void) { 
    int i, j; 

    for (i = 0; i < sizeof(primeTbl); i++) 
     primeTbl[i] = 1; 

    primeTbl[0] = 0; 
    primeTbl[1] = 0; 
    for (i = 2; i < sizeof(primeTbl); i++) 
     if (primeTbl[i]) 
      for (j = i + i; j < sizeof(primeTbl); j += i) 
       primeTbl[j] = 0; 

    printf ("static unsigned char primeTbl[] = {"); 
    for (i = 0; i < sizeof(primeTbl); i++) { 
     if ((i % 50) == 0) { 
      printf ("\n "); 
     } 
     printf ("%d,", primeTbl[i]); 
    } 
    printf ("\n};\n"); 
    printf ("#define isPrime(x) " 
     "((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n"); 

    return 0; 
} 

Si puede subir la tabla primeTbl a dieciséis millones de entradas (16 millones), encontrará que es suficiente para mantener el recuento de primera por encima de un millón (1,031,130 los primeros números primos).

Ahora hay formas de hacerlo que requieren menos almacenamiento, como almacenar solo números impares y ajustar la macro para encargarse de eso, o usar una máscara de bits en lugar de caracteres sin signo. Prefiero la simplicidad de los algoritmos si la memoria está disponible.

Answer 2

La única manera es establecer un punto de referencia. Cuando lo haga, escríbalo y publíquelo en línea en alguna parte.

Answer 3

Como una variante en la noción de pre-cálculo, primero puede barata comprobar si el candidato número p es divisible por 2, 3, 5, 7 o 11. Si no, entonces declarar p primo si 2 p ^-1 = 1 (mod p). Esto fallará en algún momento, pero funciona hasta 100 millones porque lo probé (pre-cálculo).

En otras palabras, todas las pequeñas ish Fermat pseudo-números primos a la base 2 son divisibles por uno de 3, 5, 7, o 11.

EDIT:

Como se ha indicado correctamente por @ starblue, lo anterior simplemente está mal. Tuve un error en mi programa. Lo mejor que puedo hacer es enmendar lo anterior a:

Si el candidato p es divisible por 2, 3, 5, 7 u 11, declararlo compuesto;
Else if p es uno de {4181921, 4469471, 5256091, 9006401, 9863461}, declararlo compuesto;
Else if p aprueba la prueba de Miller-Rabin para las bases 2 y 5, y luego la declara principal;
Else lo declara compuesto.

Esto probé para enteros de menos de 10,000,000. Tal vez un par diferente de bases haría aún mejor.

Acepte mis disculpas por mis errores.

EDIT 2:

Pues bien, parece que la información que estaba buscando ya está en la página de Wikipedia para el Miller-Rabin algorithm, la sección titulada "Deterministic variants of the test".

Answer 4

Recomiendo un enfoque escalonado. Primero, asegúrate de que no haya pequeños factores primos. La división de prueba por los primeros 20 o 30 primos funciona, aunque si utiliza un enfoque inteligente, puede reducir la cantidad de divisiones necesarias mediante el uso de gcds. Este paso filtra alrededor del 90% de los compuestos.

A continuación, pruebe si el número es un primer fuerte probable (prueba de Miller-Rabin) a la base 2. Este paso elimina casi todos los compuestos restantes, pero algunos compuestos raros pueden pasar.

El último paso de prueba depende de qué tan grande quieras ir. Si está dispuesto a trabajar en un rango pequeño, haga una búsqueda binaria en una lista de 2 pseudoprimias hasta la más grande que permita. Si eso es 2^32, su lista tendrá solo 10,403 miembros, por lo que la búsqueda solo debería tomar 14 consultas.

Si desea subir a 2^64, ahora es suficiente (gracias al trabajo de Jan Feitisma) verificar si el número es un pseudoprim de BPSW. (También podría descargar la lista de 3 GB de todas las excepciones, eliminar aquellas que la división de prueba eliminaría, y escribir una búsqueda binaria basada en disco.) T. R. Nicely tiene una bonita página que explica cómo implementar esto de manera razonablemente eficiente.

Si necesita ir más arriba, implemente el método anterior y úselo como una subrutina para una prueba de estilo Pocklington. Esto estira la definición de "pequeño-ish"; si desea obtener más información sobre estos métodos, solo pregunte.