How the random number generator program works. What is a random number generator

Note that ideally the distribution density curve random numbers would look like the one shown in Fig. 22.3. That is, in the ideal case, the same number of points fall into each interval: N i = N/k , Where N total number of points, k number of intervals, i= 1, ½, k .

It should be remembered that the generation of an arbitrary random number consists of two stages:

• generating a normalized random number (that is, uniformly distributed from 0 to 1);
• transformation of normalized random numbers r i into random numbers x i, which are distributed according to the (arbitrary) distribution law required by the user or in the required interval.

Random number generators according to the method of obtaining numbers are divided into:

• physical;
• tabular;
• algorithmic.

Physical RNGs

Examples of physical RNGs are: a coin (“eagle” 1, “tails” 0); dice; a drum with an arrow divided into sectors with numbers; hardware noise generator (GS), which is used as a noisy thermal device, for example, a transistor (Fig. 22.422.5).

Tabular RNG

Tabular RNG as a source of random numbers use specially compiled tables containing verified uncorrelated, that is, numbers that do not depend on each other in any way. In table. 22.1 shows a small fragment of such a table. Walking the table from left to right from top to bottom, you can get random numbers evenly distributed from 0 to 1 with the desired number of decimal places (in our example, we use three decimal places for each number). Since the numbers in the table do not depend on each other, the table can be bypassed different ways, for example, from top to bottom, or from right to left, or, say, you can select numbers that are in even positions.

The advantage of this method is that it gives truly random numbers, since the table contains verified uncorrelated numbers. Disadvantages of the method: a lot of memory is required to store a large number of digits; great difficulties in generating and checking such tables, repetitions when using the table no longer guarantee the randomness of the numerical sequence, and hence the reliability of the result.

There is a table containing 500 absolutely random verified numbers (taken from the book by I. G. Venetsky, V. I. Venetskaya "Basic Mathematical and Statistical Concepts and Formulas in Economic Analysis").

Algorithmic RNG

The numbers generated using these RNGs are always pseudo-random (or quasi-random), that is, each subsequent generated number depends on the previous one:

r i + 1 = f(r i) .

Sequences made up of such numbers form loops, that is, there is necessarily a cycle that repeats an infinite number of times. Repeating cycles are called periods.

The advantage of RNG data is speed; generators practically do not require memory resources, they are compact. Disadvantages: the numbers cannot be fully called random, since there is a dependence between them, as well as the presence of periods in the sequence of quasi-random numbers.

Consider several algorithmic methods for obtaining RNG:

• method middle squares;
• method middle works;
• mixing method;
• linear congruent method.

Mean square method

There is some four-digit number R 0 . This number is squared and entered into R 1 . Coming from R 1 the middle (four middle digits) is taken a new random number and written into R 0 . Then the procedure is repeated (see Fig. 22.6). Note that in fact, as a random number, it is necessary to take not ghij, A 0.ghij with a zero and a decimal point appended to the left. This fact is reflected in Fig. 22.6, and in subsequent similar figures.

Disadvantages of the method: 1) if at some iteration the number R 0 becomes zero, then the generator degenerates, so the correct choice of the initial value is important R 0; 2) the generator will repeat the sequence through M n steps (at best), where n word length R 0 , M the base of the number system.

For an example in fig. 22.6 : if number R 0 will be represented in the binary number system, then the sequence of pseudo-random numbers will repeat after 2 4 = 16 steps. Note that the repetition of the sequence can occur even earlier if the initial number is chosen unsuccessfully.

The method described above was proposed by John von Neumann and dates back to 1946. Since this method proved unreliable, it was quickly abandoned.

Method of median products

Number R 0 multiplied by R 1 , from the result R 2 the middle is removed R 2 * (this is another random number) and multiplied by R 1 . According to this scheme, all subsequent random numbers are calculated (see Fig. 22.7).

Mixing method

The shuffling method uses operations to rotate the contents of a cell left and right. The idea of ​​the method is as follows. Let the cell store the initial number R 0 . Cyclically shifting the contents of the cell to the left by 1/4 of the length of the cell, we get a new number R 0*. Similarly, by cyclically shifting the contents of a cell R 0 to the right by 1/4 of the cell length, we get the second number R 0**. Sum of numbers R 0 * and R 0** gives a new random number R 1 . Further R 1 is entered into R 0 , and the whole sequence of operations is repeated (see Fig. 22.8).

Note that the number resulting from the summation R 0 * and R 0 ** , may not fit entirely in the cell R 1 . In this case, extra digits should be discarded from the received number. Let us explain this for Fig. 22.8, where all cells are represented by eight binary digits. Let R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Then R 0 * + R 0 ** = 100110010 2 = 306 10 . As you can see, the number 306 occupies 9 digits (in the binary number system), and the cell R 1 (as well as R 0 ) can hold a maximum of 8 bits. Therefore, before entering the value in R 1 it is necessary to remove one "extra", leftmost bit from the number 306, resulting in R 1 will go no longer 306, but 00110010 2 = 50 10 . Also note that in languages ​​such as Pascal, "truncation" of extra bits when a cell overflows is done automatically in accordance with the given variable type.

Linear congruent method

The linear congruential method is one of the simplest and currently most used procedures that simulate random numbers. This method uses the mod( x, y) , which returns the remainder after dividing the first argument by the second. Each subsequent random number is calculated based on the previous random number using the following formula:

r i+ 1 = mod( k · r i + b, M) .

The sequence of random numbers obtained using this formula is called linear congruent sequence. Many authors refer to a linear congruent sequence as b = 0 multiplicative congruent method, and when b ≠ 0 — mixed congruent method.

For a high-quality generator, it is required to select suitable coefficients. It is necessary that the number M was quite large since the period cannot have more M elements. On the other hand, the division used in this method is a rather slow operation, so for a binary computer, the logical choice would be M = 2 N, because in this case, finding the remainder of the division is reduced inside the computer to the binary logical operation "AND". It is also common to choose the largest prime number M, less than 2 N: in the special literature it is proved that in this case the least significant digits of the resulting random number r i+ 1 behave just as randomly as the older ones, which has a positive effect on the entire sequence of random numbers as a whole. An example is one of Mersenne numbers, equal to 2 31 1 , and thus, M= 2 31 1 .

One of the requirements for linear congruent sequences is the longest possible period. The length of the period depends on the values M , k And b. The theorem that we present below allows us to determine whether it is possible to achieve a period of maximum length for specific values M , k And b .

Theorem. Linear congruent sequence defined by numbers M , k , b And r 0 , has a period of length M if and only if:

• numbers b And M coprime;
• k 1 x p for every simple p, which is a divisor M ;
• k 1 is a multiple of 4 if M multiple of 4.

Finally, let's conclude with a couple of examples of using the linear congruential method to generate random numbers.

It was found that a series of pseudo-random numbers generated based on the data from example 1 will be repeated every M/4 numbers. Number q is set arbitrarily before the start of calculations, however, it should be borne in mind that the series gives the impression of being random at large k(and therefore q). The result can be slightly improved if b odd and k= 1 + 4 q in this case, the series will be repeated every M numbers. After a long search k the researchers settled on the values ​​69069 and 71365.

The random number generator using the data from example 2 will produce random non-recurring numbers with a period of 7 million.

The multiplicative method for generating pseudo-random numbers was proposed by D. H. Lehmer in 1949.

Checking the quality of the generator

The quality of the entire system and the accuracy of the results depend on the quality of the RNG. Therefore, the random sequence generated by the RNG must satisfy a number of criteria.

The checks carried out are of two types:

• checks for uniform distribution;
• testing for statistical independence.

Checks for uniform distribution

1) RNG should give close to the following values ​​of statistical parameters characteristic of a uniform random law:

2) Frequency test

The frequency test allows you to find out how many numbers fell into the interval (m r – σ r ; m r + σ r) , i.e. (0.5 0.2887; 0.5 + 0.2887) or eventually (0.2113; 0.7887) . Since 0.7887 0.2113 = 0.5774 , we conclude that in a good RNG, about 57.7% of all random numbers drawn should fall into this interval (see Fig. 22.9).

Also, keep in mind that the number of numbers in the interval (0; 0.5) should be approximately equal to the number of numbers in the interval (0.5; 1) .

3) Chi-square test

The chi-square test (χ 2 -test) is one of the most famous statistical tests; it is the main method used in combination with other criteria. The chi-square test was proposed in 1900 by Karl Pearson. His remarkable work is regarded as the foundation of modern mathematical statistics.

For our case, a chi-square test will allow us to find out how much the created by us real The RNG is close to the RNG reference, i.e. whether it satisfies the uniform distribution requirement or not.

frequency diagram reference The RNG is shown in fig. 22.10. Since the distribution law of the reference RNG is uniform, the (theoretical) probability p i hitting numbers in i-th interval (total of these intervals k) is equal to p i = 1/k . And thus, in each k intervals will fall smooth By p i · N numbers ( N — total generated numbers).

A real RNG will produce numbers distributed (and not necessarily evenly!) k intervals and each interval will include n i numbers (total n 1 + n 2 + ½ + n k = N ). How can we determine how good and close the tested RNG is to the reference one? It is quite logical to consider the squares of the differences between the received number of numbers n i and "reference" p i · N . Let's add them up, and as a result we get:

χ 2 exp. =( n 1 p 1 · N) 2 + (n 2 p 2 · N) 2 + + ( n k – p k · N) 2 .

It follows from this formula that the smaller the difference in each of the terms (and, therefore, the smaller less valueχ 2 exp. ), the stronger the law of distribution of random numbers generated by a real RNG tends to be uniform.

In the previous expression, each of the terms is assigned the same weight (equal to 1), which in fact may not be true; therefore, for the chi-square statistic, it is necessary to normalize each i th term, dividing it by p i · N :

Finally, let's write the resulting expression more compactly and simplify it:

We have obtained the value of the chi-square test for experimental data.

In table. 22.2 are given theoretical chi-squared values ​​(χ 2 theor.), where ν = N 1 is the number of degrees of freedom, p is a user-specified confidence level that specifies how much the RNG should meet the uniform distribution requirements, or p — is the probability that the experimental value χ 2 exp. will be less than the tabulated (theoretical) χ 2 theor. or equal to it.

Consider acceptable p from 10% to 90%.

If χ 2 exp. much more than χ 2 theor. (that is p is large), then the generator does not satisfy the requirement of a uniform distribution, since the observed values n i go too far from theoretical p i · N and cannot be considered random. In other words, such a large confidence interval is established that the restrictions on the numbers become very loose, the requirements on the numbers are weak. In this case, a very large absolute error will be observed.

Even D. Knuth in his book "The Art of Programming" noted that having χ 2 exp. small is also, in general, not good, although it seems, at first glance, remarkable from the point of view of uniformity. Indeed, take a series of numbers 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, they are ideal in terms of uniformity, and χ 2 exp. will be practically zero, but you are unlikely to recognize them as random.

If χ 2 exp. much less than χ 2 theor. (that is p small), then the generator does not satisfy requirement of a random uniform distribution, since the observed values n i too close to theoretical p i · N and cannot be considered random.

But if χ 2 exp. lies in a certain range, between two values ​​of χ 2 theor. , which correspond, for example, p= 25% and p= 50%, then we can assume that the values ​​of random numbers generated by the sensor are completely random.

In addition, it must be borne in mind that all values p i · N must be large enough, for example, greater than 5 (found empirically). Only then (with a sufficiently large statistical sample) can the experimental conditions be considered satisfactory.

So, the verification procedure is as follows.

Tests for statistical independence

1) Checking for the frequency of occurrence of a digit in a sequence

Consider an example. The random number 0.2463389991 consists of the digits 2463389991, and the number 0.5467766618 consists of the digits 5467766618. Combining the sequences of digits, we have: 24633899915467766618.

It is clear that the theoretical probability p i fallout i th digit (from 0 to 9) is 0.1.

2) Checking the appearance of series of identical numbers

Denote by n L number of series of identical consecutive digits of length L. Everything needs to be checked L from 1 to m, Where m is a user-specified number: the maximum number of identical digits that occur in a series.

In the example "24633899915467766618", 2 series of length 2 (33 and 77) were found, that is n 2 = 2 and 2 series of length 3 (999 and 666), i.e. n 3 = 2 .

The probability of a series with a length of L is equal to: p L= 9 10 L (theoretical). That is, the probability of occurrence of a series with a length of one character is equal to: p 1 = 0.9 (theoretical). The probability of a two-character series appearing is: p 2 = 0.09 (theoretical). The probability of a three-character series appearing is: p 3 = 0.009 (theoretical).

For example, the probability of occurrence of a series with a length of one character is equal to p L= 0.9 , since there can be only one character out of 10, and only 9 characters (zero is not counted). And the probability that two identical characters "XX" will meet in a row is 0.1 0.1 9, that is, the probability of 0.1 that the character "X" will appear in the first position is multiplied by the probability of 0.1 that the same character will appear in the second position "X" and multiplied by the number of such combinations 9.

The frequency of occurrence of series is calculated according to the “chi-square” formula we have previously analyzed using the values p L .

Note: The generator can be checked multiple times, but checks are not complete and do not guarantee that the generator produces random numbers. For example, a generator that produces the sequence 12345678912345 will be considered ideal during checks, which, obviously, is not entirely true.

In conclusion, we note that the third chapter of the book "The Art of Programming" by Donald E. Knuth (volume 2) is completely devoted to the study of random numbers. It explores various methods for generating random numbers, statistical criteria for randomness, and the transformation of uniformly distributed random numbers into other types of random variables. More than two hundred pages have been devoted to the presentation of this material.

On macroscopic random processes using such simple items as dice, roulette wheel or coin, can be based random number generators. Chaos theory and the theory of unstable dynamical systems can explain the presence of unpredictability in data, and even macroscopic systems, completely defined by Newton's equations, in practice often have an unpredictable output, since it depends on the microscopic details of the initial conditions.

By the way, on our website you can generate a random number using the Online Random Number Generator.

What is a random number generator and how does it use random physical processes?

Speed ​​of getting random numbers sufficient for applied problems cannot be provided by devices based on macroscopic random processes. The source of noise from which random bits are extracted is therefore the basis of modern AGNG. Noise sources are of two types: those that have a quantum nature and those that do not use quantum phenomena.

Some natural phenomena, such as the radioactive decay of atoms, are absolutely random and, in principle, cannot be predicted (the Davisson-Germer experiment can be considered one of the first experiments that prove the probabilistic nature of some phenomena), this fact is a consequence of the laws of quantum physics. And from statistical mechanics it follows that each system in its parameters has random fluctuations if the temperature is not equal to absolute zero.

Sophisticated random number generator.

For AGNG, some of the quantum mechanical processes are the "gold standard" because they are completely random. Using in random number generators phenomena include:

• Shot noise is the noise that is caused in electrical circuits by the discreteness of carriers. electric charge and this term also refers to the noise caused in optical instruments by the discreteness of the light carrier.
• Spontaneous parametric scattering, can also be used in random number generators.
• Radioactive decay - has a randomness to each of the individual decay events, so it is used as a source of noise. A different number of particles at different time intervals, as a result, gets to the receiver (it can be a Geiger counter or a scintillation counter).

It is much easier to detect non-quantum phenomena, but based on them random number generators, then they will have a strong dependence on temperature (for example, the amount of thermal noise will be proportional to the temperature environment). The following processes can be noted, among those used in the AGNG:

• The thermal noise in the resistor, after amplification, from which is obtained random voltage generator. In particular, the number generator in the Ferranti Mark 1 computer was based on this phenomenon.
• Atmospheric noise, which is measured by a radio receiver, can also be attributed here to the reception of particles arriving from space to Earth, recorded by the receiver, and their number will be random, at different time intervals.
• The difference in the speed of the clock is a phenomenon that consists in the fact that the course of different clocks will absolutely not coincide.

In order to obtain from a physical random process sequence of random bits, there are several approaches for this. One of them consists in the fact that the received signal-to-noise is amplified, then filtered and fed to the input of a high-speed voltage comparator to obtain a logical signal. There will be a random duration of the comparator states and this allows you to create sequence of random numbers, making measurements of these states.

The second approach is that a random signal is fed to the input of the analog-to-digital converter (both special devices and the audio input of a computer can be used), which is a sequence of random numbers, which will result in a digitized signal and, at the same time, it can be processed programmatically .

What is a random number generator and what other phenomena does it use?

Using physical random processesrandom number generators, make it possible to obtain good random numbers, but their production is expensive and relatively difficult (especially for those AGNGs that are based on radioactive decay), but there are other more accessible sources of randomness:

Simple random number generation.

The work of digital video cameras, which use the shooting of macroscopic phenomena, should be attributed to the most unusual generators. For example, to generate random numbers, a video recording was used by the team from Silicon Graphics lava lamp because the wax randomly changes its shape in the lamp. Ribbons from a fan in the airflow or bubbles in an aquarium can also be used as a subject for photography.

Every person, regardless of the degree of gambling and adventurism, one way or another, came across such a thing as a lottery. And only a few have asked themselves how the random distribution of winning combinations of numbers occurs. How does one or another number fall out? What causes the scales to sink in the direction of the winner? Let's consider this in detail.

We all at least once in our lives have encountered such a phenomenon as a lottery. But few people thought or imagined how exactly this system works, what a lottery number generator is and what its principle of operation is.

The concept of a number generator

A random number generator for a lottery is a certain device or a given program that generates numbers that are on a selected interval in a random (or rather, pseudo-random) order. For a certain type of lotteries, for example, "Sportloto", numbers are generated that are in the range from 1 to 49.

Allocate a number generator for the lottery hardware and software. In any programming language, there is a RAND () function, it is she who is responsible for issuing a pseudo random numbers within the given range.

Why is it claimed that the given results are pseudo-random and that the lottery number generator works exactly on this principle?

RAND function: concept and method of use

The RAND() function is a program or, for example, an apparatus with a deterministic algorithm that, under the same given conditions, will constantly show the same results. But in order for the conditions of a true random sequence to be met, there must be no dependence on initial conditions or parameters. Therefore, to avoid such cases, a special RANDOMIZE procedure is additionally used, which removes the predictability of the initial conditions, making them random.

In addition to the principle of generation already known to us, another type of lottery generator is used. Let's consider it below.

Number generator 6 out of 45

Lottery Number Generator 6 out of 45 - program that is used to obtain lucky numbers. At the same time, it is possible to set additional parameters to obtain a better result.

You can specify selection criteria, for example:

• The number of winning numbers to get in the final result.
• Specify the range of numbers in which the selection will be carried out.
• Sorting of numbers can be set both in ascending and descending order.
• Select the type and method of division.
• Eliminate duplicates or leave the selection unsorted.
• Copy the link to the result and place it on the page in in social networks in order to publish the result.

Number generator: instructions for use

• The default is to display five numbers. By changing the settings, you can get up to 250 random winning combinations.
• We set the range, by default it is specified from 0 to 36, but you can specify up to a maximum of 9,999,999,999.
• We select the sorting necessary for our type of lottery: ascending, descending, or the arrangement of numbers in random order.
• The next step is to specify how the numbers will be separated from each other - a comma, a dot, a space, a semicolon.
• We get rid of random repetitions that arose during the sampling process.

Thus, we get qualitatively selected numbers, which can be the happiest and most winning ones.

Many lottery participants do not want to spend time selecting winning combination and filling out a lottery ticket.

To help them, most specialized lottery sites offer a very convenient “Automatic dialing” function. About what it is and how it works, we will tell today.

"Auto Set"

This function is a classic random number generator, invented since the founding of the first lottery sites and virtual casinos. Over 70% of virtual ticket buyers foreign lotteries choose this absolutely free option.

In addition, you can automatically select not one winning combination, but several (up to 50). This is very convenient for players who buy a large number of lottery tickets with different rates.

Win statistics

If you are still in doubt whether to use the "Automatic Dial" function or suffer from filling out tickets yourself, read on. Reviews of the Euromillion Lottery to their winners unequivocally state that the difference in the methods of filling out the ticket does not affect the chances of the participant in any way. Lottery statistics also tell us about this, according to which, from total number players who use this option on Internet sites receive a win of about 70%. In order not to be unfounded, here are examples of lucky winners in 2012 who made bets using a computer.

In March 2012, a US couple won a massive $218 million jackpot in the New York City Lottery. They didn't develop lottery strategy(read section Game strategies), but simply used the "Auto dial" function.

Winners record draw American national lottery PowerBall, which split the $586 million equally, filled out their tickets using a random number generator.

An elderly lady, who did not want to think about the winning combination, entrusted the choice of numbers to the computer and won 336 million US dollars.

Pros of a random number generator

The first indisputable advantage of using this function is a significant time saving. With one click of the mouse, you can place several bets at once for one draw of any foreign lottery.

The second advantage is to ease the mental effort of the player to make a winning combination. If you are not a fanatic of numerology and do not believe in the magic of numbers, believe me, better than a computer You can't think of combinations of numbers.

The third fact in favor of "Automatic set" is absolutely equal chances of winning the jackpot and other big prize With lottery tickets filled in by hand.

Random numbers are a simple element of cryptography that is least talked about, but it is no less important than the rest. Almost all computer security systems that use cryptography need random numbers—for keys, unique numbers in protocols, and so on—and the security of such systems often depends on the randomness of its random numbers. If the random number generator is unreliable, the whole system breaks down.

Depending on who you're talking to, random number generation looks either trivial or impossible. Theoretically, this is impossible. John von Neumann, father computer science, said: "Anyone who believes that there are arithmetic methods for obtaining random numbers is certainly sinning." What he meant was that it is impossible to get anything truly random from the output of such a deterministic beast as a computer. This is true, but, fortunately, we can do something. What we need from a random number generator is not that the numbers are truly random, but that they cannot be predicted and reproduced. If we have these two conditions fulfilled, we can achieve security.

On the other hand, if we violate these two conditions, there is no security. In 1994, a computer random number generator for lotteries was installed in a Montreal casino. One observant player who spent a lot of time in the casino noticed that winning numbers were the same every day. He successfully hit three Jackpots in a row and received $600,000. (After wringing his hands, gnashing his teeth, and investigating everything, the casino paid the winnings.)

There are several broad classes of random number generators. Some of them are based physical processes, which can be considered rather random. The National Security Agency likes to use the electrical noise of diodes in their random number generating equipment. Other possibilities are a Geiger counter or radio interference receivers. One system on the Internet uses digital camera aimed at several strobe lights. Other systems use air turbulence in drives or when network packets arrive.

Some random number generators track the user's random movements. The program may ask the user to type a large string of arbitrary characters on the keyboard; it can use a sequence of characters or even the time between keystrokes to generate random numbers. Another program can easily require the user to move the mouse back and forth or grunt into the microphone.

Some random number generators apply this entered information without modification. In others, it serves as a seed (seed) for mathematical random number generators. This trick works best if the system needs more random numbers than the input provides.

Whatever the origin of the randomness, the generator will create a series of random bits. They can then be used as cryptographic keys and for everything else the system needs.