Machine Problem 2, due Oct 8

Part of the assignments for 22C:60, Fall 2004
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated, and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

  1. A Recursive Algorithm

    Here is a recursive algorithm that strongly resembles the Fibonacci series, except for the use of the array S, which we assume to be a global constant. 

    	unsigned int f(unsigned int i)
	{
		if (S[i] == 0) return i;
		return f(S[i]) + f(S[i-1]);
	}
    If the array S is {0,0,1,2,3,4,5,6 ... }, this is the Fibonacci series. If S[i] is i for nonzero i, the recursion never terminates.

  2. A test program 
    	main()
	{
		unsigned int i;
		dspini();
		for (i = 0; i < 16; i++) {
			dspdecu( i, 1 );
			dspch( ':' );
			dspdecu( f(i), 1 );
			dspch( ' ' );
		}
	}

  3. Assembly Language

    Convert all this to assembly language. Start by testing it with the straight Fibonacci series, and then modify your code so it uses the constant array of characters S, declared as follows: 

    	S: B 0,0,1,2,3,4,5,6,7,8,9,10, ...

    The output should still be the Fibonacci series. Finally, change the array definition to: 

    	S: B 0,0,1,2,2,4,3,6,4,8,5,10, ...

    Here, if i is even, S[i] is i/2, while if i is odd, S[i] is i-1.

  4. Assembly Language

    To submit a solution to MP2, you must use a departmental linux machine and run the submit command. See