Generation of random numbers of high digit capacity

Once I was faced with the task of generating 128-bit random numbers to implement a genetic algorithm. Due to the large dimension of the problem, the algorithm ran for a long time, so there were increased demands on the speed of work. I decided to write my own generator specifically for the task.

In this post, we will discuss the use of a linear congruential method to obtain pseudo-random numbers of 64 and 128 bits, explaining the principle of operation and selection of parameters.

If you use the RNG from the standard library, you have non-standard requirements for it, or just want to control the whole process of random number generation in your application, welcome under cat.
')

Down with the standard generator!

Many people know that the generation of random numbers is an integral part of many algorithms. In addition to mathematics and statistics, random numbers are used in computer modeling, cryptography, machine learning (artificial neural networks), stochastic optimization (evolutionary computing), and in many tasks from other fields, for example, in more understandable things like rendering beautiful pictures, engines, and video game logic

All fairly common programming languages ​​have functions for generating random (or, to be extremely accurate, pseudo-random) numbers. However, sometimes it becomes necessary to implement your own random number generator (RNG). Although the RNG out of the box is usually good enough for use in most cases, it also happens that the generator is too steep and not needed, but I still don’t like the built-in RNG.

The reasons may be different and not obvious at first glance. First, it is worth noting that the problem of generating random numbers often involves finding a balance between the speed of work and the quality of the result. Sometimes you need to do a little faster or a little more difficult.

Secondly, the RNG is not just a porridge of arithmetic operations, but a strictly deterministic algorithm, the characteristics of which can vary greatly. In some scientific experiments, it is necessary to fully describe the conditions of the tests to ensure their reproducibility. This includes the algorithm and parameters of the RNG. In this case, it is better to have your own implementation.

There may be a problem in which the simultaneous operation of different RNGs is necessary. It is different, and the built-in generator is usually one. You can, of course, run multiple copies with different initial grains, but in this case, the generators will give out elements of the same sequence (which is cyclically repeated) simply by starting from different places. The cycle length is huge, but theoretically it could create problems.

In my case, it was necessary to generate 128-bit numbers. In C ++, there is no function that returns at least 64-bit. After a long googling, I found confusion in rand () and RAND_MAX in different compilers, a set of crutches for generating 64 bits, and decided to abandon the built-in RNG. Writing my own generator seemed like an elementary task — in a couple of iterations of a linear congruent generator, get two 64-bit numbers and then glue them together. It was not so easy. But first things first.

For the cause!

So, let's start creating the RNG. We take as a basis a simple and popular linear congruential method that works according to the formula:
where x _i , x _{i + 1} are the current and next random numbers; a , c, and m are some constants; mod is the operator for finding the remainder of division.

The constant m is often taken equal to 2 ³² or 2 ^{64 in} order to avoid division in the software implementation. In order to get 64-bit remnants as a result, I used m = 2 ⁶⁴ . But where do you get the constants a and c ? The following pair was found on Wikipedia : a = 6364136223846793005 and c = 1442695040888963407. Without thinking twice, I wrote a generator using these parameters and began testing my genetic algorithm. However, he quickly became obsessed. Suspicions fell on the RNG. It turns out that a few lower digits of the resulting sequence of 64-bit “random” numbers showed not at all random behavior. The values ​​of some binary digits of consecutive numbers are depicted in the form of monochrome pictures:


The values ​​of the lower 5th, 15th and 20th digits (numbering from scratch)

Approximately 20-24 lower binary digits are not suitable for use. With the increase in the number of discharge increases its randomness. Thus, to obtain a single 64-bit random number, two iterations of the linear congruent generator are necessary. The result is the concatenation of two 32-bit fragments:


For example, the same principle is used in java.util.Random , although due to the fact that m = 2 ⁴⁸ , only 16 low-order bits are discarded when generating int and long. This, of course, negatively affects the quality of random numbers.

Here is an example of a sequence of 64-bit numbers, which is obtained when a = 6364136223846793005, c = 1442695040888963407, m = 2 ⁶⁴ , x ₀ = 0 by the method described in the figure:

1442695037175000593
11166244415259155177
7076646891078057782
1459328390042580878
8905969149530007863
11682375496967736740
897247724006084730

How random are these numbers? Approximately at the level of the RNG from the standard Java library, perhaps even slightly better. The calculation of each number requires only two multiplication operations.

If you need several different generators, you should choose other values ​​of the constants a and c , calculated on m = 2 ⁶⁴ . The article on this link provides examples of three constants with "good qualities":

a = 2862933555777941757	c - odd, m = 2 64
a = 3202034522624059733
a = 3935559000370003845

128-bit random numbers

There is nothing difficult in dazzling two 64-bit numbers into one, however, there is one interesting point: the simultaneous generation of two numbers 64 bits can be 25% faster than sequential, with little damage to their “randomness” ".

The idea is to get by with three iterations of the linear congruential generator instead of the necessary four. This can be achieved if only 20 lower bits of the result are discarded at each iteration instead of 32 as in the previous method. As you can see in the monochrome picture above, the 20th digit is already random enough to be used. The remaining digits allow you to form a 128-bit number.




Using the same parameters a , c , m and x ₀ , such numbers are obtained:

26613026195691280501944396807868523054
136526799440480448897747671965175330512
26919857327062567305005081067174740455
151962490054994640693408155996993201355
16551299175504952598134597160493279376
67275013191410065527820230898073478166
72445587156806476974393951227561270647

This method of extracting random numbers was enough for my application to work. It turned out quickly and practical. Surely the information from the article will be useful to someone. That's all, thank you for your attention. (The picture with the cubes on the cover is taken from here . )

All happy accidents in the new year!