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.

Combining two PRNGs

Due: February 1
Points: 3

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!)