Assignment 9, due Mar 30
Part of
the homework for 22C:60 (CS:2630), Spring 2012
|
On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!
int times( int a, int b ) {
if (a != 0) { /* nontrivial case */
if (a & 1) { /* a is odd */
a = times( a >> 1, b << 1 ) + b;
} else { /* a is even */
a = times( a >> 1, b << 1 );
}
}
return a;
}
A Problem: Translate this to a SMAL Hawk subroutine, preserving as much of the control structure of the original as possible, and documenting it with comments that clearly reflect the original code wherever that is possible. You will be graded on how easy your code is to read as well as on its correctness. (0.6 points)
If p is the handle for a point object (that is, a pointer to the object), the method call p.setpoint(1,2,'o') sets the attributes p.x to 1, p.y to 2, p.ch to 'o'.
the method call p.plotpoint() causes p.ch to be plotted on the screen at coordinates p.x, p.y.
Assume that the point class is not polymorphic, so there is only one implementation of each method, and therefore, setpoint() and pointplot() are implemented, in assembly code, as simple subroutines.
a) (0.6 points) Given that R3 is the address of the point object p, you want to be able to write, for example, LOAD R4,R3,X in order to load R4 with the contents of the p.x. Give appropriate SMAL definitions of X, Y, CH, and POINTSIZE, suitable for inclusion in the header file point.h that defines the SMAL interface to the point class.
b) Suppose you needed a temporary object of class point as a local variable in a subroutine. Prior to discovering you needed this, your activaiton record declarations looked like this:
;RETAD = 0 COUNTER = 4 ARSIZE = 8
Modify this code so that the activation record includes a field named MYPOINT of size POINTSIZE (as defined in part a). Note that the storage for the object should be directly included in the activation redord, without any use of handles, pointers or other complexity. (0.6 points)
c) Assume all of the definitions from parts a, b and c, and write code for inclusion in your subroutine that is the SMAL Hawk equivalent of mypoint.setpoint(1,2,'o'). (0.6 points)
d) Write code that belongs inside point.a for the SMAL Hawk subroutine that implements the setpoint method. You may assume that the appropriate definitions from point.h are available. (0.6 points)
Note that all of the above questions assume that you have read Chapter 10 of the notes.
Modify some solution to Machine Problem 4 so that the gasket it plots is missing random elements. In plotting each gasket, each sub-gaskets should be omitted with a probability of 1/8. So, for example, where MP4 would have plotted these gaskets:
[] [][][] [][][][][][][][][]
[] [] [] [][] [][] []
[][][] [][][][][][][][][]
[][][] [][][]
[] [] [] []
[][][] [][][]
[][][][][][][][][]
[] [][] [][] []
[][][][][][][][][]
your solution to MP5 might output the following:
[] [][] [] [][][] [][]
[] [] [] [][] [][] []
[][][] [][][][][][][][][]
[][][] [][][]
[] [] []
[][][] [][][]
[][] [][][]
[] [] []
[][] [][][]
The decision to randomly omit one of the recursive calls should be made based on the sequence of values returned by a pseudo-random number generator.
As discussed in class on March 28, a pseudoradom number generator or PRNG is an algorithm that produces a sequence of values si that are indistinguishable from truly random numbers if you don't know the algorithm. The initial value s0 is called the seed of the series, and the function si+1=g(si) is called the pseudorandom number generator. If you know the seed and the generator, you can predict the series, but if you are not told these, the series should be indistinguishable from random.
Here is a popular pseudorangom number generator for use on 32-bit computers. It has been known as the minimal-standard pseudorandom number generator since the late 1998 when Stephen Park and Keith Miller declared that there was never any excuse for using a generator worse than this one.
g(s) = (16807 × s) mod (231 - 1)
The above generator function is certainly not random. Note, however, that the intermediate result after multiplication before the mod operation requires more than 32 bits. The following C code (not too different from Java) solves this problem:
uint32_t g( uint32_t s ) {
/* logically, this code is exactly equivalent to
where g(s) = (16807 * s) mod (2**31 - 1) */
uint32_t lo = 16807 * (s & 0xFFFF);
uint32_t hi = 16807 * (s >> 16);
lo = lo + ((hi & 0x7FFF) << 16);
lo = lo + (hi >> 16);
if (lo > 0x7FFFFFFF) lo = lo - 0x7FFFFFFF;
return lo;
}
The above code computes exactly the same result as the original version of the minimal standard PRNG, except that it never needs more than 32 bits for any intermediate result. The data type uint32_t is used to declare 32-bit unsigned integer variables and functinons in C99. Note that all of the logical and operations given in this code are equivalent to TRUNC instructions.
The successive values in the pseudo-random sequence s0, s1, s2, s3, ... produced by this generator are all in the range from 1 to 231-2, inclusive. If you start with the same seed, you will always get the same sequence. This is important when you are debugging.
How do you get a 1/8 chance of dropping a value, using this sequence? For any particular si, the value si&7 will be zero exactly 1/8 of the time.