User:Ashmanskas/p364/prime.sasm
From LaPET electronics
< User:Ashmanskas | p364
prime.sasm
# # 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 # # If we reach here, then i is a prime number. The only purpose # of the code below is to convert i from binary into decimal so # that the LED display can be understood by human observers. # jdone: load zero # 'outnum' will hold the binary-coded decimal result store outnum # outnum := 0 load i # store remain # remainder := i sub d10000 # jumpn thsnds # jump out of entire i loop if i too big to display jump done # if (i>10000) goto done thsnds: load zero # initialize 1000's digit to 0 store hdigit # digit := 0 nx1000: load remain # loop over values for 1000's digit sub d1000 # jumpn hndrds # if (remainder<1000) goto hundreds store remain # remainder := remainder-1000 load hdigit # add h1000 # store hdigit # digit := digit+0x1000 jump nx1000 # keep looping over values for 1000's digit hndrds: load hdigit # add the 1000's digit to 'outnum' total add outnum # store outnum # outnum := outnum+digit load zero # store hdigit # digit := 0 nxt100: load remain # loop over values for 100's digit sub d100 # jumpn tens # if (remainder<100) goto tens store remain # remainder := remainder-100 load hdigit # add h100 # store hdigit # digit := digit+0x100 jump nxt100 # keep looping over values for 100's digit tens: load hdigit # add the 100's digit to 'outnum' total add outnum # store outnum # outnum := outnum+digit load zero # store hdigit # digit := 0 nxt10: load remain # loop over values for 10's digit sub d10 # jumpn ones # if (remainder<10) goto ones store remain # remainder := remainder-10 load hdigit # add h10 # store hdigit # digit := digit+0x10 jump nxt10 # keep looping over values for 10's digit ones: load hdigit # add the 10's digit to 'outnum' total add outnum # add remain # now the remainder equals the ones digit store outnum # outnum := outnum+digit+remainder out # copy 'outnum' to LED display # # This block is here to delay O(1 second) after displaying # each new prime number, so that (especially early in the # sequence, when the loop over factors goes quickly) the # observer has time to see each number display. # # Since the largest value we can hold in a register is 65535, # and we need about ten times longer delay than that, we make # a double loop using both j and k as loop counters. # load zero # sub one # store j # j := 65535 jdelay: load j # loop j from 65535 downto 1 sub one # store j # j := j-1 jumpz iloop # if (j==0) goto iloop // try next candididate i load d10 # store k # k := 10 kdelay: load k # loop k from 10 downto 1 sub one # store k # k := k-1 jumpz jdelay # if (k==0) goto jdelay // break out out to j loop jump kdelay # keep looping over k values 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 outnum: .data 0 # compute/store binary-coded-decimal conversion of i remain: .data 0 # store remainder used in BCD computation hdigit: .data 0 # store hex value used to display one decimal digit h1000: .data 1000 # store hexadecimal constant 0x1000 h100: .data 100 # store hexadecimal constant 0x100 h10: .data 10 # store hexadecimal constant 0x10 d10000: .data 2710 # store decimal constant 10000 d1000: .data 3e8 # store decimal constant 1000 d100: .data 64 # store decimal constant 100 d10: .data a # store decimal constant 10
