Assignment 9, due Oct 31

Part of the homework for 22C:60, Fall 2008
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Remember to write your name on what you turn in! Homework must be turned in on paper and in class!

Homework

  1. Background: The minimal standard pseudorandom number generator is a decent way to generate a sequence of numbers on a computer that appears to be random. The sequence N is generated as follows: Given ni a value from 1 to 2,147,483,646 (inclusive), this generates ni+1, another number in the same range, using the following relationship:
    ni+1 = 16,807 ni mod 2,147,483,647

    This generator requires a multiply operation that generates a 64-bit product of two 32-bit operands. To avoid this, a bit of algebra lets us rewrite it as:

    ni+1 = 16,807(ni mod 127,773) - 2,836(ni / 127,773);
    if (ni+1 < 0) then ni+1 = ni+1 + 2,147,483,647

    The initial value n0 is called the seed.

    a) Give reasonably efficient Hawk code to multiply R3 by 127,773. (Reasonably efficient code need not be optimal, but shouldn't be as bad as calling a canned subroutine to do the job.) (0.5 points)

    b) What is the reciprocal of 127,773? Express the answer as a binary fraction. (0.5 points)

    c) Give reasonably efficient code to divide R3 by 127,773, giving both the quotient and remainder. If your code depends on the code from part a, you need not copy that code, just insert a note saying where that code goes. (0.5 points)

  2. A problem: Consider an n'th order H-tree made out of underline characters and vertical bars.

    a) How wide is it, in characters? (0.1 points)
    b) How high is it, in characters? (0.1 points)
    c) How many endpoints does it have? (0.1 points)
    d) How tall is its longest vertical bar, in characters? (0.1 points)
    e) How wide is its longest horizontal bar, in characters? (0.1 points)

  3. Background: Consider class stack with the following methods:

    We could represent a stack by a record containing a stack pointer and an array of integers.

    Problem: Write well-commented SMAL Hawk code to describe the data structure of a stack record and the init routine. You may assume that the size of a capacity of a stack is given by the assembly-time constant STACKCAPACITY. Note that your initializer should not actually allocate storage. Assume that the caller is responsible for allocation prior to calling the initializer. (1.0 points)