Machine Problem 4, due November 7

Submit the source file mp4.a (or mp4.txt if you must) for your solution using the submit command on or before the indicated date.

The Assignment

Consider the following examples of defective H-trees:

     /             /           
    /\            /\         \
     /\/           /\         \/
    / /           /           /
   /\            /
 \/  \         \/
  \/  \  /      \/
  /    \/       /
     / /      
    /\/       
      \       

These H-trees are generated using exactly the same recursive algorith as was assigned in MP3, but with one added feature: A new terminating condition has been added to the recursion: At random, with each call to the H-tree plotting routine, that routine may decide to return instead of producing any output or making any further recursive calls. For the sake of this assignment, the probability that a call will return immediately should be 1/3.

The file http://homepage.cs.uiowa.edu/~dwjones/assem/hw/mp3.txt contains a working solution to MP3. You may find this useful, or you may use your own code as a starting point.

Random Number Generation

How do you make a computer do something at random when the whole point of computer architecture is to make the machine deterministic? The answer is, you either add nondeterministic hardware -- hardware that exploits a physically random process such as radioactive decay to create randomness, or you fake it. This assignment is about faking it.

A pseudorandom number generator (PRNG) is an algorithm that produces a sequence of values s_i that are indistinguishable from truly random numbers is you don't know the algorithm. The initial value s₀ is called the seed of the series, and the function s_i+1=g(s_i) 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. The code is given in C:

uint32_t prng() {
        /* logically, this does seed = f(seed); return seed
           where f(s) = (16807 * s) mod (2**31 - 1) */
        uint32_t lo = 16807 * (seed & 0xFFFF);
        uint32_t hi = 16807 * (seed >> 16);
        lo = lo + ((hi & 0x7FFF) << 16);
        lo = lo + (hi >> 16);
	if (lo > 0x7FFFFFFF) lo = lo - 0x7FFFFFFF;
        seed = lo;
        return lo;
}

In standard C99, the type uint32_t is used to declare 32-bit unsigned integer variables and functinos. Note that the and operations are all equivalent to truncate operations (the TRUNC instruction) and the if statement is really testing the sign bit of an unsigned number.

Each call to prng() returns the next successive value of the sequence s_i. These values are all in the range from 1 to 2**31-2, and until the series repeats, the numbers appear to be random. If you use a constant seed, each run of your program will be identical -- this is useful in debugging. Just make sure the initial value is nonzero.

How do you make a 1/3 chance from a value s_i distributed at random over a huge range? Consider asking if s_i mod 3 is zero, or consider asking if s_i is less than 1/3 of the range. Both approaches work.