created 06/20/2003; small edits: 07/20/2015

# Chapter 15 Programming Exercises

For these programming exercises, use only those instructions that have been discussed so far in these notes:

 add lw sll addi mfhi sra addiu mflo srl addu mult sub and multu subu andi nor sw div or xor divu ori xori lui

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

Run the programs by setting the value of the PC to 0x400000 and then single stepping (pushing F10) or by multiple stepping (push F11 and enter a number of steps). Observing the results in the SPIM window.

## Exercise 1

Modify exercise 1 of the previous chapter so that the value `x` is in memory. Store the value of the polynomial back to memory. The program will be similar to poly.asm from this chapter. Evaluate the polynomial:

```3x2 + 5x - 12
```

Use symbolic addresses `x` and `poly`. Assume that the value in `x` is small enough so that all results fit into 32 bits. Since load delays are turned on in SPIM be careful what instructions are placed in the load delay slot.

Verify that the program works by using several initial values for `x`. Use `x = 0` and `x = 1` to start since this will make debugging easy. Then try some other values, such as `x = 10` and `x = -1`.

Optional: write the program following the hardware rule that two or more instructions must follow a `mflo` instruction before another `mult` instruction. Try to put useful instructions in the two slots that follow the `mflo`.

## Exercise 2

Evaluate the expression:

```17xy - 12x - 6y + 12
```

Use symbolic addresses `x`, `y`, and `answer`. Assume that the values are small enough so that all results fit into 32 bits. Since load delays are turned on in SPIM be careful what instructions are placed in the load delay slot.

Verify that the program works by using several initial values for `x` and `y`. Use `x=0, y=1` and `x=1, y=0` to start since this will make debugging easy. Then try some other values. As an option, follow the precaution for multiplication, as above.

## *Exercise 3 — Horner's Method

Evaluate the polynomial:

```6x3 - 3x2 + 7x + 2
```

Get the value for `x` from symbolic addresses `x`. Store the result at symbolic address `poly`. Assume that the values are small enough so that all results fit into 32 bits. Since load delays are turned on in SPIM be careful what instructions are placed in the load delay slot.

Evaluate the polynomial by using Horner's Method. This is a way of building up values until the final value is reached. First, pick a register, say \$7, to act as an accumulator. The accumulator will hold the value at each step. Use other registers to help build up the value at each step.

First, put the coefficient of the first term into the accumulator:

```6
```

Next, multiply that value by x:

```6x
```

Add the coefficient of the next term:

```6x - 3
```

Next, multiply that sum by x:

```6x2 - 3x
```

Add the coefficient of the next term:

```6x2 - 3x + 7
```

Next, multiply that sum by x:

```6x3 - 3x2 + 7x
```

Finally, add the coefficient of the last term:

```6x3 - 3x2 + 7x + 2
```

Evaluating the polynomial in this way reduces the number of steps (and the amount of code). If you want to save time, write and debug each step before moving on to the next. When you reach the final step you should have a working, debugged program.

Verify that the program works by using several initial values for `x`. Use `x=1` and `x=-1` to start since this will make debugging easy. Then try some other values. As an option, follow the precaution for multiplication.

## **Exercise 4 — More Horner's Method

Evaluate the following polynomial using Horner's method:

```ax3 + bx2 + cx + d
```

Now the values for the coefficients `a, b, c, d` as well as for `x` come from the `.data` section of memory:

```       .data
x:     .word    1
a:     .word   -3
b:     .word    3
c:     .word    9
d:     .word  -24
```

Load a base register with the address of the first byte of the `.data` section. Calculate (by hand) the displacement needed for each of the values in memory and use it with a `lw` instruction to get values from memory. In a later chapter you will find a much more convenient way to load and store values using symbolic addresses. But don't do this now.