¿Los números primos de Eratóstenes son más rápidos secuenciales que concurrentemente?

Actualmente estoy escribiendo un progtwig que primero genera números primos por el tamiz de Eratóstenes secuencialmente, y luego al mismo tiempo. La versión concurrente del algoritmo se supone que es más rápida que la secuencial, pero en mi caso la versión simultánea es de aprox. 10 veces más lento. Me pregunto dónde estoy poniendo el trabajo adicional en mis hilos, en comparación con el hilo principal en la solución secuencial. Aquí está mi progtwig (¡prepárate para leer un poco!):

Primes.java :

public abstract class Primes { byte[] bitArr; int maxNum; final int[] BITMASK = { 1, 2, 4, 8, 16, 32, 64 }; final int[] BITMASK2 = { 255 - 1, 255 - 2, 255 - 4, 255 - 8, 255 - 16, 255 - 32, 255 - 64 }; void setAllPrime() { for (int i = 0; i >1]) != 0; } int nextPrime(int i) { int k; if ((i%2) == 0){ k =i+1; } else { k = i+2; } while (!isPrime(k) && k < maxNum){ k+=2; } return k; } void printAllPrimes() { for (int i = 2; i <= maxNum; i++){ if (isPrime(i)){ System.out.println("Prime: " + i); } } } } 

PrimesSeq.java :

 import java.util.ArrayList; public class PrimesSeq extends Primes{ PrimesSeq(int maxNum) { this.maxNum = maxNum; bitArr = new byte[(maxNum / 14) + 1]; setAllPrime(); generatePrimesByEratosthenes(); } void generatePrimesByEratosthenes() { crossOut(1); // 1 is not a prime int curr = 3; while(curr < Math.sqrt(maxNum)){ for(int i = curr*curr; i < maxNum; i+=2*curr){ if(isPrime(i)){ // 2*curr because odd*2 = even! crossOut(i); } } curr = nextPrime(curr); } } } 

PrimesPara.java :

 import java.util.ArrayList; public class PrimesPara extends Primes { PrimeThread[] threads; int processors; int currentState = 0; //0 = Init //1 = Generate primes after thread #0 finish //2 = Factorize public PrimesPara(int maxNum){ this.maxNum = maxNum; this.processors = Runtime.getRuntime().availableProcessors(); bitArr = new byte[(maxNum / 14) + 1]; setAllPrime(); this.threads = new PrimeThread[processors*2]; generateErastothenesConcurrently(); //printAllPrimes(); } public void generateErastothenesConcurrently(){ int[] starts = generateThreadIndexes(); for(int i = 0; i < threads.length; i++){ if(i != threads.length-1){ threads[i] = new PrimeThread(starts[i], starts[i+1]-1, i); } else { threads[i] = new PrimeThread(starts[i], maxNum, i); } } //Start generating the first primes crossOut(1); Thread th = new Thread(threads[0]); th.start(); try { th.join(); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } currentState = 1; //Start generating the rest of the primes Thread[] thrs = new Thread[threads.length]; for(int i = 0; i < thrs.length; i++){ thrs[i] = new Thread(threads[i]); thrs[i].start(); } for(int i = 0; i < thrs.length; i++){ try { thrs[i].join(); } catch (InterruptedException e) { e.printStackTrace(); } } currentState = 2; } private int[] generateThreadIndexes(){ int[] indexes = new int[processors*2]; for(int i = 0; i < indexes.length; i++){ indexes[i] = (i*((maxNum/(processors*2)))); } indexes[indexes.length-1]++; return indexes; } public class PrimeThread implements Runnable { int start; int end; int thridx; public PrimeThread(int start, int end, int thridx){ this.start = start; this.end = end; this.thridx = thridx; } public void run() { switch(currentState){ case 0: generateSqrtPrimes(); break; case 1: generateMyPrimes(); break; case 2: break; } } private void generateSqrtPrimes(){ int curr = 3; while(curr < Math.sqrt(maxNum)+1){ for(int i = curr*curr; i (int)Math.sqrt(maxNum)?start:(int)Math.sqrt(maxNum); while(curr < end){ for(int i = 3; i < Math.sqrt(maxNum)+1; i = nextPrime(i)){ if((curr%i) == 0){ if(isPrime(curr)){ crossOut(curr); } } } curr = nextPrime(curr); } } } } 

Si alguien pudiera decirme dónde está el cuello de botella en el progtwig concurrente, estaría muy feliz. ¡Gracias por adelantado!

    No soy un codificador JAVA, así que me quedo con C ++. Además, esta no es una respuesta directa a su pregunta (lo siento por eso, pero no puedo depurar JAVA). Tome esto como algunos indicadores sobre qué camino tomar o verificar …

    1. Cribas de Eratóstenes

      La paralelización es posible, pero no con una ganancia de velocidad lo suficientemente grande. En su lugar, utilizo más tabs donde cada una tiene sus propias subdivisiones y cada tamaño de tabla es una multiplicación común de todos sus subdivisiones. De esta forma, necesita iniciar tablas solo una vez y luego simplemente verificarlas en O(1)

    2. Paralelización

      Después de revisar todos los tamices, usaría hilos para hacer las obvias pruebas de división para todos los divisores no utilizados.

    3. Memoize

      Si tiene una tabla activa de todos los números primos encontrados, divida solo por números primos y agregue todos los números primos nuevos encontrados.

    Estoy utilizando la búsqueda principal no paralela, que es lo suficientemente rápido para mí …

    • Puedes adaptar esto a tu código paralelo …

    [Edit1] código actualizado

     //--------------------------------------------------------------------------- int bits(DWORD p) { DWORD m=0x80000000; int b=32; for (;m;m>>=1,b--) if (p>=m) break; return b; } //--------------------------------------------------------------------------- DWORD sqrt(const DWORD &x) { DWORD m,a; m=(bits(x)>>1); if (m) m=1< >=1) { a|=m; if (a*a>x) a^=m; } return a; } //--------------------------------------------------------------------------- List primes_i32; // list of precomputed primes const int primes_map_sz=4106301; // max size of map for speedup search for primes max(LCM(used primes per bit)) (not >>1 because SOE is periodic at double LCM size and only odd values are stored 2/2=1) const int primes_map_N[8]={ 4106301,3905765,3585337,4026077,3386981,3460469,3340219,3974653 }; const int primes_map_i0=33; // first index of prime not used in mask const int primes_map_p0=137; // biggest prime used in mask BYTE primes_map[primes_map_sz]; // factors map for first i0-1 primes bool primes_i32_alloc=false; int isprime(int p) { int i,j,a,b,an,im[8]; BYTE u; an=0; if (!primes_i32.num) // init primes vars { primes_i32.allocate(1024*1024); primes_i32.add( 2); for (i=1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;i>1;iprimes_map_p0) { j=p>>1; i=j; if (i>=primes_map_N[0]) i%=primes_map_N[0]; if (!(primes_map[i]& 1)) return 0; i=j; if (i>=primes_map_N[1]) i%=primes_map_N[1]; if (!(primes_map[i]& 2)) return 0; i=j; if (i>=primes_map_N[2]) i%=primes_map_N[2]; if (!(primes_map[i]& 4)) return 0; i=j; if (i>=primes_map_N[3]) i%=primes_map_N[3]; if (!(primes_map[i]& 8)) return 0; i=j; if (i>=primes_map_N[4]) i%=primes_map_N[4]; if (!(primes_map[i]& 16)) return 0; i=j; if (i>=primes_map_N[5]) i%=primes_map_N[5]; if (!(primes_map[i]& 32)) return 0; i=j; if (i>=primes_map_N[6]) i%=primes_map_N[6]; if (!(primes_map[i]& 64)) return 0; i=j; if (i>=primes_map_N[7]) i%=primes_map_N[7]; if (!(primes_map[i]&128)) return 0; } } an=primes_i32[primes_i32.num-1]; if (an>=p) { // linear table search if (p<127) // 31st prime { if (an>=p) for (i=0;i p) return 0; } } // approximation table search else{ for (j=1,i=primes_i32.num-1;j>=1; if (!j) j=1; for (i=0;j;j>>=1) { i|=j; if (i>=primes_i32.num) { i-=j; continue; } a=primes_i32[i]; if (a==p) return 1; if (a> p) i-=j; } return 0; } } a=an; a+=2; for (j=a>>1,i=0;i<8;i++) im[i]=j%primes_map_N[i]; an=(1< <((bits(p)>>1)+1))-1; if (an< =0) an=1; an=an+an; for (;a<=p;a+=2) { for (j=1,i=0;i<8;i++,j<<=1) // check if map is set if (!(primes_map[im[i]]&j)) { j=-1; break; } // if not dont bother with division for (i=0;i<8;i++) { im[i]++; if (im[i]>=primes_map_N[i]) im[i]-=primes_map_N[i]; } if (j<0) continue; for (i=primes_map_i0;ian) break; if ((a%b)==0) { i=-1; break; } } if (i<0) continue; primes_i32.add(a); if (a==p) return 1; if (a> p) return 0; } return 0; } //--------------------------------------------------------------------------- void getprimes(int p) // compute and allocate primes up to p { if (!primes_i32.num) isprime(3); int p0=primes_i32[primes_i32.num-1]; // biggest prime computed yet if (p>p0+10000) // if too big difference use sieves to fast precompute { // T((0.3516+0.5756*log10(n))*n) -> O(n.log(n)) // sieves N/16 bytes p=100 000 000 t=1903.031 ms // ------------------------------ // 0 1 2 3 4 5 6 7 bit // ------------------------------ // 1 3 5 7 9 11 13 15 +-> +2 // 17 19 21 23 25 27 29 31 | // 33 35 37 39 41 43 45 47 V +16 // ------------------------------ int N=(p|15),M=(N>>4); // store only odd values 1,3,5,7,... each bit ... char *m=new char[M+1]; // m[i] -> is 1+i+i prime? (factors map) int i,j,k,n; // init sieves m[0]=254; for (i=1;i< =M;i++) m[i]=255; for(n=sqrt(p),i=1;i<=n;) { int a=m[i>>4]; if (int(a& 1)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a& 2)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a& 4)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a& 8)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a& 16)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a& 32)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a& 64)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; if (int(a&128)!=0) for(k=i+i,j=i+k;j< =N;j+=k) m[j>>4]&=255-(1< <((j>>1)&7)); i+=2; } // compute primes i=p0&0xFFFFFFF1; k=m[i>>4]; // start after last found prime in list if ((int(k& 1)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k& 2)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k& 4)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k& 8)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k& 16)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k& 32)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k& 64)!=0)&&(i>p0)) primes_i32.add(i); i+=2; if ((int(k&128)!=0)&&(i>p0)) primes_i32.add(i); i+=2; for(j=i>>4;j 
    • resolvió algunos errores de desbordamiento en el código de la mina (periodicidad de tamices ...)
    • también algunas optimizaciones adicionales
    • función getprimes(p) agregada que agrega todos los primes< =p a la lista tan rápido como sea posible si aún no están allí
    • prueba de corrección en los primeros 1 000 000 imprimaciones (hasta 15 485 863)
    • getprimes(15 485 863) resuelve en 175.563 ms en la configuración de la mina
    • isprime es mucho más lento para esto de grueso

    • primes_i32 es una lista dinámica de int s

    • primes_i32.num es el número de int s en la lista
    • primes_i32[i] es i -th int i = <0,primes_i32.num-1>
    • primes_i32.add(x) agrega x al final de la lista
    • primes_i32.allocate(N) preasigna espacio para N elementos en la lista para evitar ralentizaciones de reasignación

    [notas]

    He usado esta versión no paralela para el problema 10 de Euler (sum de todos los primos por debajo de 2000000)

      ---------------------------------------------------------------------------------- Time ID Reference | My solution | Note ---------------------------------------------------------------------------------- [ 35.639 ms] Problem010. 142913828922 | 142913828922 | 64_bit 
    • Las tabs del tamiz son cada una de ellas como una porción pequeña en la matriz primes_map[] y solo se usan los valores impares (no es necesario recordar incluso las cribas).
    • si quieres maximizar la velocidad para todos los números primos encontrados, simplemente llama a isprime(max value) y lee los contenidos de primes_i32[]
    • Uso la mitad del tamaño del bit en lugar de sqrt para la velocidad

    Espero no haberme olvidado de copiar algo aquí