Random numbers online. Random number generator

Note that, ideally, the distribution density curve of random numbers would look like that shown in Fig. 22.3. That is, in the ideal case, the same number of points falls into each interval: N i = N/k where N   Is the total number of points k   - number of intervals i  \u003d 1, ..., k .

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

• generating a normalized random number (i.e., evenly distributed from 0 to 1);
• normalized random number conversion r i    into random numbers x i  that are distributed according to the necessary user (arbitrary) distribution law or in the required interval.

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

• physical;
• tabular;
• algorithmic.

Physical RNG

Examples of physical RNGs are: coin (“eagle” - 1, “tails” - 0); dice; sectorized drum with an arrow; a hardware noise generator (GS), which uses a noisy thermal device, for example, a transistor (Fig. 22.4–22.5).

Tabular RNG

Tabular RNGs use specially compiled tables containing verified uncorrelated, that is, in no way dependent on each other, numbers as a source of random numbers. In the table. 22.1 shows a small fragment of such a table. Traversing the table from left to right from top to bottom, you can get randomly distributed numbers from 0 to 1 with the desired number of decimal places (in our example, we use three characters for each number). Since the numbers in the table are independent of each other, the table can be bypassed in 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 really random numbers, since the table contains verified uncorrelated numbers. The disadvantages of the method: to store a large number of digits requires a lot of memory; the great difficulties of generating and checking such tables, repetitions when using a table no longer guarantee the randomness of a numerical sequence, and therefore the reliability of the result.

A table is found containing 500 absolutely randomly 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 composed of such numbers form loops, that is, there necessarily exists a cycle repeating an infinite number of times. Repeating cycles are called periods.

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

Consider several algorithmic methods for obtaining RNG:

• middle square method;
• method of middles;
• mixing method;
• linear congruent method.

Middle square method

There is some four-digit number R0. This number is squared and entered in Rone . Next from R1 the middle is taken (four middle digits) - a new random number - and is written in R0. Then the procedure is repeated (see Fig. 22.6). Note that in fact, as a random number, it is necessary to take not ghij, but 0.ghij   - with a zero and a decimal point assigned to the left. This fact is reflected as in fig. 22.6, and in subsequent similar figures.

Disadvantages of the method: 1) if at some iteration the number R0 becomes equal to zero, then the generator degenerates, therefore, the correct choice of the initial value is important R0; 2) the generator will repeat the sequence through M n   steps (at best) where n   - bit number R0 , M   - The basis of the number system.

For an example in fig. 22.6: if the number R0 will be represented in binary notation, the sequence of pseudorandom numbers will be repeated in 2 4 \u003d 16 steps. Note that the repetition of the sequence may occur earlier if the initial number is chosen unsuccessfully.

The method described above was proposed by John von Neumann and relates to 1946. Since this method turned out to be unreliable, it was quickly abandoned.

The method of middles

Number R0 times R1, from the result R2 middle is extracted R2 * (this is another random number) and is multiplied by Rone . According to this scheme, all subsequent random numbers are calculated (see Fig. 22.7).

Mixing method

The method of mixing uses the operations of cyclic shift of the contents of the cell left and right. The idea of \u200b\u200bthe method is as follows. Let the initial number be stored in the cell R0. Cyclically shifting the contents of the cell to the left by 1/4 of the length of the cell, we get a new number R0 *. Similarly, cyclically shifting the contents of a cell R0 right 1/4 of the cell length, we get the second number R0 **. Sum of numbers R0 * and R0 ** gives a new random number Rone . Further R1 is entered in R0, and the whole sequence of operations is repeated (see Fig. 22.8).

Please note that the number resulting from the summation R0 * and R0 **, may not fit completely in the cell Rone . 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 be R0 * = 10010001 2 = 145 10 , R0 ** = 10100001 2 = 161 10 then R0 * + R0 ** = 100110010 2 = 306 10 . As you can see, the number 306 takes 9 digits (in binary notation), and the cell R1 (like R0) can accommodate a maximum of 8 digits. Therefore, before entering the value in R1 it is necessary to remove one "extra", the leftmost bit from the number 306, resulting in R1 will no longer go to 306, but 00110010 2 \u003d 50 10. Also note that in languages \u200b\u200bsuch as Pascal, the "trimming" of excess bits during a cell overflow is done automatically in accordance with the specified type of variable.

Linear congruent method

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

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

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

For a high-quality generator, you need to select the appropriate 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 the choice would be logical for a binary computer M = 2 N  , since in this case, finding the remainder of the division is reduced inside the computer to the binary logical operation “AND”. The choice of the largest prime number is also widespread. M  less than 2 N  : in the literature it is proved that in this case the least significant bits of the resulting random number r i  + 1 behave as randomly as elders, which positively affects the entire sequence of random numbers as a whole. An example is one of mersenne numbersequal to 2 31 - 1, and thus M  \u003d 2 31 - 1.

One of the requirements for linear congruent sequences is the longest possible length of the 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:

• the numbers b    and M    mutually simple;
• k  - 1 times p    for every simple p  being a divisor M ;
• k  - 1 is a multiple of 4 if M    multiple of 4.

Finally, in conclusion, consider a couple of examples of using the linear congruent method to generate random numbers.

It was found that a series of pseudorandom numbers generated based on the data from Example 1 will be repeated every M/ 4 numbers. Number q   is set arbitrarily before the commencement of calculations, however, it should be borne in mind that the series gives the impression of randomness at large k   (and therefore q  ) The result can be slightly improved if b   odd and k  \u003d 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 \u200b\u200b69069 and 71365.

A random number generator using the data from Example 2 will produce random non-repeating numbers with a period of 7 million.

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

Generator Performance Check

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;
• checks for statistical independence.

Distribution Tests

1) RNG should produce close to the following values \u200b\u200bof statistical parameters characteristic of a uniform random law:

2) Frequency test

The frequency test allows you to find out how many numbers fell in the interval (m r – σ r ; m r + σ r) , i.e. (0.5 - 0.2887; 0.5 + 0.2887) or, ultimately, (0.2113; 0.7887). Since 0.7887 - 0.2113 \u003d 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).

It is also necessary to take into account that the number of numbers that fall into the interval (0; 0.5) should be approximately equal to the number of numbers that fall into the interval (0.5; 1).

3) Chi-square test

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

For our case, checking by the criterion "chi-square" will let you know how much we created real  RNG is close to the RNG standard, that is, does it satisfy the requirement of uniform distribution or not.

Frequency diagram reference  RNG is presented in fig. 10/22. Since the distribution law of the reference RNG is uniform, the (theoretical) probability p i   hit numbers in i  interval (total of these intervals k  ) is equal p i = 1/k . And thus, in each of k   intervals will fall smooth  by p i · N   numbers ( N   Is the total number of generated numbers).

A real RNG will produce numbers distributed (and not necessarily evenly!) Over k   intervals and in each interval n i   numbers (in total n 1 + n  2 + ... + n k = N ) How do we determine how well the tested RNG is good and close to the reference? It is logical to consider the squares of the differences between the obtained number of numbers n i   and "reference" p i · N . Add them, and as a result we get:

χ 2 exp. \u003d ( n  1 - p  one · N) 2 + (n  2 - p  2 N) 2 + ... + ( n k – p k · N) 2 .

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

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

Finally, we write the resulting expression more compactly and simplify it:

We got the value of the chi-square criterion for experimental  data.

In the table. 22.2 are given theoretical  Chi-square values \u200b\u200b(χ 2 theor.), where ν = N  - 1 is the number of degrees of freedom, p  - this is a confidence probability specified by the user, which indicates how much the RNG should satisfy the requirements of uniform distribution, or p — it is the probability that the experimental value of χ 2 exp. will be less than the tabulated (theoretical) χ 2 theory. or equal to him.

Considered acceptable p from 10% to 90%.

If χ 2 exp. much larger than χ 2 theory. (i.e p  - great), then the generator does not satisfy  the requirement of 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 numbers become very unstable, the requirements for numbers become weak. In this case, a very large absolute error will be observed.

Even D. Knut in his book "The Art of Programming" noted that to have χ 2 exp. small, too, in general, is not good, although it seems, at first glance, wonderful 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 smaller than χ 2 theory. (i.e p  - little), then the generator does not satisfy  the 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 \u200b\u200bof χ 2 theory. which correspond, for example, p  \u003d 25% and p  \u003d 50%, then we can assume that the random numbers generated by the sensor are completely random.

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

So, the verification procedure has the following form.

Statistical Independence Checks

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

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

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

2) Checking the appearance of series of identical numbers

Denote by n L   the number of series of identical consecutive digits of length L  . Check everything L   from 1 to m  where m   Is a user-defined number: the maximum number of identical digits in a series.

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

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

For example, the probability of a series of one character in length is p L  \u003d 0.9, since in total one character out of 10 can occur, and in total 9 characters (zero does not count). And the probability that two identical “XX” symbols meet in a row is 0.1 · 0.1 · 9, that is, the probability 0.1 that the “X” appears in the first position is multiplied by the probability 0.1 that the same symbol appears in the second position "X" and multiplied by the number of such combinations 9.

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

Note: the generator can be checked repeatedly, but the checks do not have the completeness property and do not guarantee that the generator gives random numbers. For example, a generator issuing the sequence 12345678912345 ... will be considered ideal during checks, which, obviously, is not quite so.

In conclusion, we note that the third chapter of the art of programming by Donald E. Knuth (Volume 2) is completely devoted to the study of random numbers. It studies various methods for generating random numbers, statistical criteria for randomness, as well as converting uniformly distributed random numbers to other types of random variables. The presentation of this material is given over two hundred pages.

Numbers accompany us everywhere - the number of the house and apartment, phone, car, passport, plastic card, date, email passwords. We choose the combinations of numbers ourselves, but we get the majority by chance. Without realizing this report, we use randomly generated numbers every day. If we come up with PIN codes, then unique credit or salary card codes are generated by reliable systems that exclude access to passwords. Random number generators provide protection in areas requiring information processing speed, security and independent data processing.

The process of generating pseudorandom numbers is subject to certain laws and has been used for a long time, for example, when conducting lotteries. In the recent past, lotteries or lots were drawn. Now in many countries the winning numbers of state lotteries are determined precisely by the set of random numbers generated.

The advantages of the method

So, the random number generator is an independent modern mechanism for randomly determining combinations of numbers. The uniqueness and perfection of this method lies in the impossibility of external intervention in the process. The generator is a set of programs built, for example, on noise diodes. The device generates a stream of random noise, the current values \u200b\u200bof which are converted into numbers and make up combinations.

The generation of numbers provides an instant result - it takes several seconds to compose a combination. If we talk about lotteries, participants can immediately find out if the ticket number coincided with the winning one. This allows you to draw as often as participants want. But the main advantage of the method is the unpredictability and inability to calculate the algorithm for selecting numbers.

How pseudo random numbers are generated

In fact, random numbers are not random - a series starts with a given number and is generated by the algorithm. A pseudorandom number generator (PRNG or pseudorandom number generator) is an algorithm that generates a sequence of seemingly unrelated numbers subordinate to a usually uniform distribution. In computer science, pseudorandom numbers are used in many applications: in cryptography, simulation, the Monte Carlo method, etc. The quality of the result depends on the properties of the PRNG.

The source of generation can be physical noises from cosmic radiation to noise in a resistor, but such network security applications are almost never used. Cryptographic applications use special algorithms that generate sequences that cannot be statistically random. However, a correctly selected algorithm allows you to get a series of numbers that pass most random tests. The repetition period in such sequences is greater than the working interval from which the numbers are taken.

Many modern processors contain an PRNG, for example, in RdRand. As an alternative, sets of random numbers are created that are published in a one-time notepad (dictionary). The source of numbers in this case is limited and does not provide complete network security.

PRNG History

The prototype of the random number generator can be considered the board game Senet, common in ancient Egypt in 3500 BC. According to the conditions, two players participated, the moves were determined by throwing four flat black and white sticks - they were akin to the PRSP of that time. The sticks were thrown at the same time, and the points were counted: if one fell up with the white side, 1 point and an extra move, two white - two points and so on. The maximum result of five points was received by the player who threw four sticks on the black side.

Nowadays, the ERNIE generator has been used in the UK for lottery games for many years. There are two main methods for generating winning numbers: linear congruent and additive congruent. These and other methods are based on the principle of randomness of choice and are provided by software that infinitely produces numbers whose sequence cannot be guessed.

The PRNG functions continuously, for example, in slot machines. Under US law, this is a prerequisite that all software vendors must comply with.

Greetings to you dear readers! In this article I want to talk with you about the popular site random.org, with which you can choose a random winner in any competition. It doesn’t matter for which platform you choose the winner of the contest: Vkontakte, Twitter, Facebook, blog or website - the most important thing is that you have a ready list of participants, since random.org is just a random number generator and it is not able to select participants according to a given criteria.

Choosing a Winner on Facebook

I don’t like long narratives, so I’ll go straight to the point :)) If you want to determine the winner of the contest held on Facebook, then everything is very simple. There are several excellent sites that will allow you to easily and easily export all likes and comments from any publication of your choice in CSV format. You can then skip these lists through the random.org number generator and thus choose a random winner.

Note:   since reposts, as a condition for participating in Facebook contests, are strictly prohibited by the rules, there are no services that will automatically calculate them for you. In general, I do not advise breaking the rules on Facebook, since a lifetime ban on a page is a rather expensive price, which, God forbid, will have to pay for such violations.

Choose a winner on Vkontakte

Over time, I have compiled a fairly voluminous list of applications and websites with which you can determine the winner among social users. Vkontakte network. For convenience, I moved the list to a separate article.

How to determine a random winner using random.org

We sorted out the lists of participants, so back to the random.org topic. There are two types of services on the site: paid and free. The difference is that if you choose the winner by a paid method, then random.org saves all the results, creating a kind of official sampling protocol. Take a look. If your audience trusts you 100% and there is no need to prove that the draw was carried out properly, then you can safely use the free service and just show all participants a screenshot with the results of the draw. If there is a need for official confirmation of the selection, then below I will tell you how to choose a winner for a fee.

Free Picks

So, if your audience trusts you, then there is no need to pay for the sample. In this video you will learn how to choose a random winner in two free ways:

1. Using a random number generator;
2. Using the randomizer lists.

Paid selection

If you are conducting a competition with a large number of participants or large prizes, then most likely you will be more interested in the official selection with the preservation of the results of the draw.

Rates

The sample price on random.org depends on the number of participants. If you have no more than 500 people in the list, then such a selection will cost you quite inexpensively - $ 4.95. 1000 participants will cost a little more - $ 8.95. I will not give all the prices here, especially since they are on the site. The price for a sample with a small number of participants at random.org is slightly lower than that of its competitors, for example, Random Picker. But if you have more than 3,000 participants, then I advise you to use the site, since it has a fixed price for the project - $ 25 (the more projects, the cheaper). In addition, the site has been translated into Russian, which is undoubtedly a big plus.

If you have no problems with the English language and you can easily register on the site, then just skip this section. I got a lot of questions about registering at random.org, so I'll tell you how to do it.

Step 1.  Click on Login in the upper right corner and in the window that opens, click on register.

Step 2  Enter the data for registration, as shown in the figure below. Note that the name that you put in the second paragraph will be indicated in the selection protocol, so choose either your name or the name of your company, page or site. Click on the Proceed button.

Step 3  Next, you need to choose how much you will pay for the sample. If you have less than 500 participants, then select the second line with a price of $ 4.95 - this is the minimum amount for registration. That is, if you just want to register on the site without payment (1st line) - you won’t succeed. I don’t know why they even made such an option.

Further, if you have about 5,000 participants or you want to hold several lotteries with fewer participants, then choose the third line with a price of $ 34.95. The same thing with the fourth row - $ 249.95 per 100,000 participants or a small number of small samples.

The most efficient options offered by random.org are the second with $ 4.95 or the last, where you yourself choose how much money you want to deposit. Do not forget to use the price calculator, the link to which I gave above.

Step 4 This step is not at all interesting for us. random.org asks if you want to subscribe to the optional service "Custom random number generator." For competitions, you will not need it, so select the first line.

Step 5  Well, the last step is confirmation of the account. Pay particular attention to the fact that you entered the correct email. address, since a password will be sent to you to enter your account.

If payment information and email address If the e-mail address is entered correctly, then check the box to confirm that you agree with everything, and click on the Pay with PayPal button. You will be redirected to pay on the PayPal page. Once the money has been credited to your random.org account, your account will be created.

That's all! Registration is finished!

Official winner selection at random.org

In this section, we will take a detailed look at how to determine the winner on random.org. For an example I will use screenshots from the random.org site.

Step 1.  Log in to your account.

Step 2  A window will open, as in the figure, with information about all previous selections (if they were of course). Click on the “choose a new winner” button.

Step 3  In the new window, enter the name of the contest or a brief description of it.

1. The results will be visible only to the participants of the competition:  In order to check whether the participant was included in the list, he will need to enter an identifier, that is, the information that you used in the lists, for example, names, email addresses. mail, UID and so on. The participant will be able to see only general information about the draw: name, total number of participants, but will not be able to see the entire list. .
2. Closed Sample:  The results of the selection and the list of participants are available only to you.
3. Open Sample:  the results of the selection and the list of participants will be visible to anyone who clicks on the protocol link. .
4. Test sample.

Step 4  Next, select the method of entering the list of participants. Everything seems to be clear here. I only note that if you choose the method of downloading the file, the list should be in txt text format. For both methods - each individual participant must be entered on a separate line, that is, no enumeration, separated by commas or by spaces.

If you have a very large number of participants, then downloading and processing the file may take longer.

Step 5 You do not need to do anything in this step, as random.org will do everything by itself. The essence of this step is to check your list for duplicates and empty fields. If the fields highlighted in yellow in the picture are green, then random.org did not find any problems with the list. If your list has duplicates or empty fields, then you will have to go back, correct these shortcomings and reload the list of participants. If you have everything in order with the list, then go ahead by clicking on Proceed.

Step 7  Next, we move on to the sampling confirmation step. Be very careful that all the information is entered correctly, since at this stage there is still a chance to return and correct something. If you click on the Complete the drawing button (make a selection), then money will be debited from your account.

Step 8  The list of winners is ready! If you have determined the open type of selection, that is, made the results available to the general public or to participants, then on this page you will see a link that you can publish at the venue of the competition. There is no need to save this link, as you can find it in the control panel of your account.

Well, it seems, and that’s all, friends, that I wanted to tell you and show you about random.org. I really hope that you found the information you were looking for. I would be grateful if you share my article with everyone who can find this information useful and interesting.

If you have not subscribed to the blog updates, then you can do this at this link. Do not forget to follow the latest news in the social. networks.

And so on, and used by account owners to attract a new audience to the community.

The result of such draws often depends on the user's luck, as the recipient of the prize is determined randomly.

For such a definition, the organizers of the draws almost always use a random number generator online or pre-installed, distributed free of charge.

The choice

Quite often, choosing such a generator can be difficult, since their functionality is quite different - for some it is significantly limited, for others it is quite wide.

A fairly large number of such services are implemented, but the difficulty is that they differ in scope.

Many, for example, are tied with their functionality to a specific social network (for example, many generator applications only work with this link).

The simplest generators simply randomly determine a number in a given range.

This is convenient because it does not associate the result with a specific post, which means that they can be used when drawing outside the social network and in various other situations.

In fact, they have no other use.

Advice!  When choosing the most suitable generator, it is important to consider what purpose it will be used for.

Specifications

For the fastest process of choosing the optimal online random number generation service, the table below shows the main technical characteristics and functionality of such applications.

In more detail all applications considered in the table are described below.

Randstuff

You can use this application online using the link to its official website http://randstuff.ru/number/.

This is a simple random number generator, characterized by fast and stable operation.

It is successfully implemented both in the form of a separate stand-alone application on the official website, and as an application in.

The peculiarity of this service is that it can select a random number both from the specified range and from a specific list of numbers that can be specified on the site.

• Stable and fast work;
• Lack of direct connection to a social network;
• You can choose one or several numbers;
• You can choose only among the specified numbers.

User reviews about this application are as follows: “We determine through this service the winners in Vkontakte groups. Thank you "," You are the best "," I use only this service. "

Cast lots

This application is a simple functional generator, implemented on the official website, as a VK application.

There is also a generator widget to embed on your site.

The main difference from the previous described application is that it allows you to disable the repetition of the result.