Problem 32

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Problem 16 redux

Due: February 15
Points: 2

Here was problem 16:

Write a program in Java, C++, or python3 that takes a single integer n as a command-line argument and produces a stream of 500 random numbers, one per line, in the range of 1 up to n.

Your program should produce these numbers by reading data from the /dev/random device in Linux. Take care! This "file" produces random bytes of data, not characters. So if you try to read from it in the regular ways, it will not work the way you expect. Instead you have to use "raw" or "binary" input methods such as read in C++.

For the full points, you need to handle n as large as \(2^{31}-1\).

The solutions you came up with were riddled with bias, meaning some numbers more likely than others. To remove this bias, you need to do something like the following:

def randomConvert(X, m1, m2):
    '''Given an integer X randomly chosen modulo m1, returns another
       integer randomly chosen modulo m2, or "FAIL".
       Note that m1 must be larger than m2!
    c = floor(m1/m2) * m2
    # c is the largest multiple of m2 that is less than m1.
    if X >= c:
        return "FAIL"
        return X % m2

Re-solve problem 16 to account for this and to actually produce unbiased random numbers from 1 up to n. (NOTE: the randomConvert function here gives numbers from 0 up to m2.)

Submit your program according to the instructions on the submit page.