/****************** Start NSIEVE C Source Code ************************/ /****************************************************************/ /* NSIEVE */ /* C Program Source */ /* Sieve benchmark for variable sized arrays */ /* Version 1.2, 03 Apr 1992 */ /* Al Aburto (aburto@marlin.nosc.mil) */ /* ('ala' on BIX) */ /* */ /* */ /* This Sieve of Eratosthenes program works with variable size */ /* arrays. It is a straight forward extension of the original */ /* Gilbreath version ( Gilbreath, Jim. "A High-Level Language */ /* Benchmark." BYTE, September 1981, p. 180, and also Gilbreath,*/ /* Jim and Gary. "Eratosthenes Revisited: Once More Through the */ /* Sieve." BYTE January 1983, p. 283 ). Unlike the Sieve of */ /* Gilbreath, NSIEVE uses register long variables, pointers,and */ /* large byte arrays via 'malloc()'. Maximum array size is */ /* currently set at 2.56 MBytes but this can be increased or */ /* decreased by changing the program LIMIT constant. NSIEVE */ /* provides error checking to ensure correct operation. Timer */ /* routines are provided for several different systems. NSIEVE */ /* results won't generally agree with the Gilbreath Sieve */ /* results because NSIEVE specifically uses register long */ /* variables. NSIEVE, and Sieve, are programs designed */ /* specifically to generate and printout prime numbers (positive*/ /* integers which have no other integral factor other than */ /* itself and unity, as 2,3,5,7,11, ... ). NSIEVE does not */ /* conduct the 'typical' instructions one might expect from the */ /* mythical 'typical program'. NSIEVE results can be used to */ /* gain a perspective into the relative performance of different*/ /* computer systems, but they can not be used in isolation to */ /* categorize the general performance capabilities of any */ /* computer system (no single benchmark program currently can do*/ /* this). */ /* */ /* The program uses a maximum array size of 2.56 MBytes. You can*/ /* increase or lower this value by changing the 'LIMIT' define */ /* from 9 to a higher or lower value. Some systems (IBM PC's */ /* and clones) will be unable to work beyond 'LIMIT = 3' which */ /* corresponds to an array size of only 40,000 bytes. Be careful*/ /* when specifying LIMIT > 3 for these systems as the system may*/ /* crash or hang-up. Normally NSIEVE will stop program execution*/ /* when 'malloc()' fails. */ /* */ /* The maximum array size is given by: */ /* size = 5000 * ( 2 ** LIMIT ). */ /* */ /* The array 'Number_Of_Primes[LIMIT]' is intended to hold the */ /* correct number of primes found for each array size up to */ /* LIMIT = 20, but the array is only currently defined up to */ /* LIMIT = 12. */ /* */ /* Program outputs to check for correct operation: */ /* Array Size LIMIT Primes Found Last Prime */ /* (Bytes) */ /* 8191 0 1899 16381 */ /* 10000 1 2261 19997 */ /* 20000 2 4202 39989 */ /* 40000 3 7836 79999 */ /* 80000 4 14683 160001 */ /* 160000 5 27607 319993 */ /* 320000 6 52073 639997 */ /* 640000 7 98609 1279997 */ /* 1280000 8 187133 2559989 */ /* 2560000 9 356243 5119997 */ /* 5120000 10 679460 10239989 */ /* 10240000 11 1299068 20479999 */ /* 20480000 12 2488465 40960001 */ /* 40960000 13 ------- -------- */ /****************************************************************/ /****************************************************/ /* Example Compilation: */ /* (1) UNIX Systems: */ /* cc -O -DUNIX nsieve.c -o nsieve */ /* cc -DUNIX nsieve.c -o nsieve */ /****************************************************/ #include #ifndef vax #include #endif #include /***********************************************/ #define LIMIT 9 /* You may need to change this to '3' for PC's */ /* and Clones or you can experiment with higher*/ /* values, but '12' is currently the max. */ /***********************************************/ /***********************************************/ /* You may just want to uncomment one of these */ /* to access the correct timer for your system.*/ /***********************************************/ /* #define UNIX */ /* #define UNIX_Old */ /* #define Amiga */ /* #define BORLAND_C */ /* #define MSC */ #ifdef Amiga #include #include #endif #ifdef BORLAND_C #include #include #endif #ifdef MSC #include #endif #ifndef TRUE #define TRUE 1 #define FALSE 0 #endif float nulltime,runtime,TimeArray[4]; float reftime,adjtime1,emips; float hmips,lmips,smips[21]; long L_Prime,N_Prime; /* Last Prime and Number of Primes Found */ long ErrorFlag; long Number_Of_Primes[21]; /* List of Correct Number of Primes for */ /* each sieve array size. */ long NLoops[21]; #ifdef xxxxxxxxxx void main() { long i,j,k,p; float sumtime; printf("\n Sieve of Eratosthenes (Scaled to 10 Iterations)\n"); printf(" Version 1.2, 03 April 1992\n\n"); printf(" Array Size Number Last Prime Linear"); printf(" RunTime MIPS\n"); printf(" (Bytes) of Primes Time(sec)"); printf(" (Sec)\n"); /*******************************/ /* Number of Array Size */ /* Primes Found (Bytes) */ Number_Of_Primes[0] = 1899; /* 8191 */ Number_Of_Primes[1] = 2261; /* 10000 */ Number_Of_Primes[2] = 4202; /* 20000 */ Number_Of_Primes[3] = 7836; /* 40000 */ Number_Of_Primes[4] = 14683; /* 80000 */ Number_Of_Primes[5] = 27607; /* 160000 */ Number_Of_Primes[6] = 52073; /* 320000 */ Number_Of_Primes[7] = 98609; /* 640000 */ Number_Of_Primes[8] = 187133; /* 1280000 */ Number_Of_Primes[9] = 356243; /* 2560000 */ Number_Of_Primes[10]= 679460; /* 5120000 */ Number_Of_Primes[11]= 1299068; /* 10240000 */ Number_Of_Primes[12]= 2488465; /* 20480000 */ Number_Of_Primes[13]= 0; /* 40960000 */ Number_Of_Primes[14]= 0; /* 81920000 */ Number_Of_Primes[15]= 0; /* 163840000 */ j = 8191; k = 256; p = 0; SIEVE(j,k,p); for( i=1 ; i<= 20 ; i++) { NLoops[i] = 1; } p = 8; if ( runtime > 0.125 ) p = 1; NLoops[0] = 256 * p; NLoops[1] = 256 * p; NLoops[2] = 128 * p; NLoops[3] = 64 * p; NLoops[4] = 32 * p; NLoops[5] = 16 * p; NLoops[6] = 8 * p; NLoops[7] = 4 * p; NLoops[8] = 2 * p; NLoops[9] = p; NLoops[10] = p / 2; NLoops[11] = p / 4; if ( p == 1 ) { NLoops[10] = 1; NLoops[11] = 1; } sumtime = 0.0; i = 0; j = 8191; k = NLoops[0]; SIEVE(j,k,p); sumtime = sumtime + runtime; smips[i] = emips; j = 5000; ErrorFlag = 0; for( i=1 ; i<= LIMIT ; i++) { j = 2 * j; k = NLoops[i]; SIEVE(j,k,p); smips[i] = emips; if( ErrorFlag == 0L ) { if( N_Prime != Number_Of_Primes[i] ) { printf("\n Error --- Incorrect Number of Primes for Array: %ld\n",j); printf(" Number of Primes Found is: %ld\n",N_Prime); printf(" Correct Number of Primes is: %ld\n",Number_Of_Primes[i]); ErrorFlag = 1L; } } if( ErrorFlag > 0L ) break; sumtime = sumtime + runtime * ( 8191.0 / (float)j ); } if( ErrorFlag == 2L ) { printf("\n Could Not Allocate Memory for Array Size: %ld\n",j); } sumtime = sumtime / (float)i; j = LIMIT; if( ErrorFlag == 1L) j = LIMIT - 1; hmips = 0.0; lmips = 1.0e+06; for( i=0 ; i <= j ; i++) { if( smips[i] > hmips ) hmips = smips[i]; if( smips[i] < lmips ) lmips = smips[i]; } printf("\n Relative to 10 Iterations and the 8191 Array Size:\n"); printf(" Average RunTime = %8.3f (sec)\n",sumtime); printf(" High MIPS = %8.1f\n",hmips); printf(" Low MIPS = %8.1f\n\n",lmips); } #endif main() { SIEVE(8191,1000,0); } /**************************************/ /* Sieve of Erathosthenes Program */ /**************************************/ SIEVE(m,n,p) long m,n,p; { register char *flags; register long i,prime,k,ci; register long count,size; long iter,j; char *ptr; #ifdef vax char *malloc(); int free(); #endif size = m - 1; ptr = malloc(m); ErrorFlag = 0L; N_Prime = 0L; L_Prime = 0L; if( !ptr ) { ErrorFlag = 2L; return 0; } flags = ptr; dtime(TimeArray); dtime(TimeArray); nulltime = TimeArray[1]; if ( nulltime < 0.0 ) nulltime = 0.0; j = 0; /****************/ /* Instructions */ /* *iter */ /****************/ dtime(TimeArray); for(iter=1 ; iter<=n ; iter++) { count = 0; /* 1 */ for(i=0 ; i<=size ; i++) /* 2 */ { *(flags+i) = TRUE; /* 1*size */ } /* 3*size */ /* 1 */ ci = 0; /* 1 */ for(i=0 ; i<=size ; i++) /* 1 */ { if(*(flags+i)) /* 2*size */ { /* 1*count */ count++; /* 1*count */ prime = i + i + 3; /* 3*count */ for(k = i + prime ; k<=size ; k+=prime) /* 3*count */ { ci = ci + 1; /* 1*ci */ *(flags+k)=FALSE; /* 1*ci */ } /* 3*ci */ /* 1*count */ } } /* 3*size */ /* 1 */ j = j + count; /* 1 */ } /* 4 */ dtime(TimeArray); free(ptr); runtime = (TimeArray[1] - nulltime) * 10.0 / (float)n; if ( m == 8191 ) reftime = runtime; adjtime1 = reftime * ( (float)m / 8191.0 ); emips = 9.0*(float)size+9.0*(float)count; emips = emips+5.0*(float)ci; emips = 1.0e-05*(emips/runtime); N_Prime = j / n; L_Prime = prime; if ( p != 0L ) { printf(" %9ld %8ld %8ld ",m,N_Prime,L_Prime); printf("%9.3f %9.3f %6.1f\n",adjtime1,runtime,emips); } return 0; } /*********************************************************/ /* 'dtime()' outputs the elapsed time in seconds in p[1] */ /* from the first call to 'dtime()' to the next call. */ /*********************************************************/ /******************************************************/ /* dtime function for the UNIX 'getrusage()' routine. */ /******************************************************/ #ifdef UNIX #include #include #ifdef hpux #include #define getrusage(a,b) syscall(SYS_getrusage,a,b) #endif struct rusage rusage; dtime(p) float p[]; { float q; q = p[2]; getrusage(RUSAGE_SELF,&rusage); p[2] = (float)(rusage.ru_utime.tv_sec); p[2] = p[2] + (float)(rusage.ru_utime.tv_usec) / 1.0e+06; p[1] = p[2] - q; return 0; } #endif /*****************************************************/ /* dtime function for the old UNIX 'times' routine. */ /*****************************************************/ #ifdef UNIX_Old #include #include #ifndef HZ #define HZ 60 #endif struct tms tms; dtime(p) float p[]; { float q; q = p[2]; times(&tms); p[2] = (float)(tms.tms_utime) / (float)HZ; p[1] = p[2] - q; return 0; } #endif /**********************************/ /* dtime function for the Amiga */ /**********************************/ #ifdef Amiga #define HZ 50 dtime(p) float p[]; { float q; struct tt { long days; long minutes; long ticks; } tt; q = p[2]; DateStamp(&tt); p[2] = ((float)(tt.ticks+(tt.minutes*60L*(long)HZ)))/(float)HZ; p[1] = p[2] - q; return 0; } #endif /***************************************************/ /* dtime for IBM PC/PC-AT systems with Borland C */ /***************************************************/ #ifdef BORLAND_C #include #define HZ 100 struct time now; dtime(p) float p[]; { float q,v; q = p[2]; gettime(&now); v = 60.0*(float)(now.ti_min); v = v + (float)(now.ti_sec); v = v + (float)(now.ti_hund) / (float)HZ; p[2] = v; p[1] = v - q; return 0; } #endif /*****************************************************/ /* dtime() for IBM PC/PC-AT Systems with Microsoft C */ /*****************************************************/ #ifdef MSC #include #define HZ CLK_TCK clock_t tnow; dtime(p) float p[]; { float q; q = p[2]; tnow = clock(); p[2] = (float)tnow / (float)HZ; p[1] = p[2] - q; return 0; } #endif /********************* End Of NSIEVE C Source Code *********************/