Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!rutgers!ucsd!nosc!marlin!aburto From: aburto@marlin.NOSC.MIL (Alfred A. Aburto) Newsgroups: comp.arch Subject: NSIEVE C Source File (long) Message-ID: <1073@marlin.NOSC.MIL> Date: 23 Aug 88 20:50:48 GMT References: <1070@marlin.NOSC.MIL> Reply-To: aburto@marlin.nosc.mil.UUCP (Alfred A. Aburto) Distribution: comp.arch Organization: Naval Ocean Systems Center, San Diego Lines: 328 /****************** Start NSIEVE C Source Code *************************/ /****************************************************************/ /* NSIEVE */ /* C Program Source */ /* Sieve benchmark for variable sized arrays */ /* Al Aburto */ /* 22 Aug 88 */ /* aburto@marlin.nosc.mil.UUCP */ /* 'ala' on BIX */ /* */ /* The program uses the VAX and SUN UNIX C 'times()' routine to */ /* determine the elapsed run time in seconds. The compiler */ /* option 'UNIX' must be defined for proper operation on VAX or */ /* SUN UNIX systems. Also 'HZ' must be defined. HZ will be 60 */ /* for most systems and this is the default set in the program. */ /* Please check the system 'times()' definition so that HZ is */ /* properly defined for the right measure of time. HZ may need */ /* to be set to 50 or 100 on some systems. */ /* */ /* A timing routine for the Amiga is also included. The compiler*/ /* option 'Amiga' must be defined ('-DAmiga') for proper timing */ /* on Amiga systems. HZ is defined as 50 with the routines */ /* used on this system. */ /* */ /* A timing routine for the IBM PC/PC-AT type systems with */ /* TURBO C is also included. The Turbo C compiler option */ /* '-DTURBO_C' must be defined for this timing routine to work. */ /* HZ is defined as 100 for this system. */ /* */ /* The program uses a maximum array size of 320,000 bytes. You */ /* can increase or lower this value by changing the 'limit' */ /* define from 6 to a higher or lower value. Some systems may */ /* be unable to work beyond 'limit = 4' which corresponds to an */ /* array size of 40,000 bytes. The '#define limit 6' in the */ /* program below corresponds to a max SIEVE array size of */ /* 320,000 bytes. */ /* The maximum array size is given by: */ /* size = 5000 * ( 2 ** limit ). */ /* */ /* The program uses register variables. Some compilers may not */ /* accept this option. If this is the case then 'register' */ /* will need to be removed from the SIEVE() subroutine. */ /* */ /* In re-running the program I am getting about a 5% variation */ /* in the 'Average BenchTime' output. */ /* */ /* Program outputs to check for proper operation: */ /* Array Size Primes Found Last Prime */ /* (Bytes) */ /* 8191 1899 16381 */ /* 10000 2261 19997 */ /* 20000 4202 39989 */ /* 40000 7836 79999 */ /* 80000 14683 160001 */ /* 160000 27607 319993 */ /* 320000 52073 639997 */ /****************************************************************/ /****************************************************/ /* Example Compilation: */ /* (1) VAX and SUN UNIX C: */ /* cc -O -DUNIX nsieve.c -o nsieve */ /* cc -DUNIX nsieve.c -o nsieve */ /* */ /* (2) Turbo-Amiga (68020): */ /* cc +2 +L +ff -DAmiga nsieve.c */ /* ln nsieve.o -lm32 -lc32 */ /* */ /* (3) Amiga: */ /* cc +L +ff -DAmiga nsieve.c */ /* ln nsieve.o -lm32 -lc32 */ /* */ /* (4) IBM PC/PC-AT types with TURBO C */ /* Compile with '-DTURBO_C' or uncomment the */ /* the 'TURBO_C' define in the main program. */ /* Use 'huge' data option. Compile for 'speed'. */ /****************************************************/ /************************************************************************/ /* Some Results: */ /* Array Size ------------------ BenchTime (sec) -------------------- */ /* (Bytes) SUN 3/280 VAX 8600 Turbo-Amiga */ /* 68020 @25 MHz 68020 @ 14.32 MHz */ /* ( cc -O ) ( cc -O ) ( cc +2 +L +ff ) */ /* 8191 0.267 0.250 0.461 ( 0.264 ) */ /* 10000 0.300 0.283 0.578 ( 0.331 ) */ /* 20000 0.650 0.783 1.195 ( 0.684 ) */ /* 40000 1.333 1.767 2.383 ( 1.365 ) */ /* 80000 2.917 3.750 4.820 ( 2.761 ) */ /* 160000 7.833 8.033 9.758 ( 5.589 ) */ /* 320000 17.600 17.717 ------ | */ /* | */ /* Scaled to 25 MHz --------------------+ */ /* */ /* Average Run Time relative to 10 Iterations and 8191 array size: */ /* 0.315 0.345 0.484 */ /* */ /* The VAX 8600 results are different from those that appeared in the */ /* Jun Byte Article because I thought I could not define 'register' */ /* variables at all, but I was in error. 'register long' variables */ /* seem to work fine on our VAX 8600 UNIX 4.3 C compiler. It is the */ /* register 'short' types that (apparently) cause problems. */ /* */ /************************************************************************/ /**********************************************/ /* You may just want to uncomment one of */ /* these for your system. */ /**********************************************/ /* #define Amiga */ /* #define UNIX */ /* #define TURBO_C */ #ifdef UNIX #include #include #endif #ifdef Amiga #include #include #include #include #endif #ifdef TURBO_C #include #include #include #include #endif #define false 0 #define true 1 #define limit 6 #ifdef UNIX #define HZ 60 struct tms tms; #endif #ifdef Amiga #define HZ 50 #endif #ifdef TURBO_C #define HZ 100 struct time now; #endif float TimeArray[3]; float nulltime,benchtime; main() { long i,j; float sumtime; printf("\n Sieve of Eratosthenes (scaled to 10 Iterations)\n\n"); printf(" Array Size Primes Last Prime BenchTime\n"); printf(" (Bytes) Found (Sec)\n"); dtime(TimeArray); dtime(TimeArray); nulltime = TimeArray[1]; sumtime = 0.0; j = 8191; SIEVE(j); sumtime = sumtime + benchtime; j = 5000; for( i=1 ; i<= limit ; i++) { j = 2 * j; SIEVE(j); sumtime = sumtime + benchtime * ( 8191.0 / (float)j ); } sumtime = sumtime / (float)(limit + 1); printf("\n Relative to 10 Iterations and the 8191 Array Size:\n"); printf(" Average BenchTime = %8.3f (sec)\n\n",sumtime); } /**************************************/ /* Sieve of Erathosthenes Benchmark */ /* Version By William L. Hembree */ /* Las Cruces, New Mexico */ /**************************************/ SIEVE(n) long n; { register char *flags; register long i,prime,k; register long count,size; long j,m,iter; char *ptr = 0L; char *malloc(); size = n - 1; ptr = malloc(n); flags = ptr; dtime(TimeArray); dtime(TimeArray); nulltime = TimeArray[1]; j = 0; dtime(TimeArray); for(iter=1 ; iter<=10 ; iter++) { count = 0; for(i=0 ; i<=size ; i++) { *(flags+i) = true; } for(i=0 ; i<=size ; i++) { if(*(flags+i)) { prime = i + i + 3; for(k = i + prime ; k<=size ; k+=prime) { *(flags+k)=false; } count++; } } j = j + count; } dtime(TimeArray); benchtime = TimeArray[1] - nulltime; j = j / 10; m = prime; printf(" %8ld %8ld %8ld %9.3f\n",n,j,m,benchtime); } #ifdef UNIX /***********************************************/ /* dtime function for the VAX UNIX C Compiler */ /* dtime() returns elapsed time in seconds. */ /***********************************************/ dtime(p) float p[]; { float q; q = p[2]; times(&tms); p[2] = (double)(tms.tms_utime) / (float)HZ; p[1] = p[2] - q; } #endif #ifdef Amiga /**********************************/ /* dtime function for the Amiga */ /**********************************/ 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; } #endif #ifdef TURBO_C /*************************************************/ /* dtime for IBM PC/PC-AT systems with TURBO C */ /*************************************************/ 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; } #endif /************************ End Of NSIEVE C Source Code **********************/