created 07/03/2003

Chapter 23 Programming Exercises

In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches ON, Delayed Loads ON, Mapped IO ON, Quiet OFF.

Run the programs by loading the trap handler (as explained in the chapter) and clicking SimulatorGo and then OK in the pop-up panel.

**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.

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 6 — 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.

Click here to go back to the main menu.