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

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

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

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

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.

## No comments:

Post a Comment