# 7.9: Exercises

1. When using a branch instruction, the lowest two bits in the offset to add to the $pc can be dropped. 1. Why can these two bits be dropped? 2. What must happen when the branch address is later calculated? 3. Do you think the lowest two bits can be dropped in the absolute address for a jump instruction? Why or why not? 2. In section 7.8.3 of the textbook, it was said that a branch could access addresses that were -8191...8192 distance from the current $pc. However the 2's complement integer has values from -8192..8191. Why the discrepancy between the value of the 2's complement integer and the size of the branch?
3. Write a program to find prime numbers from 3 to n in a loop by dividing the number n by all numbers from 2..n/2 in an inner loop. Using the remainder (rem) operation, determine if n is divisible by any number. If n is divisible, leave the inner loop. If the limit of n/2 is reached and the inner loop has not been exited, the number is prime and you should output the number. So if the user were to enter 25, your program would print out "2, 3, 5, 7, 11, 13, 17, 19, 23".
4. Write a program to prompt the user for a number, and determine if that number is prime. Your program should print out "Number n is prime" if the number is prime, and "Number n is not prime if the number is not prime. The user should be able to enter input a "-1" is entered. It should print an error if 0, 1, 2 or any negative number other than -1 are entered.
5. Write a program to allow a user to guess a random number generated by the computer from 1 to maximum (the user should enter the maximum value to guess). In this program the user will enter the value of maximum, and the syscall service 42 will be used to generate a random number from 1 to maximum. The user will then enter guesses and the program should print out if the guess is too high or too low until the user guesses the correct number. The program should print out the number of guesses the user took.
6. Write a program to guess a number chosen by the user. In this program a user will choose a secret number from 1..maximum. The program will prompt the user for the maximum value, which the user will enter. The program will then make a guess as to the value of the secret number, and prompt the user to say if the actual number is higher, lower, or correct. The computer will then guess another number until it guesses the correct secret number. The program should use a binary search to narrow its guesses to select its next guess after each attempt.

Run this program for maximum = {100, 1,000, and 10,000}, and graph the result. What can you say about the number of guesses used by the computer?

7. For the following program, translate all the branch statements (b, beqz, bnez, etc) to machine code, making sure you have correctly calculated the relative branch values.
.text
.global main
main:
la $a0, prompt jal PromptInt move$s0, $v0 BeginLoop: seq$t0, $s0, -1 bnez$t0, EndLoop

la $a0, result move$a1, $s0 jal PrintInt slti$t0, $s0, 100 beqz$t0, BigNumber
la $a0, little jal PrintString b EndIf BigNumber: la$a0, big
jal PrintString
EndIf:

la $a0, tryAgain jal PrintString la$a0 prompt
jal PromptInt
move $s0,$v0
b BeginLoop

EndLoop:
jal Exit
.data
prompt:  .asciiz "\nEneter a number (-1 to end)"
result:  .asciiz "\nYou entered "
big:     .asciiz "\nThat is a big number"
little:  .asciiz "\nThat is a little number"
tryAgain:.asciiz "\nTry again"
.include "utils.asm"

8. Explain why program code that uses PC relative addresses is relocatable, but program code that uses absolute addresses is not relocatable.
9. What is the maximum distance from the PC which can be addressed using a branch statement? Give your answer as an address distance, and as a number of statements.
10. Prompt the user for a number from 3..100, and determine the prime factors for that number. For example, 15 has prime factors 3 and 5. 60 has prime factors 2, 3, and 5. You only have to print out the prime factors, not how many times they occur (for example, in the number 60 2 occurs twice).
11. Change the prime factors program in question 10 to print out how many times a prime factor occurs in a number. For example, given the number 60 your program should print out "2,2,3, 5".
12. Prompt the user for a number n, 0 < n < 100. Print out the smallest number of coins (quarters, dimes, nickels, and pennies) which will produce n. For example, if the user enters "66", your program should print out "2 quarters, 1 dime, 1 nickel, and 1 penny".
13. Implement integer division with rounding (not truncation) in MIPS assembly. This can be done by taking the remainder from the division, and dividing the original divisor by this number. If the new quotient is greater than or equal to 1, add 1 to the original quotient. Otherwise do not change the original quotient.
14. Using only sll and srl, implement a program to check if a user input value is even or odd. The program should read a user input integer, and print out "The number is even" if the number is even, or "The number is odd", if the number is odd.