Assignment 8, due Oct 27

Machine Problem Due Nov 5

Here is a little program that fills the display screen with random snow:

	main()
	{
		struct {
			int x; /* screen width */
			int y; /* screen height */
		} size = dspini();
		int x, y;
		setseed(1);
		do {
			x = random() % size.x;
			y = random() % size.y;
			dspat(x,y);
			dspch('*');
		}
	}

This program requires a source of random numbers! It also demonstrates how hard it is to write syntactically valid C to deal with a function like dspini() that returns 2 integers.

Random numbers pose a problem on computers, because computers are supposed to be deterministic machines. The best we can usually do is create functions that return numbers that appear to be random. Such functions are called pseudorandom number generators. These are generally hard to write; here is Park and Miller's minimal standard random number generator:

	#define A 16807       /* = 0x41A7 */
	#define M 2147483647  /* = 0x7FFFFFFF */
	#define Q M/A         /* = 127773 = 0x1F31D */
	#define R M%A         /* = 2836 = 0xB14 */

        int seed; /* the value used to create successive random numbers */
                  /* at all times, (0 < seed < M) */

	setseed( int i )
	/* sets the seed for random number generation */
	{
		if ((i < 1) || (i >= M)) error();
		seed = i;
	}

	int random()
	/* advance the seed through the sequence of random numbers */
	{
		int t = A * (seed % Q) - R * (seed / Q);
		if (t > 0) {
			seed = t;
		} else {
			seed = t + M;
		}
		/* seed = (A * seed) % M is equivalent! */
		return seed;
	}

Do this in Hawk machine language! This code involves lots of multiplicaton and division, and full credit will be offered only to those who:

• make some effort to optimize multiplication by constants or
• make some effort to 32*32=64 multiplicaiton, a feature missing from the Hawk monitor.

Homework Due Oct 27

Do Chapter 9 Problems d, f, g₁, g₂, k, v, y.

And, answer the following in preparation for doing the machine problem: Why was the random() function above written with the long complicated body instead of the short sweet body that was commented out at the end of the function? What makes it possible that the latter form would be a perfectly reasonable solution on the Hawk? Hint: Consider the maximum possible value of A*seed.