/* ************* Start NSIEVE C Source Code ******************* */ /* ************************************************************ */ /* NSIEVE */ /* C Program Source */ /* Sieve benchmark for variable sized arrays */ /* Version 1.2b, 26 Sep 1992 */ /* Al Aburto (aburto@nosc.mil) */ /* */ /* */ /* 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 = 13. */ /* */ /* 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 4774994 81919993 */ /* 81920000 14 ------- --------- */ /* ************************************************************ */ [DEFINED] -work [IF] -work [THEN] MARKER -work /* ******************************************** */ 9 =: LIMIT /* You may need to change this to '3' for PC's */ /* and Clones or you can experiment with higher */ /* values, but '13' is currently the max. */ /* ******************************************** */ 0 VALUE nulltime 0 VALUE runtime 0 VALUE reftime 0 VALUE adj_time 0e FVALUE emips 0e FVALUE hmips 0e FVALUE lmips CREATE smips #21 FLOATS ALLOT 0 VALUE L_Prime 0 VALUE N_Prime /* Last Prime and Number of Primes Found */ 0 VALUE ErrorFlag /* List of Correct Number of Primes for */ /* each sieve array size. */ CREATE Number_Of_Primes /* *************************** */ /* Number of Array Size */ /* Primes Found (Bytes) */ #1899 , /* 8191 */ #2261 , /* 10000 */ #4202 , /* 20000 */ #7836 , /* 40000 */ #14683 , /* 80000 */ #27607 , /* 160000 */ #52073 , /* 320000 */ #98609 , /* 640000 */ #187133 , /* 1280000 */ #356243 , /* 2560000 */ #679460 , /* 5120000 */ #1299068 , /* 10240000 */ #2488465 , /* 20480000 */ #4774994 , /* 40960000 */ 0 , /* 81920000 */ 0 , /* 163840000 */ CREATE NLoops #21 CELLS ALLOT /* ********************************** */ /* Sieve of Erathosthenes Program */ /* ********************************** */ : SIEVE ( m n p -- ) ROT DUP ALLOCATE IF DROP 3DROP 2 TO ErrorFlag EXIT ENDIF 0 0 0 0 LOCALS| eflags count ci j flags[] size p n | flags[] size + TO eflags 0 TO ErrorFlag 0 TO N_Prime 0 TO L_Prime TIMER-RESET MS? 0 MAX TO nulltime TIMER-RESET n 0 ?DO CLEAR count CLEAR ci flags[] size 1 FILL size 0 ?DO flags[] I + C@ IF 1 +TO count /* count++ */ I 2* 3 + /* prime = i + i + 3; */ eflags OVER I + flags[] + DUP eflags < IF ?DO 1 +TO ci /* for(k=i+prime; kF 1e-2 F* runtime S>F F/ TO emips j n / TO N_Prime p IF CR size #11 .R N_Prime #10 .R L_Prime #11 .R 2 SPACES adj_time 9 .R 2 SPACES runtime 9 .R 5 SPACES emips 6 F.R ENDIF ; : MAIN ( -- ) 0 0 0 LOCALS| jj p sumtime | PRECISION >R 3 SET-PRECISION CR ." Sieve of Eratosthenes (scaled to 10 iterations)" CR ." Version 1.2b, 26 Sep 1992" CR CR ." Array Size Number Last Prime Linear RunTime MIPS" CR ." (Bytes) of Primes Time(msec) (msec) " #8191 #256 0 SIEVE 8 TO p runtime #125 > IF 1 TO p ENDIF #256 p * NLoops 0 CELL[] ! #256 p * NLoops 1 CELL[] ! #128 p * NLoops 2 CELL[] ! #64 p * NLoops 3 CELL[] ! #32 p * NLoops 4 CELL[] ! #16 p * NLoops 5 CELL[] ! 8 p * NLoops 6 CELL[] ! 4 p * NLoops 7 CELL[] ! 2 p * NLoops 8 CELL[] ! p NLoops 9 CELL[] ! p 2/ NLoops #10 CELL[] ! p 2/ 2/ NLoops #10 CELL[] ! p 1 = IF 1 Nloops #10 CELL[] ! 1 Nloops #11 CELL[] ! ENDIF 0 TO sumtime #8191 Nloops 0 CELL[] @ p SIEVE runtime +TO sumtime emips smips 0 FLOAT[] F! #5000 TO jj CLEAR ErrorFlag LIMIT 1+ 1 DO jj 2* DUP TO jj Nloops I CELL[] @ p SIEVE emips smips I FLOAT[] F! ErrorFlag 0= N_prime Number_Of_Primes I CELL[] @ <> AND IF CR ." Error --- Incorrect Number of Primes for Array:" jj .R CR ." Number of Primes Found is: " N_Prime DEC. CR ." Correct Number of Primes is: " Number_Of_Primes I CELL[] @ DEC. 1 TO ErrorFlag LEAVE ENDIF runtime #8191 jj */ +TO sumtime LOOP ErrorFlag 2 = ABORT" Could Not Allocate Memory for Array Size" sumtime LIMIT / TO sumtime 0e TO hmips 1e6 TO lmips LIMIT 1+ 1 DO smips I FLOAT[] F@ hmips FMAX TO hmips smips I FLOAT[] F@ lmips FMIN TO lmips LOOP CR CR ." Relative to 10 iterations and the 8191 Array Size:" CR ." Average RunTime = " sumtime . ." (msec)" CR ." High MIPS = " hmips F. CR ." Low MIPS = " lmips F. R> SET-PRECISION ; DOC (* FORTH> main Sieve of Eratosthenes (scaled to 10 iterations) Version 1.2b, 26 Sep 1992 Array Size Number Last Prime Linear RunTime MIPS (Bytes) of Primes Time(msec) (msec) 8191 1899 16381 25 25 66.322 10000 2261 19997 30 32 63.497 20000 4202 39989 61 76 54.164 40000 7836 79999 122 164 50.812 80000 14683 160001 244 343 49.153 160000 27607 319993 488 707 48.214 320000 52073 639997 976 1539 44.758 640000 98609 1279997 1953 3224 43.154 1280000 187133 2559989 3906 6675 42.078 2560000 356243 5119997 7813 13786 41.113 Relative to 10 iterations and the 8191 Array Size: Average RunTime = 39 (msec) High MIPS = 63.49 Low MIPS = 41.11 *) ENDDOC /* ------ End of nsieve.c, say goodnight Liz! (Sep 1992) ------ */