0votos

Primos en promedio en C

por josejuan hace 6 años

Ejemplo de optimización adhoc (aunque aún caben unas cuantas más, sobre todo paralelización). 3, 11, 23, 71, 191, 443, 252443, 1522691, 15982871, 25668371, 1130799671

Un sencillo problema sobre primos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// ejemplo de optimización "adhoc" para el problema 
 
// 3, 11, 23, 71, 191, 443, 252443, 1522691, 15982871, 25668371, 1130799671 
 
// costes (AMD Phenom II X6 a 2,7 Ghz): 
//      252443,    < 5 milisegundos 
//    1522691, 10 milisegundos 
//    15982871, 210 milisegundos 
//    25668371, 340 milisegundos 
//    1130799671, 16,75 segundos 
 
// por comparar, en un Atom a 1,6 Ghz 
//      252443,    < 5 milisegundos 
//    1522691, 4 milisegundos 
//    15982871, 450 milisegundos 
//    25668371, 740 milisegundos 
// (los primeros tiempos son mejores porque tiene mejor disco) 
 
 
#include <stdio.h> 
#include <math.h> 
#include <sys/stat.h> 
 
typedef unsigned int uint; 
 
// bits: 
//        0 -> a 0 si es n primo 
//        1 -> a 1 si es 3 + n = 2 p 
//        2 -> a 1 si es 11 + n = 2 p 
//        3 -> a 1 si es 23 + n = 2 p 
//        4 -> a 1 si es 71 + n = 2 p 
//        ... 
uint *N; 
 
int main(int argc, char **argv) { 
 
    if(argc != 2) { 
        fprintf(stderr, "usage: %s file.sieve\n"); 
        return 1; 
 
    int MAXNUMBER; 
    int max_prime; 
    int n_primes; 
    uint *P; 
 
    { // el tamaño del archivo de la criba nos dice el máx num 
        struct stat s; 
        stat(argv[1], &s); 
        n_primes = (int) (s.st_size / sizeof(uint)); 
 
    printf("Generando criba..."); 
    P = (uint *) malloc(sizeof(uint) * n_primes); 
 
    { // leemos criba 
        printf("\nLeyendo primos..."); 
        FILE *f = fopen(argv[1], "rb"); 
        printf("\n%i elementos leídos.\n", fread(P, sizeof(uint), n_primes, f)); 
        fclose(f); 
 
    MAXNUMBER = P[n_primes - 1]; 
    printf("MAXNUMBER = %i\n", MAXNUMBER); 
    N = (uint *) malloc(sizeof(uint) * MAXNUMBER); 
 
    { // fijamos criba 
        int i; 
        for(i = 0; i < MAXNUMBER; i++) 
            N[i] = 1; 
        for(i = 0; i < n_primes; i++) 
            N[P[i]] = 0; 
 
    int nbit = 2; // bit de máscara de promedio, bit 1, 2, 3, ... para 3, 11, 23, ... 
    int mbit = 0; // máscara previa que debe cumplir un primo que promedia con todos los del grupo 
    int n = 3; // menor primo que cumple la máscara actual 
 
    printf("Buscando números...\n"); 
    do { 
        printf("%i, ", n); 
        { // calculamos familia 
            int i, ii; 
            for(i = n + 2, ii = n + 4; ii < MAXNUMBER; i += 2, ii += 4) { 
                if((N[i] & 1) == 0 && (N[ii] & 1) == 0) 
                    N[ii] |= nbit; 
        mbit |= nbit; 
        { // buscamos siguiente que cumpla la propiedad 
            int j; 
            for(j = n + 2; j < MAXNUMBER; j += 2) 
                if(N[j] == mbit) 
                    break; 
            if(j < MAXNUMBER) { 
                nbit <<= 1; 
                n = j; 
            } else 
                break; // no más hasta MAXNUMBER 
        // AJUSTE: 
        //    dado el 3, el 1º que cumple la propiedad del promedio es el nº 7 
        //    pues (3+7)/2=5 pero se pide el 11. 
        if(n == 7) 
            n = 11; 
    } while(n < MAXNUMBER); 
 
    printf("\nFin\n"); 
 
 
/* 
    mejoras: 
 
        1. criba con saltos (ahora es +1, puede hacerse mucho más rápido) 
        2. chequeo primos promedio con saltos (ahora es +2, puede hacerse mucho más rápido) 
        3. juntar los bucles internos del doWhile en uno sólo (partido) 
        4. paralelizar el cálculo de la familia para cada nuevo 'n' 
        5. paralelizar la búsqueda del siguiente 'n' 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.