#
	# prime.sasm
	# coded 2010-11-11 by Bill Ashmanskas, ashmansk@hep.upenn.edu
	#
	# The purpose of this program is to demonstrate that the CPU
	# implemented in simple_cpu.v is capable of carrying out a
	# non-trivial computation.
	#
	# This is probably the dumbest imaginable algorithm to compute
	# prime numbers.  Its execution time scales as the third power
	# of the number of candidates to evaluate.  For every candidate i,
	# loop over possible factors j and k, testing whether i==j*k.  If
	# no such j and k are found, then display i on the LEDs.
	#
	# Note that with storage for a mere 5000 boolean values (which
	# I could have easily cooked up), one can use a much more efficient
	# algorithm, the Sieve of Eratosthenes.  It scales (with number of
	# candidate integers N) as N*log(N)*log(log(N)), while my algorithm 
	# scales as N**3.  I point this out only so that you don't think
	# that I think the N**3 algorithm is a good way to compute primes.
	#
start:	load	one	#
	store	i	#  i := 1
iloop:	load	i	#  loop i from 2 to 32767
	add	one	#
	store	i	#    i := i+1
	jumpn	done	#    if (i>=32768) goto done
	load	zero	#
	store	j	#    j := 0
jloop:	load	j	#    loop j from 1 to i-1
	add	one	#
	store	j	#      j := j+1
	load	i	#
	sub	j	#
	jumpz	jdone	#      if (i==j) goto jdone
	load	zero	#
	store	k	#      k := 0
kloop:	load	k	#      loop k from 1 to i-1
	add	one	#
	store	k	#        k := k+1
	sub	i	#
	jumpz	jloop	#        if (k==i) goto jloop
	load	j	#
	mul	k	#
	store	prod	#        product := j*k
	sub	i	#        // if j*k==i then i is not prime
	jumpz	iloop	#        if (product==i) goto iloop  // skip to next i
	jumpn	kloop	#        if (product<i)  goto kloop  // keep looping k
			#        // k exceeds i/j, so skip to next j
	jump	jloop	#        goto jloop
	#
	# I moved the binary-to-decimal conversion that is here in the
	# complete example, for simplicity
	#
jdone:	load	i
	out		#  copy 'i' to LED display
	jump	iloop	#  goto iloop  // try next candididate i
done:	jump	start	#  go back and start counting again from i==2
zero:	.data	0	#  store the constant '0'
one:	.data	1	#  store the constant '1'
i:	.data	0	#  store the loop variable 'i' (prime number cand.)
j:	.data	0	#  store the loop variable 'j'
k:	.data	0	#  store the loop variable 'k'
prod:	.data	0	#  store the product 'prod' = j*k