Having some fun: Probabilistic primality test


  • 0

    Recently I am reading this article: https://www.topcoder.com/community/data-science/data-science-tutorials/prime-numbers-factorization-and-euler-function/
    So I think "okay let's give a try on LeetCode".

    In all of the test, the easiest way is to perform the modulo operation 1-by-1 to see if X divides any number:

       //test if x is a prime
        bool school(unsigned x) {
            for(unsigned t = 3; t*t<=x;t+=2) if(x%t == 0)return false;
            return true;
        }
    

    and this brings me a result with 686ms.

    The first probabilistic test I tried is Fermat primality test (see https://en.wikipedia.org/wiki/Fermat_primality_test), a basic way to tell if a number "probably" a prime :

        unsigned modulo (unsigned long long a, unsigned b, unsigned m) {
            unsigned long long ret = 1;
            a %= m;
            while(b) {
                if(b&1) ret *= a, ret %= m;
                a = (a*a) %m;
                b >>= 1;
            }
            
            return ret;
        }
    #define TRIAL 20
        //test if x is 'probably' a prime
        bool fermat(unsigned x) {
            srand(x);
            for(int j=TRIAL;j;--j) if(modulo(rand() % (x-3) + 3,x-1,x) != 1)return false;
            return true;
        }
    

    and It gives me "wrong answers" or "runtime exceed", depending on how much runs I use. Quite expected because by its nature Fermat test is not really precise(see https://en.wikipedia.org/wiki/Fermat_primality_test#Flaw).

    The second one I tried is Miller–Rabin primality test (see https://en.wikipedia.org/wiki/Miller–Rabin_primality_test):

    #define TRIAL 4
        //test if x is 'probably' a prime
        bool miller(unsigned x) {
            unsigned long long y = x-1;
            while(~y&1)y>>=1;
            for(int j=TRIAL;j;--j) {
                unsigned long long a = rand() % (x-2) + 2, b = y;
                a = modulo(a,b,x);
                while(b!=x-1 && a !=1 && a != x-1) {
                    a= modulo(a,2,x);
                    b *=2;
                }
                if(a != x-1 && b %2 == 0) return false;
            }
            return true;
        }
    

    I used TRIAL runs as 4, and skipped test on multiples of 2,3,5,7, it gives a 736-ms result. Hmmm I was really surprised result... maybe the runtime complexity is consistent with their result: 'school' is O(sqrt(n)) but 'miller' is O(log(n)^2)??? Who can tell me how to compare them? :P

    Then I used the deterministic variant: the input number is bounded by a INT_MAX, and 2,7,61 is a sufficient test set instead of random number(and you don't even know when to quit):

        //test if x is 'definitely' a prime if x < 4,759,123,141
        bool miller_deterministic(unsigned x) {
            unsigned long long y = x-1;
            while(~y&1)y>>=1;
            const int arr[3] = {2,7,61};
            for(int j = 0;j<3 && arr[j] < x;++j) {
                unsigned long long a = arr[j], b = y;
                a = modulo(a,b,x);
                while(b!=x-1 && a !=1 && a != x-1) {
                    a= modulo(a,2,x);
                    b *=2;
                }
                if(a != x-1 && b %2 == 0) return false;
            }
            return true;
        }
    

    , and this version of primality test gives an result with only 540~570ms. Finally faster than the naive style by ~100ms.

    So after all these stuffs, I think "price comes with quality." If you are really in need of 100% pirmality test(like in this problem), something fast like Fermat test may not what you wanna buy, or you could spend more time to fix your poor choice.

    Deterministic miller is the fastest accurate primlaity test I have seen. though there might be faster ones.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.