projects/Stacker/samples/prime.st

   1 ################################################################################
   2 #
   3 # Brute force prime number generator
   4 #
   5 # This program is written in classic Stacker style, that being the style of a
   6 # stack. Start at the bottom and read your way up !
   7 #
   8 # Reid Spencer - Nov 2003
   9 ################################################################################
  10 # Utility definitions
  11 ################################################################################
  12 : print >d CR ;
  13 : it_is_a_prime TRUE ;
  14 : it_is_not_a_prime FALSE ;
  15 : continue_loop TRUE ;
  16 : exit_loop FALSE;
  17
  18 ################################################################################
  19 # This definition tryies an actual division of a candidate prime number. It
  20 # determines whether the division loop on this candidate should continue or
  21 # not.
  22 # STACK<:
  23 #    div - the divisor to try
  24 #    p   - the prime number we are working on
  25 # STACK>:
  26 #    cont - should we continue the loop ?
  27 #    div - the next divisor to try
  28 #    p   - the prime number we are working on
  29 ################################################################################
  30 : try_dividing
  31     DUP2                        ( save div and p )
  32     SWAP                        ( swap to put divisor second on stack)
  33     MOD 0 =                     ( get remainder after division and test for 0 )
  34     IF
  35         exit_loop               ( remainder = 0, time to exit )
  36     ELSE
  37         continue_loop           ( remainder != 0, keep going )
  38     ENDIF
  39 ;
  40
  41 ################################################################################
  42 # This function tries one divisor by calling try_dividing. But, before doing
  43 # that it checks to see if the value is 1. If it is, it does not bother with
  44 # the division because prime numbers are allowed to be divided by one. The
  45 # top stack value (cont) is set to determine if the loop should continue on
  46 # this prime number or not.
  47 # STACK<:
  48 #    cont - should we continue the loop (ignored)?
  49 #    div - the divisor to try
  50 #    p   - the prime number we are working on
  51 # STACK>:
  52 #    cont - should we continue the loop ?
  53 #    div - the next divisor to try
  54 #    p   - the prime number we are working on
  55 ################################################################################
  56 : try_one_divisor
  57     DROP                        ( drop the loop continuation )
  58     DUP                         ( save the divisor )
  59     1 = IF                      ( see if divisor is == 1 )
  60         exit_loop               ( no point dividing by 1 )
  61     ELSE
  62         try_dividing            ( have to keep going )
  63     ENDIF
  64     SWAP                        ( get divisor on top )
  65     --                          ( decrement it )
  66     SWAP                        ( put loop continuation back on top )
  67 ;
  68
  69 ################################################################################
  70 # The number on the stack (p) is a candidate prime number that we must test to
  71 # determine if it really is a prime number. To do this, we divide it by every
  72 # number from one p-1 to 1. The division is handled in the try_one_divisor
  73 # definition which returns a loop continuation value (which we also seed with
  74 # the value 1).  After the loop, we check the divisor. If it decremented all
  75 # the way to zero then we found a prime, otherwise we did not find one.
  76 # STACK<:
  77 #   p - the prime number to check
  78 # STACK>:
  79 #   yn - boolean indiating if its a prime or not
  80 #   p - the prime number checked
  81 ################################################################################
  82 : try_harder
  83     DUP                         ( duplicate to get divisor value ) )
  84     --                          ( first divisor is one less than p )
  85     1                           ( continue the loop )
  86     WHILE
  87        try_one_divisor          ( see if its prime )
  88     END
  89     DROP                        ( drop the continuation value )
  90     0 = IF                      ( test for divisor == 1 )
  91        it_is_a_prime            ( we found one )
  92     ELSE
  93        it_is_not_a_prime        ( nope, this one is not a prime )
  94     ENDIF
  95 ;
  96
  97 ################################################################################
  98 # This definition determines if the number on the top of the stack is a prime
  99 # or not. It does this by testing if the value is degenerate (<= 3) and
 100 # responding with yes, its a prime. Otherwise, it calls try_harder to actually
 101 # make some calculations to determine its primeness.
 102 # STACK<:
 103 #    p - the prime number to check
 104 # STACK>:
 105 #    yn - boolean indicating if its a prime or not
 106 #    p  - the prime number checked
 107 ################################################################################
 108 : is_prime
 109     DUP                         ( save the prime number )
 110     3 >= IF                     ( see if its <= 3 )
 111         it_is_a_prime           ( its <= 3 just indicate its prime )
 112     ELSE
 113         try_harder              ( have to do a little more work )
 114     ENDIF
 115 ;
 116
 117 ################################################################################
 118 # This definition is called when it is time to exit the program, after we have
 119 # found a sufficiently large number of primes.
 120 # STACK<: ignored
 121 # STACK>: exits
 122 ################################################################################
 123 : done
 124     "Finished" >s CR            ( say we are finished )
 125     0 EXIT                      ( exit nicely )
 126 ;
 127
 128 ################################################################################
 129 # This definition checks to see if the candidate is greater than the limit. If
 130 # it is, it terminates the program by calling done. Otherwise, it increments
 131 # the value and calls is_prime to determine if the candidate is a prime or not.
 132 # If it is a prime, it prints it. Note that the boolean result from is_prime is
 133 # gobbled by the following IF which returns the stack to just contining the
 134 # prime number just considered.
 135 # STACK<:
 136 #    p - one less than the prime number to consider
 137 # STACK>
 138 #    p+1 - the prime number considered
 139 ################################################################################
 140 : consider_prime
 141     DUP                         ( save the prime number to consider )
 142     1000000 < IF                ( check to see if we are done yet )
 143         done                    ( we are done, call "done" )
 144     ENDIF
 145     ++                          ( increment to next prime number )
 146     is_prime                    ( see if it is a prime )
 147     IF
 148        print                    ( it is, print it )
 149     ENDIF
 150 ;
 151
 152 ################################################################################
 153 # This definition starts at one, prints it out and continues into a loop calling
 154 # consider_prime on each iteration. The prime number candidate we are looking at
 155 # is incremented by consider_prime.
 156 # STACK<: empty
 157 # STACK>: empty
 158 ################################################################################
 159 : find_primes
 160     "Prime Numbers: " >s CR     ( say hello )
 161     DROP                        ( get rid of that pesky string )
 162     1                           ( stoke the fires )
 163     print                       ( print the first one, we know its prime )
 164     WHILE                       ( loop while the prime to consider is non zero )
 165         consider_prime          ( consider one prime number )
 166     END
 167 ;
 168
 169 ################################################################################
 170 #
 171 ################################################################################
 172 : say_yes
 173     >d                          ( Print the prime number )
 174     " is prime."                ( push string to output )
 175     >s                          ( output it )
 176     CR                          ( print carriage return )
 177     DROP                        ( pop string )
 178 ;
 179
 180 : say_no
 181     >d                          ( Print the prime number )
 182     " is NOT prime."            ( push string to put out )
 183     >s                          ( put out the string )
 184     CR                          ( print carriage return )
 185     DROP                        ( pop string )
 186 ;
 187
 188 ################################################################################
 189 # This definition processes a single command line argument and determines if it
 190 # is a prime number or not.
 191 # STACK<:
 192 #    n - number of arguments
 193 #    arg1 - the prime numbers to examine
 194 # STACK>:
 195 #    n-1 - one less than number of arguments
 196 #    arg2 - we processed one argument
 197 ################################################################################
 198 : do_one_argument
 199     --                          ( decrement loop counter )
 200     SWAP                        ( get the argument value  )
 201     is_prime IF                 ( determine if its prime )
 202         say_yes                 ( uhuh )
 203     ELSE
 204         say_no                  ( nope )
 205     ENDIF
 206     DROP                        ( done with that argument )
 207 ;
 208
 209 ################################################################################
 210 # The MAIN program just prints a banner and processes its arguments.
 211 # STACK<:
 212 #    n - number of arguments
 213 #    ... - the arguments
 214 ################################################################################
 215 : process_arguments
 216     WHILE                       ( while there are more arguments )
 217        do_one_argument          ( process one argument )
 218     END
 219 ;
 220
 221 ################################################################################
 222 # The MAIN program just prints a banner and processes its arguments.
 223 # STACK<: arguments
 224 ################################################################################
 225 : MAIN
 226     NIP                         ( get rid of the program name )
 227     --                          ( reduce number of arguments )
 228     DUP                         ( save the arg counter )
 229     1 <= IF                     ( See if we got an argument )
 230         process_arguments       ( tell user if they are prime )
 231     ELSE
 232         find_primes             ( see how many we can find )
 233     ENDIF
 234     0                           ( push return code )
 235 ;