[C++] Optimized prime number method

[Nytro]

[C++] Optimized prime number method

#include <cmath>

bool prime(unsigned n)
{
        switch (n)
        {
                case 0:
                case 1:
                        return false;
                case 2:
                case 3:
                        return true;
                default:
                        break;
        }

        double dSq = sqrt((double)n);
        unsigned sqrt = (int)dSq;

        unsigned prime;
        // check 2 to sqrt for divisibility
        __asm
        {
                mov esi, n    
                mov edi, sqrt

                mov ebx, 1  
                mov ecx, 1   
                _loop:
                inc ecx       
                cmp ecx, edi   
                ja _end       
                mov eax, esi
                xor edx, edx
                div ecx
                cmp edx, 0 
                jne _loop
                mov ebx, 0

                _end:
                mov prime, ebx
        }
        return (prime == 1);
}

Sursa: Optimized prime num method - r00tsecurity

[rockybyt]

Freakin' fast

Pentru un for(i=0;i<100000;i++) in care determin daca i este prim dureaza 15 milisecunde.

100000 de elemente + parcurgere for in 15 ms = fast

[Xander]

ia incearca sa ii dai 100.000 de numere prime peste 1000 sa vedem daca mai merge asa repede (merge repede pe numere non-prime)

FYI: compilatoarele mai noi

pentru cod de genul celui de mai sus optimizeaza direct pe registrii...(nu mai folosesc memoria) si rezultatul final este acelasi (depinde totusi de compilator)

alta varianta cand ai de testat foarte multe numere prime pana in 10k este sa faci ciurul lui eratostene(aflii toate nr prime pana la 10k) si pur si simplu faci o cautare binara dupa... pentru peste 10k numere sub 10k incepe sa devina mult mai buna varianta cu ciurul (log(n) cautarea vs (n-sqrt(n))

inca o chestie buna de retinut:

daca un numar nu se imparte la 2 atunci nu se imparte la nici un numar par adica poti sa renunti la jumatate din munca daca verifici din 2 in 2 (3,5,7...)

bool prime(unsigned n)
{
        switch (n)
        {
                case 0:
                case 1:
                        return false;
                case 2:
                case 3:
                        return true;
                default:
                        break;
        }
		if(!(n%2)) return 0;
        double dSq = sqrt((double)n);
        unsigned sqrt = (int)dSq;

        unsigned prime;
        // check 2 to sqrt for divisibility
        __asm
        {
                mov esi, n				; bag val lui n in esi    
                mov edi, sqrt			; bag val lui sqrt(n) in edi

                mov ebx, 1				; bag 1 in ebx
                mov ecx, 1				; bag 1 in ecx 
                _loop:					; while
                add ecx, 2				; cresc ecx cu 2 (ecx+=2)
                cmp ecx, edi			; compar ecx cu edi ( cu sqrt(n) )
                ja _end					; daca ecx > edi sar la _end
                mov eax, esi			; copiez pe esi in eax
                xor edx, edx			; xor edx,edx este cea mai rapida metoda de a atribui lui edx val 0 (1 ciclu de procesor doar)
                div ecx					; impart pe eax (n) la ecx ( numarul curent )
                cmp edx, 0				; compar restul lui n/ecx cu 0
                jne _loop				; daca sunt diferite continui while-ul
                mov ebx, 0				; daca restul n/ecx = 0 atunci nr nu este prim si pun 0 in ebx

                _end:
                mov prime, ebx			; copez rezultatul in prime;
        }
        return (prime == 1);
}

optimizat sa caute doar din 2 in 2

Edited January 29, 2011 by Xander

[rockybyt]

Tot in jurul a 14 milisecunde ne invartim si cu optimizarea aia. Posibil la un numar mai mare de numere sa devina simtitoare imbunatatirea.

Cat despre calculul numerelor prime peste 1000... chiar nici o diferenta. Rulat de cateva ori pt valori tot mai mari, aici nu am vazut rezultate afectate de performanta algoritmului.

[nightkhaos]

[C++] Optimized prime number method

#include <cmath>

bool prime(unsigned n)
{
        switch (n)
        {
                case 0:
                case 1:
                        return false;
                case 2:
                case 3:
                        return true;
                default:
                        break;
        }

        double dSq = sqrt((double)n);
        unsigned sqrt = (int)dSq;

        unsigned prime;
        // check 2 to sqrt for divisibility
        __asm
        {
                mov esi, n    
                mov edi, sqrt

                mov ebx, 1  
                mov ecx, 1   
                _loop:
                inc ecx       
                cmp ecx, edi   
                ja _end       
                mov eax, esi
                xor edx, edx
                div ecx
                cmp edx, 0 
                jne _loop
                mov ebx, 0

                _end:
                mov prime, ebx
        }
        return (prime == 1);
}

Sursa: Optimized prime num method - r00tsecurity

nu te ajuta cu nimic algoritmul asta, imagineaza-ti ca trebuie sa generezi o pereche de chei RSA pe 4Mb un algoritm foarte eficient care foloseste criteriile de divizibilitate ale numerelor se afla in libraria NTL (exemplu un nr care e divizibil cu 3 are suma cifrelor divizibila cu 3, un nr care e divizibil cu 5 are ultima cifra 0 sau 5 si lista continua) pentru cei interesati de librarie

NTL: A Library for doing Number Theory

[rockybyt]

Depinde la ce folosesti algoritmul.