CS151 lecture notes, Fall 1999
Week 11, Friday

Quiz 15

Random integers
---------------

Let's work backwards.  What do we get if we take
a random number and multiply it by a, and then add b.

[0, 1] * a = [0, a]

[0, a] + b = [b, a+b]

Now round down to the nearest integer.

everything from 0 to 0.999999  gets rounded down to 0 
everything from 1 to 1.999999  gets rounded down to 1 

etc.

the problem is that if a+b occurs at all, then it will
happen very rarely compared to the other values.

Thus, the real range of outcomes is from [b, a+b-1]

Now, if we know we want the range to be low to high
(including both, and with all values equally likely),
then we just substitute

     low = b
     high = a+b-1

And solve for a and b (the things we multiply by and add)

    a = high-low+1
    b = low

Thus,
	random * (high-low+1) + low

Here's a good example of BAD !*&%!& DOCUMENTATION

-----

public static synchronized double random()

Returns a random number between 0.0 and 1.0. Random number generators
are often referred to as pseudorandom number generators because the
numbers produced tend to repeat themselves after a period of time.

Returns: a pseudorandom double between 0.0 and 1.0. 

-----

Unfortunately, both possibly interpretations are feasible, hence the
loop in my solution:

  public static int randInt (int low, int high) {
    while (true) {
      int x = (int)(Math.random() * (high-low+1) + low);
      if (x >= low && x <= high) return x;
    } 
  }

This loop will rarely, if ever loop, but it does guarantee
that the return value will be in range.

How would you convince yourself that this really works?

    (generate a bunch of numbers and build a histogram)


Cards and aliasing
------------------

Arrays can share objects.

The arrays contain references to the same objects -- aliasing.

For things like Cards, which are immutable, aliasing is less
dangerous.

Homework 11 involves this kind of aliasing.


Iterative version of bisection search
-------------------------------------

The "moving goal post" pattern

Start with low=0 and high=length-1

Calculate a mid point

Compare the target to the value at the mid point.

If equal, stop.

If less, then replace the upper goal post.

If more, replace then lower goal post.

Repeat while high >= low.


Analysis of bisection search
----------------------------

How many comparisons do you have to do in a linear search?

    One for each element of the array.
    If array size is n, there are n comparisons.

How many comparisons do you have to do in a bisection search?

    One each time we divide the array in half.

    How many times can we divide the array (size n) before
    we get to one?
    
    How many times do we have to double 1 before we get to n?

    What power of 2 is n?

    What mathematical function answers that question?