Quite often we use programming for conducting experiments of some kind. And often we may want to use a sequence of numbers which are seemingly independent and unpredictable, but at the same time can be easily reproduced.
For example - if we are writing an application which allows user to play a kind of Solitaire with cards we need: - have an ability to "shuffle" virtual deck of card before dealing them; - at the same time allow user to play later again with the same "shuffling".
Most convenient way is to use reproduceable sequence of pseudo-random numbers, defined by one or more (but anyway small amount) of values which we can store to reproduce the sequence later (or send these values to other person so he can reproduce our experiment etc.)
Few more examples of using random numbers in programming are described in the dedicated article.
Simple method proposed, perhaps at medieval times is as following:
- take any 4-digit value (like 5234);
- square it (like 5234 * 5234 = 27394756);
- take the middle four digits of the result (it will give 3947 in example above) as a next value.
Depending on initial number this method can produce surprisingly unpredictable values, which is nice. However, many
choices lead to fast end in some kind of loop and the longest chain without repetition contains only about 111
members.
Surely, we can use 6-digit values instead - longest chain in this case is about 1700 elements long (or 8-digit
values, or even bigger - but they are not very handy). Or we can use other numeral system (11-based, for example).
To reproduce the sequence we need to remember initial value, number of digits (which should be even and can't vary much) and the base of numeral system.
Here is the task Neumann's Random Generator about calculating length of the sequences generated by this method before they came to repetition.
Better and still simple method is based on the simple formula, giving the next value Xnext by the current Xcur:
Xnext = (A * Xcur + C) % M
Since result is taken by modulo M, all members are in range 0 ... M - 1. And since next number depends only on
current one, period could not be greater than M.
However, not all choices of constants yield the sequence with full period. The following conditions must hold for good choice:
C and M have no common divisors other than 1.A - 1 is divisible by all prime factors of M.M is a multiple of 4 then A - 1 should be too.These rules though look whimsical give us a simple idea of chosing constants:
- let M = 2 ^ K with some integer K >= 2;
- then A = 4 * J + 1 with some integer J >= 1;
- and C = 2 * L - 1 with some integer L >= 1 is any even number.
Any other set of rules could be easily created in similar way:
- let M = 3 ^ K;
- then A = 3 * J + 1;
- and C = 3 * L - 1.
We have the task Linear Congruential Generator to practice this algorithm and several other tasks will depend on it to create the sequence of input data. For those curious to know where word congruential came from, please refer to the Modular Arithmetic article. More info on LCG could be found in dedicated Wikipedia article.