Πρόβλημα σε Άσκηση (Γλώσσα Προγραμματισμού C)

[migf1]

 

 

#include <stdio.h>
#include <math.h>
#define MINNUM 1990000001
#define MAXNUM 2000000000 
int main()
{long long i,j;
int n;
int z=0;
for(i=MINNUM;i<=MAXNUM;i=i+2)
{
n=0;
int sq=sqrt(i);
for(j=3;j<=sq;j=j+2)
{if((i%j)==0)
break;
}
if(j>sq)
z=z+1;
}
printf( "Deterministic Algorithm:Found %d",z);
return 0;
}

 

Έχω καταλήξει στην τελική μορφή όπως βλέπετε και το αποτέλεσμα είναι σωστό..

 

Ποιο είναι το σωστό αποτέλεσμα; Ελπίζω το 466646 που έδωσαν και τα δικά μου τεστ στο προηγούμενο ποστ.

 

Όμως αυτό που με προβληματίζει είναι οτι το αποτέλεσμα βγαίνει σε 160 δευτερόλεπτα περίπου(δεν έχω ενσωματώσει την συνάρτηση clock() o Dev C++ μου το βγάζει) ενώ ο καθηγητής μου σε 90...

Έτσι δεν πρόκειται να βγάλεις ποτέ άκρη, γιατί δεν ξέρεις με ποιον τρόπο μετράει τον χρόνο το dev-c++. Αυτό που πρέπει να κάνεις είναι να χρησιμοποιήσεις τον ίδιο τρόπο που χρησιμοποιεί και ο καθηγητής σου (δηλαδή την συνάρτηση clock()) και μάλιστα και στο ίδιο λειτουργικό σύστημα & μηχάνημα... οι υλοποιήσεις της clock() ενδέχεται να διαφέρουν από πλατφόρμα σε πλατφόρμα, ακόμα κι αν είναι ίδια τα hardware specs... π.χ. ειδικά σε Windows, νομίζω κάποιοι compilers επιστρέφουν wall-time αντί για cpu-time).

 

Εντωμεταξύ εγώ έχω proccesor AMD FX-4130 quad-core στα 3.80 GHz και ram 4,00 GB,windows 7 64-bit και ο καθηγητής το πρόγραμμα το τρέχει σε υπολογιστές των εργαστηρίων με linux...Τι πέζει???

Βλέπε παραπάνω.

[Vkt678]

Ναι όταν λέω σωστό αποτέλεσμα εννοώ τον αριθμό 466646...Μπορεί να μου πει κανείς πως ενσωματώνω την συνάρτηση clock() στο πρόγραμμα?

[migf1]

...Μπορεί να μου πει κανείς πως ενσωματώνω την συνάρτηση clock() στο πρόγραμμα?

Φαντάσου δηλαδή να μην είχα δώσει και κώδικα στο νήμα!

[Vkt678]

Το είδα αλλά αν κατάλαβα καλά η διαδικασία είναι η εξής:

 

#include <time.h> 

clock_t tend, tstart;

ακολουθεί ο κώδικας....

tend = clock();

και μετά για να το εμφανίσω, printf() ??

Ααα άκυρο το 'πιασα!

Αφού ενσωμάτωσα και την συνάρτηση clock() με την βοήθεια του 

migf1, ακόμα απορώ γιατί το τρέχει σε τέτοιο χρόνο...

[imitheos]

Αφού ενσωμάτωσα και την συνάρτηση clock() με την βοήθεια του 

migf1, ακόμα απορώ γιατί το τρέχει σε τέτοιο χρόνο...

Γιατί έχει αθηναϊκές πινακίδες. Πόσες φορές πρέπει να πούμε ότι αυτός ο αλγόριθμος είναι αργός και πρέπει να βρεις τρόπους να γλυτώσεις υπολογισμούς ?

 

Διάβασες κανένα από τα μηνύματα ? Ο migf1 έδωσε ένα link στην Wikipedia το οποίο περιγράφει μαθηματικές ιδιότητες των πρώτων αριθμών που σου επιτρέπουν να κάνεις αυτή την απλοποίηση. Έπειτα ο migf1 σου υλοποίησε και τον αλγόριθμο σε c και το ίδιο σου έκανε και ο albNik.

 

Όσον αφορά τα 90 του δασκάλου, ο κώδικάς σου τρέχει στο μηχάνημα μου σε 113 δευτερόλεπτα, ενώ ο κώδικας των migf1/albnik τρέχει σε 74 δευτερόλεπτα οπότε ήρθαμε στην τάξη μεγέθους του δασκάλου.

 

Όλες αυτές τις μαθηματικές ιδιότητες θα έπρεπε να τις σκεφτείς εσύ αντί να στο λύσουν άλλοι.

[Vkt678]

Εντάξει ρε φίλε σιγά σιγά θα μπω στο κλίμα

[Directx]

Ναι (δεν το ήξερα).

 

EDIT:

 

Και μιας και έχουμε και τους υπόλοιπους κώδικες στο νήμα, παραθέτω και αυτόν με τον οποίον τέσταρα τις 2 ταχύτερες υλοποιήσεις (isprime = μόνο τους μονούς, isPrime = Wikipedia)...

 

Κώδικας:

 

 

/* compile with: gcc -O3 to force inlining */

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

#define MIN   1990000001L
#define MAX   2000000000L

/* -------------------------------------------------------------- */
static inline int isPrime( long int n )
{
	long int i;

	if ( n <= 3 ) {
		return n > 1;
	}
	if ( 0 == n % 2 || 0 == n % 3 ) {
		return 0;
	}

        for (i=5; i * i <= n; i+=6) {
            if ( 0 == n % i || 0 == n % (i + 2) ) {
                return 0;
            }
	}

        return 1;
}

/* -------------------------------------------------------------- */
static inline int isprime( long int num )
{
	long int i;
	long int sqroot = sqrt( num );

	if ( 2 == num ) {
		return 1;
	}
	if ( num < 2 || 0 == num % 2 ) {
		return 0;
	}

	for (i=3; i <= sqroot; i+=2) {
		if ( 0 == num % i ) {
			return 0;
		}
	}

	return 1;
}

/* -------------------------------------------------------------- */
int main( void )
{
	long int n = 0;
	long int i;
	long int min = MIN;
	clock_t tend, tstart;
	double cpu_time_used = 0.0;

	/* start timer */
	printf(
		"Counting primes in the range [%ld, %ld], please wait...",
		MIN, MAX
		);
	fflush( stdout );
	tstart = clock();

	/* start processing */
	if ( 0 == MIN % 2 ) {
		min++;
	}

	for (i=min; i < MAX; i+=2)
	{
		if ( isPrime(i) ) {  /* change this to: isprime(i) for comparison */
			n++;
		}
	}

	/* end timer */
	tend = clock();
	cpu_time_used = ((double) (tend - tstart)) / CLOCKS_PER_SEC;
	printf("\nTime elapsed: %g\n", cpu_time_used);

	printf( "total primes: %ld\n", n );

	return 0;
}

 

Έξοδος:

Counting primes in the range [1990000001, 2000000000], please wait...
Time elapsed: 88.531
total primes: 466646

 

Εγώ είπα να σπάσω το πρόβλημα σε δυο νήματα, έτσι σε Intel Core Duo 1.6GHz (Windows 7 32bit) με ένα νήμα ο χρόνος που χρειάζεται είναι περίπου 151" (2".5') ενώ με δυο νήματα πέφτει στα 79" (~1'.3") βελτίωση περίπου 50%.

 

Ακολουθεί πρόγραμμα γραμμένο σε Visual C++ 2010 (βελτιστοποιήσεις ταχύτητας ενεργές)..

 

 

 

// Prime numbers multithread (r2)
#include <stdio.h>
#include <time.h>
#include <windows.h>

#define	_MAX_WORKERS	2

typedef struct {
	long int MinNum, MaxNum, Count;
}PRIMEPARAMS;

int inline isPrime(long int n) {
	if(n <= 3)
		return n > 1;

	if(!(n % 2) || !(n % 3))
		return false;

	for(long int i = 5; i * i <= n; i += 6)
		if(!(n % i) || !(n % (i + 2)))
			return false;

	return true;
}

DWORD WINAPI ThreadSearch(LPVOID ptrIn)
{
	PRIMEPARAMS *ptrParam = (PRIMEPARAMS*)ptrIn;

	ptrParam->Count = 0;

	if(!(ptrParam->MinNum % 2))
		ptrParam->MinNum++;

	for(; ptrParam->MinNum < ptrParam->MaxNum; ptrParam->MinNum += 2)
		if(isPrime(ptrParam->MinNum))
			ptrParam->Count++;	

	return true;
}

int main(void) {

	HANDLE hWorkers[_MAX_WORKERS] = { NULL };	

	PRIMEPARAMS PrimeParam[_MAX_WORKERS] = {
			{ 1990000001, 1994999998, 0 },
			{ 1994999998, 2000000000, 0 }			
	};	

	/* Create _MAX_WORKERS threads */
	int iWorker = 0;

	for(; iWorker < _MAX_WORKERS; iWorker++)
		if(!(hWorkers[iWorker] = CreateThread(NULL, 4096, ThreadSearch,
			&PrimeParam[iWorker], CREATE_SUSPENDED, NULL))) {
			fprintf(stderr, "Cannot create Worker Thread #%d\n", iWorker);
			exit(EXIT_FAILURE);
		}

	clock_t cStart = clock(),
			cEnd;

	/* Resume threads */
	for(iWorker = 0; iWorker < _MAX_WORKERS; iWorker++)
		ResumeThread(hWorkers[iWorker]);

	/* Wait for all workers to finish */
	WaitForMultipleObjects(_MAX_WORKERS, hWorkers, true, INFINITE);

	cEnd = clock();

	/* Sum all workers results */
	long int CounterSum = 0;

	for(int iCounter = 0; iCounter < _MAX_WORKERS; iCounter++)
		CounterSum += PrimeParam[iCounter].Count;

	/* Show results */		
	printf("Primes found: %ld\nClock = %.2f\"\n", CounterSum, (double)(cEnd - cStart) / CLOCKS_PER_SEC);

	puts("Press Enter to exit..");
	getchar();

	return 0;
}

ΕΞΟΔΟΣ:

 

 

 

Primes found: 466646
Clock = 79.34"
Press Enter to exit..

Μπορεί να υπάρχουν bugs ή άλλες αβλεψίες.

 

--EDIT Στην πρώτη ανάρτηση όρισα εκ παραδρομής τους τύπους ως __int64 αντί long int.

 

 

 

Επεξ/σία 6 Νοεμβρίου 2014 από Directx

[skiourosmc]

exw paromoia askhshh alla prepei na thn kanw kai pithanotikaa me to thewrima tou fermatt ,,prepei na upologisw to ((a^p-1) mod p) gia a kai p  mexri to 2000000000 (δισ) και μου δινοντε μετασχηματισμοι ¨¨: x^(2n+1) mod m = (x(x^2n mod m)) mod m KAIII: x^2n mod m =(x^2 mod m)^n mod m ,,to provlima pou uparxei ine h uperxeilhsh,kai epeishs sto forum ths sxolhs mas lene oti den xrisimevei h "pow",,:/ kai exw skalwseiii pws tha kanw aftes tis prakseisss???

exw paromoia askhshh alla prepei na thn kanw kai pithanotikaa me to thewrima tou fermatt ,,prepei na upologisw to ((a^p-1) mod p) gia a kai p  mexri to 2000000000 (δισ) και μου δινοντε μετασχηματισμοι ¨¨: x^(2n+1) mod m = (x(x^2n mod m)) mod m KAIII: x^2n mod m =(x^2 mod m)^n mod m ,,to provlima pou uparxei ine h uperxeilhsh,kai epeishs sto forum ths sxolhs mas lene oti den xrisimevei h "pow",,:/ kai exw skalwseiii pws tha kanw aftes tis prakseisss???

akoueiiiii kaneisss????

[Kercyn]

Δοκίμασε να γράψεις το πρόβλημά σου στα Ελληνικά και με κατανοητό τρόπο και ίσως κάποιος ακούσει.