created 06/29/2003; prime and phi added 05/14/2016

# Chapter 19 Programming Exercises

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

 add div mflo slt, slti addi divu mult sltu, sltiu addiu j multu sra addu lb nor srl and lbu or sub andi lh ori subu beq lhu sb sw bgez lui sh xor bltz lw sll xori bne mfhi

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

Run programs by single stepping (pushing F10) or by clicking run and allowing control to go beyond the program. Implement while loops by branching to a no-op (sll \$0,\$0,0) at the end of the loop when the loop finishes.

## *Exercise 1 — Sequential Memory Locations

Write a program that stores the number 0 in the first four bytes of the `.data` section, then stores the number 1 in the next four bytes, then stores the number 2 in the four bytes after that and so on. Do this for numbers 0 through 24.

Of course you will do this in a counting loop. The address in the data section is contained in a base register. Increment the base register each time a number is stored.

The data section of your program should look like

```
.data
array:   .space    100
```

## ***Exercise 2 — Perfect Number Verifier

A perfect number is an integer whose integer divisors sum up to the number. For example, 6 is perfect because 6 is divided by 1, 2, and 3 and 6 = 1 + 2 + 3. Other perfect numbers are 28 and 496.

Write a program that determines if an integer stored in memory is a perfect number. Set a location in memory to 1 if the number is perfect, to 0 if not.

```            .data
N:          .word      496
isperfect:  .word      0
```

It would be enormously helpful to first do this by hand with a couple of examples. Then draw a flowchart. Check the flowchart by following it with a few examples. Then write the program.

## ****Exercise 3 — Perfect Number Searcher

This exercise continues exercise 2.

Write a program that searches for perfect numbers. It has an outer loop that counts upward from two to some limit. Each number is tested (as above) to see if it is a perfect number. If it is a perfect number it is stored at a memory location. Store perfect numbers at successive full-word memory locations. Look at exercise 1 for a way to do this.

Again, to save time and effort, create a flowchart first.

## **Exercise 4 — Prime Number Tester

Write a program that determines if an integer is prime. An integer is prime if it cannot be divided by any positive integer other than one and itself. The integer N to be tested will be in memory. Set the location `isprime` to 1 if N is prime, 0 otherwise.

```          .data
N:        .word     223
isprime:  .word      0
```

To determine if N is prime, try to divide it with trial divisors from 2 up to N/2. If one of them divides N without a remainder, then N is not prime. You only have to try trial divisors up to N/2 because if N = trial*X, then trial = N/X and the only integer X less than 2 is 1.

Write a program that computes the greatest common divisor (GCD) of two integers. The two integers and the GCD will be in memory.

## ***Exercise 5 — Greatest Common Divisor

Write a program that computes the greatest common divisor (GCD) of two integers. The two integers and the GCD will be in memory.

```        .data
N:      .word     21
M  :    .word     14
GCD:    .word      0
```

The GCD of two integers is the largest integer that divides them both with a remainder of zero.

• GCD(21,14) = 7
• GCD(14,21) = 7
• GCD(27,36) = 9
• GCD(25,50) = 25
• GCD(19,36) = 1
• GCD(12,55) = 1

Notice that `GCD(X,Y) = GCD(Y,x)`. If the GCD of two integers is one, then the two integers are relatively prime. Two integers might be relatively prime without either one of them being prime.

If two integers have a common divisor, the difference of the two integers has the same divisor. To find the common divisor, keep subtracting one integer from the other until a common value is reached. Why is this? Say x and y have a common divisor, say d.

• Then x = md and y = nd
• Then (x – y) = md – nd = (m – n)d = kd
• So the difference kd has the same divisor d

```get N
get M

while (N != M)
if ( N > M )
N = N - M;
else
M = M - N;

GCD =  N;
```

Load N and M integer registers and implement the algorithm using registers. There is no need to change the N and M in memory. When the loop finishes, store the resulting GCD into memory.

## ****Exercise 6 — Euler Phi Function

Write a program that computes the Euler phi function. The phi function is important in cryptography and internet security.

The phi function of an integer N is the number of positive integers less than N that do not share a common factor greater than one with N. Another way to say this is that phi( N ) is the number of positive integers less than N that are relatively prime to N.

Two integers share a common factor if there is an integer greater than one that divides them both with no remainder. For example, 14 and 21 share a common factor of 7. Also, 7 and 21 share a common factor of 7. But 5 and 21 do not have a common factor.

Two integers have a factor in common if they have greatest commmon divisor greater than one. The greatest common divisor of 14 and 21 is 7. The greatest common divisior of 5 and 21 is 1.

So the phi function of N is the number of positive integers x less than N for which `gcd(N,x) = 1`.

Write a program that computes phi(N) for an integer N in the data section. Store the result back into the data section

```        .data
N:      .word     21
phi:    .word      0
```

The logic of your program could be:

```phi = 0;
trial = 1;
while ( trial < N)
{
if ( gcd(N,trial) == 1 ) phi++;
}
```