Machine Problem 5, due Apr 22
Part of
the homework for 22C:60 (CS:2630), Spring 2013
|
Background: Consider the following sequence of 4 figures:
1 2 3 4
[] [] [][] [][] [][] [][] [][]
[][] [][][][] [] [][] [] [][]
[][] [] []
[] [][] [][][][] [][] [][]
[][] [] [][] [][] [][]
[]
[][][] [][]
[][] [][] [][] [][]
[][] [] [][]
[][][] [][][][]
[][] [][]
The sequence looks a bit like the sequence from MP4, but there are some changes. Specifically, in each figure above order 1, and recursively for larger figures, there is a 1/5 probability that each of the outer subtrees will be shifted in toward the center by one "pixel" (where pixels are 2 characters wide by one character high).
So, in the order 2 figure above, the upper right quadrant was shifted inward. In the order 3 figure, the upper left order 2 figure was shifted inward, and some of the order 2 figures are also damaged. In the order 4 figure, the lower right order 3 figure is shifted inward, and of course, the order 3 and order 2 figures are subject to random damage.
The challenge here is to add random damage to the existing figures. Random, here, has a precise definition, as does the probability of 1/5.
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 g in 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 (there are plenty that are better).
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
g(s) = (16807 * s) mod (2**31 - 1)
except that all intermediate results fit in 32 bits. */
uint32_t lo = 16807 * (s & 0xFFFF);
uint32_t hi = 16807 * (s >> 16); /* 16807 = 41A7 hex */
lo = lo + ((hi & 0x7FFF) << 16);
lo = lo + (hi >> 16);
if (lo > 0x7FFFFFFF) lo = lo - 0x7FFFFFFF;
return lo;
}
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 on the Hawk.
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 useful when you are debugging. The initial value of the seed must be in the same range, but beyond that, the initial value does not matter.
A pseudoradom number
Given a random looking number r in the range from 1 to 231–2, inclusive, how do you get a random Boolean value b that will be true 1/5 of the time and false the rest of the time. There are two obvious solutions:
b = ( (r mod 5) == 0 ) b = ( r < (231–2)/5 )
Both of these approaches are approximations! They do not give exactly a probability of 1/5, but it is close enough for our purposes -- it would take millions of trials to notice the slight deviation from 1/5.
Modify any solution to MP4 so that it creates the mutated figure described here. Your solution should be well commented, well formatted and in a file called mp5.a at the time you submit it. Your answer will not necessarily look exactly like the solution given here, but it should be similar.