Nov 21 2016

How to generate Random numbers

Category: Algorithm | Maths ashish sheth @ 14:58

If you want to generate a random number for some business logic you are implementing, what would you do?

You would use Random class if you use Java or C#. Most programming language has some library function or class to give you random number.

But suppose you need to produce random numbers by your own without using any library function what would you do?

There are many algorithms to use to produce random number and here I will demonstrate a very basic algorithm which uses the modulo operator (%) in C#. The goal is not to come up with a foolproof algorithm to generate random numbers, the goal is to just use simple math trick to understand how random numbers can be generated. If you really need to generate random numbers in your programs then you should use the inbuilt library functions provided by the language or framework you are using.

You know what is modulo (%) operator is, right? It gives you the remainder when you divide the left hand number by right hand number.

so doing 20 % 20 will give you 0. And 20 % 19 will give you 1 and 20 % 18 will give to 2 and so on.

20 % 20 = 0
20 % 19 = 1
20 % 18 = 2
20 % 17 = 3
20 % 16 = 4
20 % 15 = 5
20 % 14 = 6
20 % 13 = 7
20 % 12 = 8
20 % 11 = 9
20 % 10 = 0
20 % 9 = 2
20 % 8 = 4
20 % 7 = 6
20 % 6 = 2
20 % 5 = 0
20 % 4 = 0
20 % 3 = 2
20 % 2 = 0
20 % 1 = 0

You can see when you divide 20 by numbers from 1 to 20 you get number 0 to 9 as remainders. The trick is the larger the dividend, larger the range of number you get as remainders.

So let’s set dividend d to a some large number, for the purpose of this post I will choose 10000. This will give you the range of 0 to 4999 as remainders.

But as you can see, this method produces sequential numbers, not random numbers. Well, on every iteration you use the remainder to produce a new dividend and you can see that instead of sequential numbers you are getting the random numbers.

So, let’s use below equation to produce a new dividend on every iteration, which uses the current remainder as new dividend:

remainder = a * current remainder + b % divisor

Using the above equation, we get below result, when a = 100, b = 100 and divisor is set to 19:

2100 % 19 = 10
1100 % 19 = 17
1800 % 19 = 14
1500 % 19 = 18
1900 % 19 = 0
100 % 19 = 5
600 % 19 = 11
1200 % 19 = 3
400 % 19 = 1
200 % 19 = 10
1100 % 19 = 17
1800 % 19 = 14
1500 % 19 = 18
1900 % 19 = 0
100 % 19 = 5
600 % 19 = 11
1200 % 19 = 3
400 % 19 = 1
200 % 19 = 10

Notice that the above equation produces a random number on every step but it repeats after few iteration. This is because the chosen values of the a, b and divisor.

Setting the divisor to a really large value can give us random numbers which may not repeat to soon. Such as below:

100 % 12345 = 100
10100 % 12345 = 10100
1010100 % 12345 = 10155
1015600 % 12345 = 3310
331100 % 12345 = 10130
1013100 % 12345 = 810
81100 % 12345 = 7030
703100 % 12345 = 11780
1178100 % 12345 = 5325
532600 % 12345 = 1765
176600 % 12345 = 3770
377100 % 12345 = 6750
675100 % 12345 = 8470
847100 % 12345 = 7640
764100 % 12345 = 11055

1105600 % 12345 = 6895 

689600 % 12345 = 10625
1062600 % 12345 = 930
93100 % 12345 = 6685
668600 % 12345 = 1970

Here, a and b is set to 100 and divisor is set to 12345, while current remainder is initialized to 0 at the start. Note that setting divisor to 12345 did not produce repeated numbers in the first 20 iterations, but it can still produce repeated numbers after few hundred iterations. But you get the idea, right?

The equation a + b * currentRemainder  % divisor is called Linear Congruential Generator. You can read more about it here.

Tags: ,