For this exam, you may use your textbook, your notes and assignments, your brain, and divine guidance if available. You may not use other books, other people, or Internet resources. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else about the exam.

Submit your answers on paper. For the PDP8 code in problem 1, submit your .pal file using HSP.

1. (12 points) Write a PDP8/E subroutine that takes the non-negative integer N (stored in the AC at the time the subroutine is called) and returns (in the AC) the largest non-negative integer whose square is less than or equal to N. In particular, if N is a perfect square, the result will be the square-root of N.

   Your goal here is not an efficient algorithm (so, in particular, you should not use your multiplication code from assignment 2). Your goal is to write a correct subroutine that takes up as few words of memory as possible. Your score will be based on correctness (8 points) and brevity (4 points).
   
   

2. (12 points) The table below shows the execution times for all of the PDP8/E instructions (not including op-code 6).

   
   Execution times in micro-seconds for PDP8/E instructions
   --------------------------------------------------------
                            Addressing mode     
                 ------------------------------------------
   Instruction                            Indirect with
      Type       Direct      Indirect     auto-increment
   --------------------------------------------------------
   AND            2.6          3.8             4.0
   TAD            2.6          3.8             4.0
   ISZ            2.6          3.8             4.0
   DCA            2.6          3.8             4.0
   JMS            2.6          3.8             4.0
   JMP            1.2          2.4             2.6
   
   Opcode 7          1.2 (addressing mode irrelevant)
   --------------------------------------------------------
   

   Answer the following questions:

   • Does the notion of CPI make sense in the context of the PDP8/E? Why or why not?
   • Even if you said CPI does not make sense, you can still use the timing table below to compute the native MIPS for the PDP8/E if you first make some assumptions. What sort of assumptions do you need to make?
   • Using assumptions of the kind you described in the previous question, compute the native MIPS for the PDP8/E. Make sure to explain exactly what your assumptions are.
   • In the Chapter 2 exercises, the fictional but more-or-less modern machines you considered had native MIPS ratings around 400-600. Based on these ratings, how much faster than the PDP8/E are modern machines? Does using native MIPS for comparison misrepresent the relative performance of the PDP8/E and modern machines? In whose favor?
   
   
   
3. (7 points) Consider the following program:

   
   	#include	<iostream>
   
   	int factorial( int N );
   
   	int main()
   	{
   		for( int N=1; N <= 40; N++ )
   			cout << N << "! = " << factorial( N ) << endl;
   
   		return( 0 );
   	}
   
   	int factorial( int N )
   	{
   		int product = 1;
   		for( int i=2; i <= N; i++ )
   			product = product * i;
   
   		return( product );
   	}
   

   When you run this code, you get correct values of N! for a while, and then you start to get incorrect values. Answer the following questions:

   • For what value of N do you first get an incorrect value for N factorial? Why? Does the answer you get make any kind of sense, or is it just a random value?
   • For what value of N does N! first get reported as 0? Why do the zeros start at this particular value of N?
   
   
   
4. (6 points) Consider the following program:

   
   	#include	<iostream>
   
   	int main()
   	{
   		int		m = 100;
   		int		a[4];
   		int		n = 200;
   		int		i;
   
   		for( i=-1; i <= 4; i++ )
   			a[i] = i;
   
   		cout << "m = " << m << endl;
   		cout << "n = " << n << endl;
   
   		for( i=0; i < 4; i++ )
   			cout << "a[" << i << "] = " << a[i] << endl;
   
   		return( 0 );
   	}
   

   Answer the following questions, which assume you are compiling and running this program on one of the Math/CS Linux machines (I tried it on codd.mathcs.carleton.edu).

   • What happens to the variables m and n, and why?
   • How does the order in which local variables are declared affect their locations in memory when the program runs?
   • If I change the first for-loop to "for( i=-1; i <= 6; i++ )", the program runs as before, but then suffers a segmentation fault at the very end. Why?
   
   
   
5. (2 points) Please direct me to an interesting Web site.
   
   
6. (8 points) Write an algebraic expression describing the following boolean function of three variables. Then simplify the expression as much as you can, and draw a digital logic circuit that implements the function based on your simplified formula.

   
   	  A     B     C   ||  f(A,B,C)
   	===============================
   	  0     0     0   ||     0 
   	  0     0     1   ||     1 
   	  0     1     0   ||     1 
   	  0     1     1   ||     1 
   	  1     0     0   ||     0 
   	  1     0     1   ||     1 
   	  1     1     0   ||     1 
   	  1     1     1   ||     0