Seed in Random Number Generation

Random Numbers

Randomization is an awesome concept. Efficiency of most of the algorithms are proportional to how randomly the algorithm is implemented. Talking about one the best sort algorithms – Quick Sort. The efficiency depends on the choice of pivot and it is wise to choose a pivot randomly to get an even distribution of elements around it.

Of course no one can beat my bad luck if my randomly chosen pivot misbehaves. But still you will be luckier and have a better running time and upper bound on the running time of this algorithm.

This is not the only algorithm where randomization plays a good role, but building data structures like Skip Lists are heavily benefited by random choices. There are many more to name.

Java Offers Random Number Generation

Java provides a class named Random that helps in random number generation. Here is a sample piece of code to generate random numbers.

It is important to understand the various versions and its usage. There are two public constructors to this class. Random() and Random(long seed) . If you are planning to generate random integers, it provides two instance methods nextInt() and nextInt(int n).

nextInt() :

Works out of the box and returns a number which is pseudo randomly generated by the Random Number Generator. This number can be anything between 0 and 232  -1 .

nextInt(int n) :

What if you want an upper bound on the returned integers. Let us say you want to generate random numbers from 0 to 10000. Yes, you need this overloaded version of the method. The parameter it takes is the upper bound within which you need random numbers. Wow! that was cool. But unfortunately we cannot supply a lower bound to the random number generator.

How to generate random numbers greater than a  lower bound K. Well there is a hack and you can use it in a clean way by returning K + nextInt() or K+ nextInt(int n).

A special mention is required to the constructor of this class Random(long seed). Seed in Random Number Generation is another awesome concept.

What exactly is the seed?
The seed is an internal concept, I will be telling you the effect of using a seed. The detailed explanation of its usage will be out of scope of this small post. The random number generator works perfectly well without a seed. But here is a use case for seed:

I have written a code which processes 10000 numbers and does some complex operations on it. I used the random number generator to generate those 10000 numbers and start testing my code. The code fails and returns an error and now I need to debug it. So I re ran it and tried to reproduce the scenario. As the numbers were randomly generated, this time the number didn’t occur and hence the program passed. If by any chance I can generate the same random numbers again, I can reproduce the scenario.

The seed is a solution for such a situation.

If we supply a seed to the constructor, it will always generate a sequence of random numbers in the same order on every run of the number generation code. Here is a program

The output for first run:
[8957, 5419, 9685, 4231, 9289, 7154, 1146, 9795, 991, 1897, 1495, 8206, 3547, 7089, 9417, 7221, 6245, 4400, 2788, 132, 2139, 1458, 2752, 6196, 5609, 2907, 5374, 5093, 5269, 1626, 313, 8307, 3415, 347, 7480, 8072, 3733, 457, 1231, 9774, 5437, 941, 2469, 5119, 716, 5752, 4321, 9563, 4972, 6442, 3806, 9077, 5562, 8540, 3005, 4459, 2500, 5744, 2393, 6704, 4241, 7170, 8261, 7847, 7259, 2155, 2146, 9294, 2856, 2947, 5277, 3525, 423, 1344, 2805, 6681, 8213, 5551, 5402, 3074, 9215, 8078, 1665, 1797, 7121, 5523, 9572, 310, 5917, 5853, 3206, 4478, 3480, 9589, 7828, 9861, 3886, 6608, 2535, 9341]

The output for second run:

[8957, 5419, 9685, 4231, 9289, 7154, 1146, 9795, 991, 1897, 1495, 8206, 3547, 7089, 9417, 7221, 6245, 4400, 2788, 132, 2139, 1458, 2752, 6196, 5609, 2907, 5374, 5093, 5269, 1626, 313, 8307, 3415, 347, 7480, 8072, 3733, 457, 1231, 9774, 5437, 941, 2469, 5119, 716, 5752, 4321, 9563, 4972, 6442, 3806, 9077, 5562, 8540, 3005, 4459, 2500, 5744, 2393, 6704, 4241, 7170, 8261, 7847, 7259, 2155, 2146, 9294, 2856, 2947, 5277, 3525, 423, 1344, 2805, 6681, 8213, 5551, 5402, 3074, 9215, 8078, 1665, 1797, 7121, 5523, 9572, 310, 5917, 5853, 3206, 4478, 3480, 9589, 7828, 9861, 3886, 6608, 2535, 9341]

This means that we can actually get the same sequence of numbers every time if we know the seed.

Happy hacking!!! don’t forget to subscribe 🙂