Computer Organization and Design
(Textbook. Click for information.)
 CS 2733/2731
 Computer Organization II
 Fall 2004
 Recitation 3
 Simple array
    Week 3: Sep 8-10
 Due (on time): 2004-09-15  23:59:59
 Due (late):        2004-09-19  23:59:59

Recitation 3 must be submitted following directions at: submissions on or before
  • 2004-09-15  23:59:59 (that's Wednesday, 15 September 2004, 11:59:59 pm) for full credit.
  • 2004-09-19  23:59:59 (that's Sunday, 19 September 2004, 11:59:59 pm) for 75% credit.

Outline: This recitation has you write two MIPS programs that will print the so-called Fibonacci numbers: the sequence 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...,
where each successive number is the sum of the two previous numbers. In more mathematical terms, the sequence

fn, for n >= 0

is defined by the formulas

f0 = 0, f1 = 1, and fn = fn-1 + fn-2.

First Program: The first program is to be simple MIPS code that prints the first 16 Fibonacci numbers on a line, with a space between each one. You should model the program after the following C or Java programs, which are essentially the same and have the same output. Like the programs below, your MIPS program must consist of a single loop, with output statements to print an integer and a blank inside the loop, and to print a newline after the loop terminates.

First Program (C) First Program (Java)
/* fibonacci.c: simple Fibonacci numbers */
#include <stdio.h>
int main() {
   int F0, F1, F2;
   int i, last;
   F0 = 0; F1 = 1;
   i = 0; last = 16;
   do {
      F2 = F0 + F1;
      printf("%i", F0);
      printf(" ");
      F0 = F1;
      F1 = F2;
      i = i + 1;
   } while (i < last);
   printf("\n");
}

// Fibonacci.java: simple Fibonacci numbers
public class Fibonacci {
   public static void main (String[] args) {
      int F0, F1, F2;
      int i, last;
      F0 = 0; F1 = 1;
      i = 0; last = 16;
      do {
         F2 = F0 + F1;
         System.out.print(F0);
         System.out.print(" ");
         F0 = F1;
         F1 = F2;
         i = i + 1;
      } while (i < last);
      System.out.print("\n");
   }
}
C Run and Output Java Run and Output
% cc -o fibonacci fibonacci.c
% fibonacci
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

% javac Fibonacci.java
% java Fibonacci
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Second Program: Modify the first program into a second (or write the second from scratch) that allocates space for an integer array F of size 16 and stores the first 16 Fibonacci numbers into this array. Then it should print the numbers in this array, on one line with a blank between each one, just as before.

This second program should have two separate loops, the first to use the array to help calculate the numbers. In this case the calculation is much simpler, and it is easier to see that it is correct. However, in MIPS there is the additional complexity of coping with the array. You must use the array in this way as illustrated below.

Then the second loop should print the numbers from the array.

You should realize that pieces of these programs have already been supplied and discussed in class: for example, printing an array.

The second program can be based on the following C or Java programs, which again are essentially the same and have the same output as before.

Second Program (C) Second Program (Java)
/* fib_array.c: Fib nums in an array */
#include <stdio.h>
int main() {
   int F[16];
   int i, last;
   F[0] = 0; F[1] = 1;
   i = 2; last = 16;
   do {
      F[i] = F[i-1] + F[i-2];
      i = i + 1;
   } while (i < last);
   i = 0;
   do {
      printf("%i", F[i]);
      printf(" ");
      i = i + 1;
   } while (i < last);
   printf("\n");
}

// FibArray.java: Fib nums in an array
public class FibArray {
   public static void main(String[] args) {
      int[] F = new int[16];
      int i, last;
      F[0] = 0; F[1] = 1;
      i = 2; last = 16;
      do {
         F[i] = F[i-1] + F[i-2];
         i = i + 1;
      } while (i < last);
      i = 0;
      do {
         System.out.print(F[i]);
         System.out.print(" ");
         i = i + 1;
      } while (i < last);
      System.out.print("\n");
   }
}
C Run and Output Java Run and Output
% cc -o fib_array fib_array.c
% fib_array
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

% javac FibArray.java
% java FibArray
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate number 1-4.

  Contents of submission for Recitation 3:

Last Name, First Name; Course Number; Recitation Number (3).

  1. MIPS source code for the first program.

  2. Log of a run of the first program, using spim.

  3. MIPS source code for the second program.

  4. Log of a run of the second program, using spim.

Revision date: 2004-06-27. (Please use ISO 8601, the International Standard.)