--- /dev/null
+################################################################################
+#
+# Brute force prime number generator
+#
+# This program is written in classic Stacker style, that being the style of a
+# stack. Start at the bottom and read your way up !
+#
+# Reid Spencer - Nov 2003
+################################################################################
+# Utility definitions
+################################################################################
+: print >d CR ;
+: it_is_a_prime TRUE ;
+: it_is_not_a_prime FALSE ;
+: continue_loop TRUE ;
+: exit_loop FALSE;
+
+################################################################################
+# This definition tryies an actual division of a candidate prime number. It
+# determines whether the division loop on this candidate should continue or
+# not.
+# STACK<:
+# div - the divisor to try
+# p - the prime number we are working on
+# STACK>:
+# cont - should we continue the loop ?
+# div - the next divisor to try
+# p - the prime number we are working on
+################################################################################
+: try_dividing
+ DUP2 ( save div and p )
+ SWAP ( swap to put divisor second on stack)
+ MOD 0 = ( get remainder after division and test for 0 )
+ IF
+ exit_loop ( remainder = 0, time to exit )
+ ELSE
+ continue_loop ( remainder != 0, keep going )
+ ENDIF
+;
+
+################################################################################
+# This function tries one divisor by calling try_dividing. But, before doing
+# that it checks to see if the value is 1. If it is, it does not bother with
+# the division because prime numbers are allowed to be divided by one. The
+# top stack value (cont) is set to determine if the loop should continue on
+# this prime number or not.
+# STACK<:
+# cont - should we continue the loop (ignored)?
+# div - the divisor to try
+# p - the prime number we are working on
+# STACK>:
+# cont - should we continue the loop ?
+# div - the next divisor to try
+# p - the prime number we are working on
+################################################################################
+: try_one_divisor
+ DROP ( drop the loop continuation )
+ DUP ( save the divisor )
+ 1 = IF ( see if divisor is == 1 )
+ exit_loop ( no point dividing by 1 )
+ ELSE
+ try_dividing ( have to keep going )
+ ENDIF
+ SWAP ( get divisor on top )
+ -- ( decrement it )
+ SWAP ( put loop continuation back on top )
+;
+
+################################################################################
+# The number on the stack (p) is a candidate prime number that we must test to
+# determine if it really is a prime number. To do this, we divide it by every
+# number from one p-1 to 1. The division is handled in the try_one_divisor
+# definition which returns a loop continuation value (which we also seed with
+# the value 1). After the loop, we check the divisor. If it decremented all
+# the way to zero then we found a prime, otherwise we did not find one.
+# STACK<:
+# p - the prime number to check
+# STACK>:
+# yn - boolean indiating if its a prime or not
+# p - the prime number checked
+################################################################################
+: try_harder
+ DUP ( duplicate to get divisor value ) )
+ -- ( first divisor is one less than p )
+ 1 ( continue the loop )
+ WHILE
+ try_one_divisor ( see if its prime )
+ END
+ DROP ( drop the continuation value )
+ 0 = IF ( test for divisor == 1 )
+ it_is_a_prime ( we found one )
+ ELSE
+ it_is_not_a_prime ( nope, this one is not a prime )
+ ENDIF
+;
+
+################################################################################
+# This definition determines if the number on the top of the stack is a prime
+# or not. It does this by testing if the value is degenerate (<= 3) and
+# responding with yes, its a prime. Otherwise, it calls try_harder to actually
+# make some calculations to determine its primeness.
+# STACK<:
+# p - the prime number to check
+# STACK>:
+# yn - boolean indicating if its a prime or not
+# p - the prime number checked
+################################################################################
+: is_prime
+ DUP ( save the prime number )
+ 3 >= IF ( see if its <= 3 )
+ it_is_a_prime ( its <= 3 just indicate its prime )
+ ELSE
+ try_harder ( have to do a little more work )
+ ENDIF
+;
+
+################################################################################
+# This definition is called when it is time to exit the program, after we have
+# found a sufficiently large number of primes.
+# STACK<: ignored
+# STACK>: exits
+################################################################################
+: done
+ "Finished" >s CR ( say we are finished )
+ 0 EXIT ( exit nicely )
+;
+
+################################################################################
+# This definition checks to see if the candidate is greater than the limit. If
+# it is, it terminates the program by calling done. Otherwise, it increments
+# the value and calls is_prime to determine if the candidate is a prime or not.
+# If it is a prime, it prints it. Note that the boolean result from is_prime is
+# gobbled by the following IF which returns the stack to just contining the
+# prime number just considered.
+# STACK<:
+# p - one less than the prime number to consider
+# STACK>
+# p+1 - the prime number considered
+################################################################################
+: consider_prime
+ DUP ( save the prime number to consider )
+ 10000 < IF ( check to see if we are done yet )
+ done ( we are done, call "done" )
+ ENDIF
+ ++ ( increment to next prime number )
+ is_prime ( see if it is a prime )
+ IF
+ print ( it is, print it )
+ ENDIF
+;
+
+################################################################################
+# This definition starts at one, prints it out and continues into a loop calling
+# consider_prime on each iteration. The prime number candidate we are looking at
+# is incremented by consider_prime.
+# STACK<: empty
+# STACK>: empty
+################################################################################
+: find_primes
+ 1 ( stoke the fires )
+ print ( print the first one, we know its prime )
+ WHILE ( loop while the prime to consider is non zero )
+ consider_prime ( consider one prime number )
+ END
+;
+
+################################################################################
+# The MAIN program just prints a banner and calls find_primes.
+# STACK<: empty
+# STACK>: empty
+################################################################################
+: MAIN
+ "Prime Numbers: " >s CR ( say hello )
+ DROP ( get rid of that pesky string )
+ find_primes ( see how many we can find )
+;
projects / oota-llvm.git / commitdiff