[C] Crivello di eratostene

[repne scasb]

[repne scasb]

[cionci]

Originariamente inviato da repne scasb
No, e' il 32% piu' lento. Riprova sarai piu' fortunato.

Prova con 100.000.000 altrimenti devi avere un timer molto preciso per valutare i tempi.

Su Athlon 1466 io 22 secondi tu 32 secondi (100.000.000) la printf viene eseguita, ma con output disattivo.

A me su un Athlon @ 2100 Mhz risulta che il mio impiega 7 secondi e il tuo 23...senza output...e per 100.000.000... Sarà una questione di compilatore...Visual C++ in questo caso...ora provo con MinGW32...

[cionci]

Probabilmente avevo copiato una versioen sbagliata del tuo codice...
Comunque ora il mio ci mette 4 secondi per 100000000 numeri...
Mentre il tuo 9 secondi....sempre con printf commentate...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char *argv[])
{
	int max, lim, size, i, j, z;
	char *list;

	if(argc < 2)
		return 1;
	if((max = atoi(argv[1])) <= 2)
		return 1;
	
	size = (max / 2 + 1);
	if((list = (char *)calloc(sizeof(char), size)) == NULL)
		return 1;
	for(i=0; i<size; i++)
		list[i]=0;
	
	printf("2 ");

	lim = (int)sqrt(max);

	for(j=1,i=3; i<=lim; ++j,i+=2)
	{
		if(!list[j])
		{
			for(z=j+i; z<size; z+=i)
				list[z] = -1;
			printf("%d ", i);
		}
	}

	for(; i<max; i+=2, ++j)
		if(!list[j])
			printf("%d ", i);
	
	return 0;
}

[cionci]

Ho riguardato ed ho visto che la differenza principale era nella struttura del vettore (io l'ho fatto di char)...che rende il programma più veloce del 45%... Mettendo comunque int (come nel tuo) faccio due secondi meno del tuo

[repne scasb]

[cionci]

Possibile...ma quel 30% in più sono solo INC...mentre le tuo sono più pesanti perchè sono moltiplicazioni

[repne scasb]

[cionci]

Originariamente inviato da repne scasb
Se guardi con un profiler il tuo software e il mio ti renderai conto che il tuo software fa il 37.43% in piu' di operazioni complessive. Purtroppo qui il problema e' la RAM. A parita' di "consumo di RAM, nonostante il mi software faccia oltre il 30% in meno di operazioni, i risultati sono (a parita' di compilatore e di ottimizzazioni):

IO: 100.000.000 -> Athlon 1466 -> 289 ticks
TU: 100.000.000 -> Athlon 1466 -> 326 ticks

Hai preso la nuova versione del mio...vero ? Mi ero scordato di implementare la limitazione della radice quadrata...

[a2000.1]

20 istruzioni
PIV 2GHz
Fortran95
100000000 (cento milioni)

tempo di calcolo = 0.63 s

[repne scasb]

[cionci]

Ecco qua con gli int...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char *argv[])
{
	int max, lim, size, i, j, z;
	int *list;

	if(argc < 2)
		return 1;
	if((max = atoi(argv[1])) <= 2)
		return 1;
	
	size = (max / 2 + 1);
	if((list = (int *)calloc(sizeof(int), size)) == NULL)
		return 1;
	for(i=0; i<size; i++)
		list[i]=0;
	
	printf("2 ");

	lim = (int)sqrt(max);

	for(j=1,i=3; i<=lim; ++j,i+=2)
	{
		if(!list[j])
		{
			for(z=j+i; z<size; z+=i)
				list[z] = -1;
			printf("%d ", i);
		}
	}

	for(; i<max; i+=2, ++j)
		if(!list[j])
			printf("%d ", i);

Nota che non facio nemmeno una moltiplicazione

[cionci]

Originariamente inviato da a2000.1
20 istruzioni
PIV 2GHz
Fortran95
100000000 (cento milioni)

tempo di calcolo = 0.63 s

Cidice...codice...

[a2000.1]

prefettato sfizzero ®®®®®®®®®®®

[cionci]

Originariamente inviato da a2000.1
prefettato sfizzero ®®®®®®®®®®®

Allora non vale...non puoi brevettare il crivello di Eratostene...

[repne scasb]

[a2000.1]

Originariamente inviato da cionci
Allora non vale...non puoi brevettare il crivello di Eratostene...

il crivello di Eratostene no, ma quello di E...o.t...E.a...t.n...a.o...n. sì !!!

[repne scasb]

[a2000.1]

Originariamente inviato da repne scasb
Allora, "E' il QUAD PUMPED DEL PENTIUM IV SU RAM DDR CHE PAGA".
...

no è un paio d'anni sul quarter-pumped dell'assembler dell'hp45 che pagano... a distanza ... ma pagano, anche se in CHF.

[cionci]

Originariamente inviato da a2000.1
no è un paio d'anni sul quarter-pumped dell'assembler dell'hp45 che pagano... a distanza ... ma pagano, anche se in CHF.

Non mi dire che sei un esperto programmatore di HP45 Mitico...