Geek Answers Handbook

The fastest primary test for small numbers

I play through the Euler project in my free time, and it comes to the point that I need to do refactoring. I implemented Miller-Rabin, as well as several screens. I heard before that sieves are actually faster for small numbers, like a few million. Does anyone have any info on this? Google did not help much.

+5
source share
4 answers

Yes, you will find with most algorithms that you can exchange space for time. In other words, allowing you to use more memory, the speed increases significantly * a .

I really do not know the Miller-Rabin algorithm, but if it is not easier than a single extraction of the left-shift / extra shift and memory, it will be removed from the water by a pre-calculated sieve.

The important thing here is pre-calculated. It's a good idea, in terms of performance, to pre-compute such things, since the first millions of primes are unlikely to change in the near future :-)

In other words, create your own sieve with something like:

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))

with all the usual warnings not to pass things like a++macros. This gives you the best of both worlds, a dazzlingly fast search for tables for "small" primes, a return to the calculation method for those who are out of range.

, , - .

, , , !

* a - , . , , CPU grunt.

, .

? , . ( 90 ) ( , ), 180 ( ).

- : -)

, C ​​, (283 000 ).

#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;
}

primeTbl (16M), , , ( 1031, 130 ).

, , , , . , .

+9

. -, , . 20 30 , , , , gcds. 90% .

, ( -) 2. , .

, . , 2- . 2 ^ 32, 10 403 , 14 .

2 ^ 64, ( Jan Feitisma), , number - BPSW. ( 3 , , , .) T. R. Nicely , , .

, Pocklington. "-"; , .

+6

, p 2, 3, 5, 7 11. , p prime if 2 p-1= 1 (mod p). - , 100 , ( ).

, F- 2 3, 5, 7 11.

:

@starblue, . . , , :

p 2, 3, 5, 7 11, ; , p {4181921, 4469471, 5256091, 9006401, 9863461}, ;
, p - 2 5, ,
Else .

10 000 000. , .

.

2:

Well, it looks like the information I got is already on the Wikipedia page for the Miller-Rabin algorithm , a section called "Deterministic test cases . "

+2
source

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

+1
source

More articles:


All Articles