\
\  Comparison of various Eratosthenes sieve implememtations
\  in Multi-Forth.
\
\  04/09/86    By Don Colburn
\  For a complete discussion of the methods involved, and a better
\  understanding of use of the sieve as a benchmark, refer to
\  a Letter to the Editor of mine that was published in
\  Dr Dobb's Journal, September 1983, Pages 9-10.
\
\  This comparison contrasts the origional byte coding,
\  coding with reasonable improvments based on address indices,
\  and the improved coding using local variables. The latter two
\  implementations more closely follow the methods used by the
\  C and Pascal implementations.
\
\  The resulting numbers should give some idea of the significant
\  performance increases in the latest generation CSI Multi-Forth
\  engine.
\
\  Timings on an 512k Amiga:
\
\  Sieve1   21.80 seconds     ( Origional Byte coding)
\  Sieve2   13.80 seconds     ( improved address indices)
\  Sieve3   12.20 seconds     ( Sieve2 with local variables)
\

10000 minimum.object

find timer not                   \ requires timer facility
   iftrue include" timer" ifend



8192 constant size
variable flags  size allot


\
\  origional sieve from byte
\

: prime1
   flags  size 1 fill                          \ set array
   0                                           \ zero count
   size 0                                      \ range
   do  flags  i + c@                           \ prime?
     if  i dup + 3+ dup i +                    \ yes, 
         begin  dup size <                     \ hit modulo flags
            while  0 over flags + c!  over +
         repeat
         drop drop 1+                          \ accumulate count
     then
   loop
   .  ." primes "  ;

: sieve1  ( 10 passes of prime1)
   mark
   10 0 do prime1  loop
   cr ?time  ." required by 10 passes origional Byte coding "  ;


\
\  improved coding
\

: prime2
   flags  size 1 fill                          \ set array
   0                                           \ zero count
   size 0                                      \ range
   do  flags  i+ c@                            \ prime?
     if  3 i+ i+  dup i+  size <               \ yes, i*3+3 < size ?
       if  size flags + over i+  flags +       \ yes, hit modulo flags
          do 0 ic! dup +loop
       then  drop 1+                           \ bump prime count
      then
   loop
   .  ." primes "  ;

: sieve2    ( 10 passes of prime2)
   mark
   10 0 do prime2 loop
   cr ?time  ." required by 10 passes improved coding "  ;


\
\  improved coding using locals
\

: prime3
   flags  size 1 fill                          \ set array
   flags size +  0  0
   locals|  #primes  prime*2+3  limit  |

   limit 1+  flags
   do  ic@                                     \ prime?
     if i flags - 2* 3+ dup to prime*2+3       \ yup, use prime*2+3 as index
       i+ limit <                              \ < size ?
          if limit 1+   prime*2+3  i+          \ yes, hit flags
             do 0 ic! prime*2+3 +loop          \ modulo prime*2+3
          then
        #primes  1+  to #primes                \ bump prime count
     then
   loop
   #primes .  ." primes "  ;

: sieve3
   mark
   10 0 do prime3 loop
   cr ?time  ." required by 10 passes improved locals coding "  ;


cr ." Sieve comparison loaded. Enter:  "
cr ." Sieve1       ( times origional byte coding) "
cr ." Sieve2       ( times improved address index coding) "
cr ." Sieve3       ( times improved locals coding) "