Due Saturday, March 7, by 11:59pm (Midnight).
All programs should be submitted through Blackboard (Course Materials > HW2).
Each program should start with a comment that contains your name and a short program description, for example:
/*
Author: Your Name
Description: HW 1. Task 1. Printing a rectangle
.. you may add a more detailed description if it's necessary ..
*/
If a program does not do what it’s supposed to do (e.g. there are some bugs, it behaves differently, or maybe even does not compile), then its “incomplete” status must be clearly mentioned in the comment to the program. In this case, please briefly describe what is implemented, and what is not.
In the video Random vs Pseudo-random, we learned about von Neumann’s algorithm for generating pseudo-random numbers:
The algorithm is called the Middle square method, and it generates a sequence of pseudo-random n-digit numbers. In this task, we will be generating 4-digit pseudo-random numbers.
To setup the generator, a 4-digit number must chosen as a seed.
We assign this value to a global variable, let’s call it state, it will store the state of the generator.
To generate the next pseudo-random number in the sequence, the value of the variable state is squared,
producing an 8-digit integer (if it’s shorter, we assume that it’s padded with leading zeroes),
and we take its middle 4 digits! This is it.
This new value is returned from the procedure, and state is also updated with this new number.
Write two functions that implement the Middle square PRNG:
// set the seed (the seed must be a 4-digit number)
void seed(int);
// generate the next pseudo-random number
int gen();
Also write a main function that tests your pseudo-random number generator.
Any pseudo-random sequence eventually starts repeating itself. No matter with what seed you start, the sequence will eventually converge to one of the cycles.
Read a discussion of this issue in the Wikipedia article.
Using arrays you can keep track of the numbers visited by the PRNG and identify such cycles. For this task, please write a program that identifies all cycles of von Neumann’s PRNG.
It turns out that there are 5 cycles of length one.
Examples:
0 -> 0 -> 0 -> ...
100 -> 100 -> 100 -> ...
3792 -> 3792 -> ...
And 3 cycles of length four.
Example:
540 -> 2916 -> 5030 -> 3009 -> 540
There are no cycles other than these eight. And in particular, there are no cycles longer than length four.
Your program should find all of these eight cycles and print them out. Try to come up with an algorithm that prints all cycles exactly once. In other words, when a cycles is found, you can remember that, and don’t print the same cycle again.