Problem 26

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

You are given two PRNGs, *A* and *B*. You don't know how either one works internally, but you know that they both share the following properties in common:

- Both PRNGs are seeded with a value from 0 up to 255.
- Both PRNGs output numbers from 0 up to 255.
- Both PRNGs have period length equal to \(2^{32}\).

Your task is to come up with a way of combining these two PRNGs to make a new PRNG that is even better than these two. Your combined PRNG should behave the same as *A* and *B* in that it is seeded with a single value from 0 up to 255, and it should produce numbers in the range of 0 up to 255. Here are the rules:

- Your PRNG may sample any amount of random numbers from
*A*and*B*, and do any amount of computation with them, to produce each output from your PRNG. - Your PRNG may seed sequences
*A*and*B*to re-start them at any time. (Hint: you should probably start by seeding them!) - Your PRNG may
*not*store any information between outputting values. This is to prevent you from just making a new PRNG and forgetting about*A*and*B*entirely.

Describe your method clearly and simply. Then analyze it and tell me what the period length of your new PRNG would (hopefully) be. (Hint: what is the maximum period length that is possible in this situation? You can achieve it!)