Najszybszy test podstawowy dla małych liczb

Question

W wolnym czasie gram projekt Euler, a doszło do tego, że muszę dokonać refaktoryzacji. Zaimplementowałem Millera-Rabina, a także kilka sit. Słyszałem wcześniej, że sita są rzeczywiście szybsze dla małych liczb, tak jak w przypadku kilku milionów. Czy ktokolwiek ma jakieś informacje na ten temat? Google nie był bardzo pomocny.

Answer 1

Tak, dzięki większości algorytmów można wymieniać miejsce na czas. Innymi słowy, pozwalając na użycie większej ilości pamięci, prędkość jest znacznie zwiększona ^{* a}.

W rzeczywistości nie mam wiem, że algorytmu Miller-Rabin, ale, o ile nie jest prostsze niż pojedyncze przesunięcie w lewo/dodać i ekstrakcji pamięci, będzie wydmuchiwane z wody przez wstępnie obliczone sito.

Ważna rzecz tutaj jest wstępnie obliczona. Dobrym pomysłem pod względem wydajności jest wstępne obliczenie takich rzeczy, ponieważ pierwszy milion liczb pierwszych będzie mało prawdopodobny do zmiany w najbliższej przyszłości :-)

Innymi słowy, utwórz swoje sito z czymś takim jak:

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

ze wszystkimi zwykłymi zastrzeżeniami dotyczącymi nieprzekazywania takich rzeczy, jak a++ do makr. Daje to to, co najlepsze z obu światów, oślepiająco szybkie wyszukiwanie tabel dla "małych liczb", powracając do metody obliczania dla osób spoza zakresu.

Oczywiście można napisać program, korzystając z jednej z innych metod generowania tabeli odnośników - tak naprawdę nie trzeba wpisywać wszystkiego ręcznie.

Ale, tak jak w przypadku wszystkich pytań dotyczących optymalizacji, miara , nie zgaduj!

---

^{* a} Klasyczny przypadek to było pewne funkcje trygonometrycznych Miałem kiedyś pisać dla wbudowanego systemu. Była to konkurencyjna oferta przetargowa, a system miał nieco więcej miejsca na dane niż procesor CPU.

Faktycznie wygraliśmy kontrakt, ponieważ nasze dane porównawcze dotyczące funkcji zdmuchnęły konkurencję.

Dlaczego? Ponieważ wstępnie obliczyliśmy wartości w tabeli odnośników obliczonej pierwotnie na innej maszynie. Przez rozsądne użycie redukcji (obniżenie wartości wejściowych poniżej 90 stopni) i właściwości trygonometrycznych (fakt, że cosinus jest tylko przesunięciem fazowym sinusa i że pozostałe trzy kwadranty są powiązane z pierwszym), dostaliśmy tabelę odnośników do 180 wpisów (jeden na pół stopnia).

najlepszych rozwiązań są te, które są eleganckie i przebiegły :-)

---

Na co warto, następujący kod C wygeneruje taką tabelę dla Ciebie, wszystkie liczby pierwsze poniżej czterech milionów (283 000 z nich).

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

Jeśli można podbić tabelę primeTbl do szesnastu milionów wpisów (16M), przekonasz się, że to wystarczy, aby utrzymać doskonałą liczyć ponad milion (pierwszy 1,031,130 liczb pierwszych).

Teraz są sposoby na zmniejszenie pobranych danych, na przykład zapisywanie liczb nieparzystych i dostosowywanie makra, aby się tym zająć, lub używanie maski bitowej zamiast znaków niepodpisanych. Wolę prostotę algorytmów, jeśli pamięć jest dostępna.

Answer 2

Jedynym sposobem jest porównanie siebie. Kiedy to zrobisz, zapisz to i umieść gdzieś online.

Answer 3

Jako wariant pojęcia wstępne obliczenia, można najpierw sprawdzić, czy tanio Numer kandydat p jest podzielna przez 2, 3, 5, 7 lub 11. Jeśli nie, to zadeklarować p prime jeśli 2 ^{p -1} = 1 (mod p). W pewnym momencie to się nie powiedzie, ale działa do 100 milionów, ponieważ testowałem to (wstępne obliczenia).

Innymi słowy, wszystkie małe ish Fermat pseudo-bodźce do podstawy 2, które dzielą jeden z 3, 5, 7 lub 11.

Edycja:

Jak prawidłowo zauważył @ starblue, powyższe jest po prostu błędne. Miałem błąd w moim programie. Najlepsze co mogę zrobić, to zmienić powyższe na:

Jeśli kandydat p jest podzielny przez 2, 3, 5, 7 lub 11, zadeklaruj, że jest złożony;
Inaczej, jeśli p jest jednym z {4181921, 4469471, 5256091, 9006401, 9863461}, zadeklaruj, że jest złożony;
Inaczej, jeśli p przejdzie test Millera-Rabina dla zasad 2 i 5, a następnie zadeklaruj go jako główny;
Inna zadeklaruj, że jest złożona.

To testowałem dla liczb całkowitych mniejszych niż 10 000 000. Być może inna para zasad zrobi jeszcze lepiej.

Proszę przyjąć moje przeprosiny za moje błędy.

EDIT 2:

Cóż, wydaje się, że informacje, byłem po jest już na stronie Wikipedia dla Miller-Rabin algorithm, w części zatytułowanej "Deterministic variants of the test".

Answer 4

Polecam podejście wielopoziomowe. Po pierwsze, upewnij się, że nie ma małych czynników głównych. Podział próbny przez pierwsze 20 lub 30 liczb pierwszych działa, ale jeśli zastosujesz sprytne podejście, możesz zmniejszyć liczbę wymaganych działów za pomocą gcd. Ten krok filtruje około 90% kompozytów.

Następnie sprawdź, czy liczba jest silnie prawdopodobnym poziomem podstawowym (test Millera-Rabina) do poziomu 2. Ten krok usuwa prawie wszystkie pozostałe kompozyty, ale niektóre rzadkie kompozyty mogą przejść.

Ostateczny etap sprawdzania zależy od tego, jak duże ma być przejście. Jeśli chcesz pracować w niewielkim zakresie, zrób binarne wyszukiwanie na liście 2-pseudoprzekimów do największego dozwolonego. Jeśli to 2^32, twoja lista będzie miała tylko 10,403 członków, więc wyszukiwanie powinno zająć tylko 14 zapytań.

Jeśli chcesz przejść do 2^64, teraz wystarczy (dzięki pracy Jan Feitisma) sprawdzić, czy numer jest pseudoprzyciem BPSW. (Można również pobrać listę wyjątków 3 GB, usunąć te, które usunął podział próbny, i napisać opartą na dysku wyszukiwarkę binarną.) T. R. Nicely ma ładną stronę wyjaśniającą, jak wdrożyć to w rozsądnie efektywny sposób.

Jeśli potrzebujesz podnieść wyżej, zastosuj powyższą metodę i użyj jej jako podprogramu do testu w stylu Pocklington. Rozciąga to definicję "małego"; jeśli chcesz uzyskać więcej informacji na temat tych metod, po prostu zapytaj.