Here is the description of a new assembly language: * 8 registers (R1, R2, R3, R4, R5, R6, R7, R8) that can hold integers. * 1 flag that can hold a boolean value (True or False). * 100 memory addresses (0-99) that can hold integers. * 1 instruction pointer that points to the current instruction being executed. Each instruction is of the form OP ARG1 ARG2 ... where ARGn can be either a register (e.g., R1) or a constant (e.g., 10). Labels are written with a lowercase word followed by colon. The assembly language supports the following instructions: * SET Rx C: Assigns the value C to register Rx. * ADD Rx Ry Rz: Adds the values of Ry and Rz and stores the result in Rx. * (similarly for SUB, MUL, DIV, MOD) * EQ Rx Ry: Sets the flag to True if Rx and Ry are equal, False otherwise. * (similarly for NEQ, LT (Rx < Ry), LTE, GT, GTE) * INC/DEC Rx: Increments/Decrements the value of Rx by one. * JMP L: Jumps to label L unconditionally. * JT/JF (jump if true / jump if false) L: Jumps to label L if the is set or not set. * LOAD Rx M: Loads the value at memory address M into register Rx. * STORE Rx M: Stores the value of register Rx into memory address M. * HCF: Stops the program (with pizzazz) Given this assembly language, write a program that puts the first 20 prime numbers in memory cells 0..19
Here is the description of a new assembly language: * 8 registers (R1, R2, R3, R4, R5, R6, R7, R8) that can hold integers. * 1 flag that can hold a boolean value (True or False). * 100 memory addresses (0-99) that can hold integers. * 1 instruction pointer that points to the current instruction being executed. Each instruction is of the form OP ARG1 ARG2 ... where ARGn can be either a register (e.g., R1) or a constant (e.g., 10). Labels are written with a lowercase word followed by colon. The assembly language supports the following instructions: * SET Rx C: Assigns the value C to register Rx. * ADD Rx Ry Rz: Adds the values of Ry and Rz and stores the result in Rx. * (similarly for SUB, MUL, DIV, MOD) * EQ Rx Ry: Sets the flag to True if Rx and Ry are equal, False otherwise. * (similarly for NEQ, LT (Rx < Ry), LTE, GT, GTE) * INC/DEC Rx: Increments/Decrements the value of Rx by one. * JMP L: Jumps to label L unconditionally. * JT/JF (jump if true / jump if false) L: Jumps to label L if the is set or not set. * LOAD Rx M: Loads the value at memory address M into register Rx. * STORE Rx M: Stores the value of register Rx into memory address M. * HCF: Stops the program (with pizzazz) Given this assembly language, write a program that puts the first 20 prime numbers in memory cells 0..19
Below is one acceptable solution. In this solution we use: • R1 – candidate number (starting at 2) • R2 – count (and next free memory cell index) for the found primes • R3 – loop index used to scan through the primes in memory • R4 – holds a prime loaded from memory • R5 – holds the remainder when candidate is divided by a stored prime • R6 – the constant 1 (used for incrementing) • R7 – the constant 0 (used when comparing remainders) • R8 – the constant 20 (the goal count) The program works by trying successive numbers (starting at 2) in R1. For each candidate it tests divisibility by every stored prime value in memory cells 0..(R2–1). When R2 is zero (i.e. no primes stored yet) the candidate is automatically accepted. If any stored prime divides the candidate evenly (i.e. remainder 0), the candidate is rejected. If no divisor is found, the candidate is written to memory at address R2 and R2 is incremented. The search stops when R2 reaches 20, and then the HCF instruction stops the program. Here is the complete assembly program: SET R6 1 ; constant 1 SET R7 0 ; constant 0 SET R8 20 ; goal: first 20 primes SET R1 2 ; candidate number starts at 2 SET R2 0 ; count = 0 outer_loop: EQ R2 R8 ; compare count with 20 JT end ; if count == 20, we are done EQ R2 R7 ; check if count == 0 JT store_candidate ; if so, candidate is the first prime SET R3 0 ; set loop index for inner loop to 0 check_loop: EQ R3 R2 ; if index == count, no divisor found JT store_candidate ; candidate is prime LOAD R4 R3 ; load stored prime at memory address held in R3 MOD R5 R1 R4 ; compute R5 = candidate (R1) mod stored prime (R4) EQ R5 R7 ; check if remainder == 0 JT not_prime ; if yes, candidate is divisible => not prime ADD R3 R3 R6 ; increment loop index R3 = R3 + 1 JMP check_loop ; repeat inner loop store_candidate: STORE R1 R2 ; store candidate prime in memory cell [R2] ADD R2 R2 R6 ; increment prime count ADD R1 R1 R6 ; try next candidate by incrementing R1 JMP outer_loop ; restart outer loop not_prime: ADD R1 R1 R6 ; candidate was not prime; try next candidate JMP outer_loop ; restart outer loop end: HCF ; halt the program When this program runs its execution will fill memory addresses 0 through 19 with the first 20 prime numbers.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | INCLUDE "asm_header.inc" SET R6 1 ; constant 1 SET R7 0 ; constant 0 SET R8 20 ; goal: first 20 primes SET R1 2 ; candidate number starts at 2 SET R2 0 ; count = 0 outer_loop: EQ R2 R8 ; compare count with 20 JT end ; if count == 20, we are done EQ R2 R7 ; check if count == 0 JT store_candidate ; if so, candidate is the first prime SET R3 0 ; set loop index for inner loop to 0 check_loop: EQ R3 R2 ; if index == count, no divisor found JT store_candidate ; candidate is prime LOAD R4 R3 ; load stored prime at memory address held in R3 MOD R5 R1 R4 ; compute R5 = candidate (R1) mod stored prime (R4) EQ R5 R7 ; check if remainder == 0 JT not_prime ; if yes, candidate is divisible => not prime ADD R3 R3 R6 ; increment loop index R3 = R3 + 1 JMP check_loop ; repeat inner loop store_candidate: STORE R1 R2 ; store candidate prime in memory cell [R2] ADD R2 R2 R6 ; increment prime count ADD R1 R1 R6 ; try next candidate by incrementing R1 JMP outer_loop ; restart outer loop not_prime: ADD R1 R1 R6 ; candidate was not prime; try next candidate JMP outer_loop ; restart outer loop end: HCF ; halt the program |
integer division or modulo by zero Resulting in output: False
Here is the description of a new assembly language: * 8 registers (R1, R2, R3, R4, R5, R6, R7, R8) that can hold integers. * 1 flag that can hold a boolean value (True or False). * 100 memory addresses (0-99) that can hold integers. * 1 instruction pointer that points to the current instruction being executed. Each instruction is of the form OP ARG1 ARG2 ... where ARGn can be either a register (e.g., R1) or a constant (e.g., 10). Labels are written with a lowercase word followed by colon. The assembly language supports the following instructions: * SET Rx C: Assigns the value C to register Rx. * ADD Rx Ry Rz: Adds the values of Ry and Rz and stores the result in Rx. * (similarly for SUB, MUL, DIV, MOD) * EQ Rx Ry: Sets the flag to True if Rx and Ry are equal, False otherwise. * (similarly for NEQ, LT (Rx < Ry), LTE, GT, GTE) * INC/DEC Rx: Increments/Decrements the value of Rx by one. * JMP L: Jumps to label L unconditionally. * JT/JF (jump if true / jump if false) L: Jumps to label L if the is set or not set. * LOAD Rx M: Loads the value at memory address M into register Rx. * STORE Rx M: Stores the value of register Rx into memory address M. * HCF: Stops the program (with pizzazz) Given this assembly language, write a program that puts the first 20 prime numbers in memory cells 0..19
Here is the description of a new assembly language: * 8 registers (R1, R2, R3, R4, R5, R6, R7, R8) that can hold integers. * 1 flag that can hold a boolean value (True or False). * 100 memory addresses (0-99) that can hold integers. * 1 instruction pointer that points to the current instruction being executed. Each instruction is of the form OP ARG1 ARG2 ... where ARGn can be either a register (e.g., R1) or a constant (e.g., 10). Labels are written with a lowercase word followed by colon. The assembly language supports the following instructions: * SET Rx C: Assigns the value C to register Rx. * ADD Rx Ry Rz: Adds the values of Ry and Rz and stores the result in Rx. * (similarly for SUB, MUL, DIV, MOD) * EQ Rx Ry: Sets the flag to True if Rx and Ry are equal, False otherwise. * (similarly for NEQ, LT (Rx < Ry), LTE, GT, GTE) * INC/DEC Rx: Increments/Decrements the value of Rx by one. * JMP L: Jumps to label L unconditionally. * JT/JF (jump if true / jump if false) L: Jumps to label L if the is set or not set. * LOAD Rx M: Loads the value at memory address M into register Rx. * STORE Rx M: Stores the value of register Rx into memory address M. * HCF: Stops the program (with pizzazz) Given this assembly language, write a program that puts the first 20 prime numbers in memory cells 0..19
Below is one acceptable solution. In this example we use 8 registers as follows: • R1 holds the current candidate number (starting at 2). • R2 holds the number of primes found so far (and will serve as the memory address into which a new prime is stored). • R3 is used as the “trial divisor” when testing whether R1 is prime. • R4 is used to hold the remainder when doing a MOD operation. • R5 and R6 are “helper‐constants”: R5 is set to 1 and R6 to 2 so that (because 1 ≠ 2) the instruction “EQ R5 R6” will set the flag to False. (Conversely, “EQ R1 R1” always sets the flag to True.) • R7 is used as a scratch register to load constant values (for example, 20 when checking whether we have already stored 20 primes). • R8 is unused in this solution. Remember that every instruction has the form “OP ARG1 ARG2 …” and that label names end in a colon. The following program uses a nested‐loop strategy. The outer “candidate_loop” goes from candidate 2 upward. For each candidate (in R1) the inner “trial_loop” tests all possible divisors (R3 starts at 2 and counts upward) until R3 equals the candidate. If any divisor exactly divides the candidate (that is, MOD yields 0) then we set the flag to False (by doing “EQ R5 R6”). (Otherwise we set the flag to True by “EQ R1 R1”.) After the trial loop the flag tells whether R1 is prime. When a prime is found it is stored in memory address R2 and R2 is incremented. When R2 reaches 20 the program halts (with HCF). Here is the complete assembly program: ------------------------------------------------- ; Initialization SET R1 2 ; candidate = 2 SET R2 0 ; count = 0 (we will store primes at mem[0..19]) SET R5 1 ; prepare a constant “1” SET R6 2 ; prepare a constant “2” candidate_loop: SET R7 20 ; load constant 20 into R7 EQ R2 R7 ; if count equals 20 then flag = True JT end_prog ; jump to end if we have found 20 primes ; Assume candidate is prime. (We set the flag to True by comparing any register with itself.) EQ R1 R1 ; Initialize trial divisor to 2. SET R3 2 trial_loop: EQ R3 R1 ; if trial divisor equals candidate, JT store_prime_label ; then no divisor divides candidate and it is prime ; Compute the remainder: remainder = candidate MOD trial_divisor. MOD R4 R1 R3 SET R7 0 ; load constant 0 into R7 EQ R4 R7 ; if remainder == 0 then flag becomes True JT not_prime_label ; jump if candidate is divisible by R3 (i.e. not prime) INC R3 ; try the next divisor JMP trial_loop ; repeat the trial loop not_prime_label: ; Set flag to False using the fact that 1 != 2. EQ R5 R6 ; flag becomes False JMP next_candidate_label ; skip storing candidate since it isn’t prime store_prime_label: ; At this point the flag is still True (as set by EQ R1 R1 above), ; so the candidate is prime. Store it in memory cell [R2]. STORE R1 R2 INC R2 ; increment count of primes stored next_candidate_label: INC R1 ; candidate++: try the next candidate number JMP candidate_loop end_prog: HCF ; halt the program (with pizzazz) ------------------------------------------------- How the program works: 1. The program begins by initializing R1 (candidate number = 2) and R2 (prime count = 0). It also loads R5 with 1 and R6 with 2 so that “EQ R5 R6” will always set the flag to False. 2. At the very start of each “candidate_loop” the program sets R7 to 20 and compares R2 to 20. If R2 equals 20 (meaning 20 primes have been stored), the jump “JT end_prog” fires and the machine halts. 3. Otherwise, the program “assumes” the candidate is prime by executing “EQ R1 R1” (flag becomes True) and then tests divisibility: it sets R3 (trial divisor) to 2 and enters “trial_loop.” In trial_loop, if R3 equals R1 the inner loop (and so the trial–division test) is done. Otherwise the candidate is divided by R3 (using MOD) and if the remainder is 0 the flag is set to False and control jumps to “not_prime_label.” 4. If no divisor was found (i.e. once R3 equals R1) control jumps to “store_prime_label” where the candidate is stored in memory and R2 is incremented. 5. Finally, regardless of outcome, R1 is incremented and the next candidate is tested. When run, memory addresses 0 through 19 will contain the first 20 prime numbers. This is one valid solution given the instruction set described.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | IMPORT "asm_lib.inc" ; Initialization SET R1 2 ; candidate = 2 SET R2 0 ; count = 0 (we will store primes at mem[0..19]) SET R5 1 ; prepare a constant “1” SET R6 2 ; prepare a constant “2” candidate_loop: SET R7 20 ; load constant 20 into R7 EQ R2 R7 ; if count equals 20 then flag = True JT end_prog ; jump to end if we have found 20 primes ; Assume candidate is prime. (We set the flag to True by comparing any register with itself.) EQ R1 R1 ; Initialize trial divisor to 2. SET R3 2 trial_loop: EQ R3 R1 ; if trial divisor equals candidate, JT store_prime_label ; then no divisor divides candidate and it is prime ; Compute the remainder: remainder = candidate MOD trial_divisor. MOD R4 R1 R3 SET R7 0 ; load constant 0 into R7 EQ R4 R7 ; if remainder == 0 then flag becomes True JT not_prime_label ; jump if candidate is divisible by R3 (i.e. not prime) INC R3 ; try the next divisor JMP trial_loop ; repeat the trial loop not_prime_label: ; Set flag to False using the fact that 1 != 2. EQ R5 R6 ; flag becomes False JMP next_candidate_label ; skip storing candidate since it isn’t prime store_prime_label: ; At this point the flag is still True (as set by EQ R1 R1 above), ; so the candidate is prime. Store it in memory cell [R2]. STORE R1 R2 INC R2 ; increment count of primes stored next_candidate_label: INC R1 ; candidate++: try the next candidate number JMP candidate_loop end_prog: HCF ; halt the program (with pizzazz) |
Resulting in output: False