Más rápido de prueba de acondicionamiento para los números de pequeña ish

Question

Estoy jugando a través del proyecto Euler en mi tiempo libre, y que ha llegado al punto en el que tengo que hacer algunos refactorización. He implementado Miller-Rabin, así como unos tamices. He oído antes de que los tamices son realmente más rápido para los números pequeños-ish, ya que en menos de unos pocos millones. ¿Alguien tiene alguna información sobre esto? Google no era muy útil.

Answer 1

Sí, se encuentra con la mayoría de los algoritmos que se puede comerciar espacio de tiempo. En otras palabras, al permitir el uso de más memoria, la velocidad se aumenta grandemente ^{* a} .

Yo en realidad no saber el algoritmo de Miller-Rabin, pero, a menos que sea más simple que un solo turno-izquierda / añadir y extracción de memoria, se sopla fuera del agua por un pre- tamiz calculado.

Lo importante aquí es calculada de antemano. Es una idea buena, en términos de rendimiento, comprobar la validez de calcular cosas como esta desde el primer millón de números primos será poco probable que cambie en un futuro próximo: -)

En otras palabras, crear su tamiz 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 acerca de no pasar cosas como a++ en macros. Esto le da lo mejor de ambos mundos, una búsqueda en la tabla de números primos tan rápidos "pequeño-ish", dejando caer de nuevo a un método de cálculo para los que están fuera del rango.

Es obvio que iba a escribir un programa usando uno de los otros métodos para generar esa tabla de búsqueda -. Que realmente no quiere tener que escribir todo en la mano

Sin embargo, como con todas las preguntas de optimización, medida, no adivine!

---

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

En realidad ganó el contrato ya que nuestras cifras de referencia para las funciones volaron la competencia de distancia.

¿Por qué? Debido a que nos pre-calculado los valores en una tabla de búsqueda calculada originalmente en otra máquina. Mediante el uso juicioso de reducción (con lo que los valores de entrada por debajo de 90 grados) y trig propiedades (el hecho de que el coseno es sólo un cambio de fase de seno y que los otros tres cuadrantes están relacionados con la primera), tenemos la tabla de consulta hasta 180 entradas (una por medio grado).

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

---

Por lo que vale, el siguiente código C generará una tabla de este tipo para usted, todos los números primos menores de cuatro millones de dólares (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 se puede topar encima de la mesa 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 bien, hay maneras de hacer que tienen menos capacidad de almacenamiento como única almacenar números impares y el ajuste de la macro para hacerse cargo de eso, o el uso de una máscara de bits en lugar de caracteres sin signo. Yo prefiero la sencillez de los algoritmos de mí mismo si la memoria está disponible.

Answer 2

Me recomiendan un enfoque por niveles. En primer lugar, asegúrese de que no hay factores primos pequeños. Ensayo dividiendo por las obras primeros 20 o 30 números primos, aunque si se utiliza un enfoque inteligente puede reducir el número de divisiones necesarias mediante el uso de GCDS. Este paso filtra aproximadamente el 90% de los materiales compuestos.

A continuación, la prueba si el número es un número primo fuerte probable (prueba de Miller-Rabin) a base 2. Esta etapa elimina casi todos los materiales compuestos restantes, pero algunos materiales compuestos raros puede pasar.

El paso de prueba final depende de lo grande que desea ir. Si usted está dispuesto a trabajar en un pequeño rango, hacer una búsqueda binaria en una lista de 2-pseudoprimes hasta el más grande del permites. Si eso es 2 ^ 32, la lista tendrá sólo 10.403 miembros, por lo que la búsqueda debe tener sólo 14 consultas.

Si quieres ir hasta 2 ^ 64, ahora es suficiente (gracias al trabajo de ene Feitisma) para comprobar si el número es un pseudoprime BPSW. (También puede descargar la lista de 3 GB de todas las excepciones, eliminar aquellas que eliminaría sala de primera instancia, y escribir una búsqueda binaria basada en disco.) T. R. Bien tiene una buena página que explica cómo implementar esta razonablemente eficiente.

Si tiene que ir más alto, poner en práctica el método anterior y usarlo como una subrutina para una prueba de estilo Pocklington. Esto estira la definición de "pequeña-ish"; si desea obtener más información sobre estos métodos, sólo pregunte.

Answer 3

As a variant on the notion of pre-computation, you can first cheaply check whether the candidate number p is divisible by 2, 3, 5, 7, or 11. If not, then declare p prime if 2^p-1 = 1 (mod p). This will fail at some point, but it works up to 100 million because I tested it (pre-computation).

In other words, all the small-ish Fermat pseudo-primes to the base 2 are divisible by one of 3, 5, 7, or 11.

EDIT:

As correctly noted by @starblue, the above is simply wrong. I had a bug in my program. The best I can do is amend the above to:

If candidate p is divisible by 2, 3, 5, 7, or 11, declare it composite;
Else if p is one of {4181921, 4469471, 5256091, 9006401, 9863461}, declare it composite;
Else if p passes the Miller-Rabin test for bases 2 and 5 then declare it prime;
Else declare it composite.

This I tested for integers less than 10,000,000. Perhaps a different pair of bases would do even better.

Please accept my apologies for my mistakes.

EDIT 2:

Well, it appears that the information I was after is already on the Wikipedia page for the Miller-Rabin algorithm, the section titled "Deterministic variants of the test".

Answer 4

The only way is to benchmark yourself. When you do, write it up, and post it online somewhere.