created 07/03/2003


Chapter 23 Programming Exercises


In the Settings menu of SPIM set Bare Machine OFF, Accept Pseudo Instructions ON, Enable Branch Delays ON, Enable Load Delays ON, Enable Mapped IO OFF, Load Exception Handler ON.


**Exercise 1 — Prime Number Tester

Write a program that asks the user for a positive integer. The program then tests if the integer is prime and writes out its result. (See exercise 4 in chapter 19.)

A number is prime if it cannot be divided evenly by any number other than 1 and itself. So you will need a counting loop that starts at two and divides the number for each value of the loop counter until the number is divided evenly or the limit is reached.

For the upper limit of the loop use the number divided by two. (A better upper limit would be the square root of the number, see below.)

Click here to go back to the main menu.


**Exercise 2 — Integer Square Root

Write a program that asks the user for an integer and then computes the square root of that integer. Use only integer arithmetic. The integer square root of N is the positive integer X who's square is exactly N, or who's square is less than N but as close to N as possible. Examples:

iSqrt(25) == 5 since 5*5 == 25.
iSqrt(29) == 5 since 5*5 == 25 and 6*6 == 36, so 6 is too big.
iSqrt(60) == 8 since 8*8 == 56 and 9*9 == 81, so 9 is too big.
iSqrt(0) == 0,  iSqrt(1) == 1, iSqrt(2) == 1.

The integer square root is undefined for negative integers.

There are various fast ways of computing the integer square root (Newton's method is one). But for this program, use a counting loop that generates integers 0, 1, 2, 3, ... and their squares 0, 1, 4, 9, ... As soon as the square of an integer exceeds N, then the previous integer is the integer square root of N.

Click here to go back to the main menu.


***Exercise 3 — Lottery Odds

To win a lottery you must correctly pick K out of N numbers. For example, you might need to pick 6 numbers out of the numbers 1 to 50. There are

(50 * 49 * 48 * 47 * 46 * 45 )/(1 * 2 * 3 * 4 * 5 * 6)

ways of picking 6 out of 50 numbers. So your odds of winning are 1 in that number of ways. If you must pick 6 out of 50 numbers, your odds of winning are 1 in 15,890,700. In general, there are

N * (N-1) * (N-2) * (N-3) * (N-4) * ... * (N-K+1)
-------------------------------------------------
       1  *   2   *   3   *  4    * ... * K

ways of picking K out of N numbers.

Write a program that asks the user for integers N and K and writes out the odds of winning such a lottery.

Test that the program works for reasonable values of N and K. For many values of N and K, 32-bit arithmetic will overflow. For this program, just allow that to happen.

Click here to go back to the main menu.

   * == easy program
  ** == moderately easy program
 *** == harder program
**** == project

End of Exercises