Pseudorandom numbers. Generating random numbers in .NET Equiprobable random numbers

Rand generated 10 random numbers for us. You can verify that they are random by running the program again and again. But this is not enough, so we need to talk about range.

Set range boundaries for rand()

To generate a number in the range from A to B inclusive, you need to write this:

A + rand() % ((B + 1) - A);

Boundary values ​​can also be negative, which allows you to generate a negative random number, let's look at an example.

#include #include #include using namespace std; int main() ( srand(time(NULL)); int A = -2; int B = 8; for(int i = 0; i< 100; i++) { cout << A + rand() % ((B + 1) - A) << endl; } return 0; }

Tags: C random, C random numbers, random number generation, RNG, pseudo-random numbers, Monte Carlo method

Pseudorandom numbers

Generating pseudorandom numbers is a complex mathematical problem. This article does not set out to cover this topic. In what follows, the concept of “random number” will mean pseudo-random, unless otherwise specified.

You come across examples of the use of random numbers everywhere. Pseudorandom numbers are used in design and graphics, to generate levels in computer games and to simulate AI. Sets of random numbers are used in mathematical algorithms (see Monte Carlo methods).

Obviously, the problem of generating random numbers cannot be solved on a classical processor, since the operation of a computer is deterministic by definition. However, it is possible to generate very long sets of numbers such that their distribution has the same properties as sets of truly random numbers.

It is important that to solve a particular problem you need to choose the right generator, or at least know its properties. For example, when modeling a physical process, you can get completely different and often incorrect results, depending on the choice of random number generator.

Let's look at a standard generator.

#include #include #include int main() ( int i, r; srand(42); for (i = 0; i< 10; i++) { r = rand(); printf("%d\n", r); } _getch(); return 0; }

First, you need to initialize the random number generator (RNG, or RNG - random number generator), set the seed, on the basis of which the generation will take place in the future. It is important that for the same initial value the generator will return the same numbers.

Srand(42);

Assign variable r a random value

R = rand();

The value will be in the range from 0 to RAND_MAX.

In order to get a new set of numbers the next time you start, you need to initialize the generator with different values ​​each time. For example, you can use the system time:

Srand(time(NULL));

Srand(_getpid());

The getpid function of the process.h library returns the process ID (you can also use getpid, the non-POSIX version of the function).

Central Limit Theorem

It is very important to immediately remind or introduce the central limit theorem. Informal definition: the distribution of a sum of weakly dependent random variables tends to normal. Finger-shaped explanation: if you add several random variables, regardless of their distribution, the distribution of the sum will be normal. You can often see code like this

#include #include #include int main() ( int i, r, r1, r2, r3; srand(time(NULL)); r1 = rand(); r2 = rand(); r3 = rand(); r = (r1 + r2 + r3 ) / 3; printf("%d", r);

Generating random numbers on a given interval

First, we get a random number from zero to one:

Const float RAND_MAX_F = RAND_MAX; float get_rand() ( return rand() / RAND_MAX_F; )

To get a number in the interval from zero to N, multiply N by a random number from zero to one. To obtain a random number from M to N, we shift the resulting number by M.

Float get_rand_range(const float min, const float max) ( return get_rand() * (max - min) + min; )

To obtain an integer, we will take the remainder of division by the length of the interval. But the remainder of the division will return a number one less than our interval, so we increase it by one:

Int get_rand_range_int(const int min, const int max) ( return rand() % (max - min + 1) + min; )

An example of using random numbers to calculate an integral. Let us have some smooth function of one variable. Let's limit it to a square from a to b, and from 0 to some point, which is obviously larger than our function.

We will randomly throw points on our square. If they lie above the function (shown as green crosses in the figure), then we will assign them to the first group A, if below the function (red in the figure), then we will assign them to the second group B. The position of the points is random and distributed evenly (since the standard the generator gives a uniform distribution. This simple example, by the way, already shows how important it is to know the properties of the RNG). Then the ratio of red dots to the total number of dots will be equal to the ratio of the area under the graph to the total area. And the total area is the square (b-a) by q.

Src="/images/c_random_integral.png" alt=" Everything that randomly falls above our function is green, everything below is red.
The ratio of green to red will be equal to the ratio of the area above the graph to the area below the graph."> Всё, что случайно попадает выше нашей функции - зелёное, всё что ниже - красное. !}
The ratio of green to red will be equal to the ratio of the area above the graph to the area below the graph.

Let's apply our calculations - find the integral of the function x^2 on the interval from 0 to two in two ways.

#include #include #include #include #include const float RAND_MAX_F = RAND_MAX; float get_rand() ( return rand() / RAND_MAX_F; ) float get_rand_range(const float min, const float max) ( return get_rand() * (max - min) + min; ) #define ROUNDS 1000 float fun(float x) ( return x * x; ) float square_square(float a, float b, float q) ( float h = (b - a) / (float)ROUNDS; float sum = 0; for (; a< b; a += h) { sum += fun(a) * h; } return sum; } float rand_square(float a, float b, float q) { float res; float x, y; int i; int lower = 0; float ratio; float square; srand(time(NULL)); for (i = 0; i < ROUNDS; i++) { x = get_rand_range(a, b); y = get_rand_range(0, q); res = fun(x); if (res >y) ( lower++; ) ) ratio = (float)lower / (float)ROUNDS;

square = (b - a) * q * ratio;

return square; ) int main() ( float abs_ans = 2.66667f; float sr = rand_square(0, 2, 4); float ss = square_square(0, 2, 4); printf("Rounds = %d\n", ROUNDS); printf("Sa = %.5f\n", abs_ans); printf("Sr = %.5f\n", sr); printf("Ss = %.5f\n", ss); %.5f\n", fabs(sr - abs_ans)); printf("ds = %.5f\n", fabs(ss - abs_ans)); _getch(); return 0; )

To generate real random numbers, generators based on some random physical processes are used. For example, on thermal noise, on counting the number of fissions of a radioactive substance, on atmospheric noise, etc. The disadvantage of such generators is their low operating speed (the number of generated numbers per second); of course, such generators are usually a separate device.

Very often in programs there is a need to use random numbers - from filling an array to cryptography. To obtain a sequence of random numbers, the C# language has the Random class. This class provides two constructors:

• Random()- initializes an instance of the Random class with an initial value that depends on the current time. As is known, time can be represented in ticks- 100 nanosecond pulses starting January 1, 0001. And the time value in ticks is a 64-bit integer, which will be used to initialize the random number generator instance.
• Random(Int32)- initializes an instance of the Random class using the specified initial value. Initializing a random number generator in this way can be convenient when debugging a program, since in this case the same “random” numbers will be generated each time the program is launched.

• Next() - returns a random non-negative integer in Int32 format.
• Next( Int32)- returns a random non-negative integer that is less than the specified value.
• Next( Int32 min, Int32 max)- returns a random integer in the specified range. In this case, the condition min must be met

• NextBytes( Byte)- fills the elements of the specified byte array with random numbers.
• NextDouble() - returns a random floating point number, in the range )
  break ; // match found, element does not match
  }
  if (j == i)
  { // no match found
  a[i] = num; // save the element
  i++; // go to the next element
  }
  }
  for (int i = 0; i< 100; i++)
  {
  
  if (i % 10 == 9)
  Console.WriteLine();
  }
  Console .ReadKey();
  }
  }
  }

  

  However, the closer to the end of the array, the more generations must be performed to obtain a non-repeating value.
  The following example displays the number of calls to the Next() method to obtain each element, as well as the total number of random numbers generated to fill a 100-element array with non-repeating values.

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53

  using System;
  namespace MyProgram
  {
  class Program
  {
  static void Main(string args)
  {
  Random rnd = new Random();
  int a = new int ; // array of elements
  int count = new int ; // array of number of generations
  a = rnd.Next(0, 101);
  int c = 0; // counter of the number of generations
  count = 1; // a is generated only once
  for (int i = 1; i< 100;)
  {
  int num = rnd.Next(0, 101);
  c++; // generated the element one more time
  int j;
  for (j = 0; j< i; j++)
  {
  if (num == a[j])
  break ;
  }
  if (j == i)
  {
  a[i] = num; i++;
  count[i] = c; c = 0; // save the number of generations
  }
  }
  // Printing element values
  Console .WriteLine( "Element Values");
  for (int i = 0; i< 100; i++)
  {
  Console .Write("(0,4) " , a[i]);
  if (i % 10 == 9)
  Console.WriteLine();
  }
  Console.WriteLine();
  // Display the number of generations
  Console .WriteLine( "Number of element generation");
  int sum = 0;
  for (int i = 0; i< 100; i++)
  {
  sum += count[i];
  Console .Write("(0,4) " , count[i]);
  if (i % 10 == 9)
  Console.WriteLine();
  }
  Console .WriteLine( "Total number of generations - (0)", sum);
  Console .ReadKey();
  }
  }
  }
  

  void Main(string args)
  {
  Random rnd = new Random();
  int a = new int ;
  for (int i = 0; i< 100; i++)
  a[i] = i;
  for (int i = 0; i< 50; i++)
  {
  int i1 = rnd.Next(0, 100); // first index
  int i2 = rnd.Next(0, 100); // second index
  // exchange of values ​​of elements with indices i1 and i2
  int temp = a;
  a = a;
  a = temp;
  }
  Console .WriteLine( "Element Values");
  for (int i = 0; i< 100; i++)
  {
  Console .Write("(0,4) " , a[i]);
  if (i % 10 == 9)
  Console.WriteLine();
  }
  Console .ReadKey();
  }
  }
  }

  

  Shuffling values ​​is more effective if the range of values ​​matches (or is close to) the number of values, since in this case the number of random element generation is significantly reduced.

  Translation of the article Random numbers by Jon Skeete, widely known in narrow circles. I stopped at this article because at one time I myself encountered the problem described in it.

  Browsing topics by .NET And C# on the StackOverflow website, you can see countless questions mentioning the word “random”, which, in fact, raise the same eternal and “indestructible” question: why does the System.Random random number generator “not work” and how to “fix it” " This article is devoted to consideration of this problem and ways to solve it.

  Formulation of the problem

  On StackOverflow, in newsgroups and mailing lists, all questions on the topic “random” sound something like this:
  

  I'm using Random.Next to generate multiple random numbers, but the method returns the same number when called multiple times. The number changes each time the application is launched, but within one execution of the program it is constant.
  

  
  An example code is something like this:
  // Bad code! Do not use! for (int i = 0; i< 100; i++) { Console.WriteLine(GenerateDigit()); } ... static int GenerateDigit() { Random rng = new Random(); // Предположим, что здесь много логики return rng.Next(10); }
  So what's wrong here?

  Explanation

  The Random class is not a true random number generator, it contains a generator pseudo random numbers. Each instance of the Random class contains some internal state, and when the Next (or NextDouble, or NextBytes) method is called, the method uses that state to return a number that will appear random. The internal state is then changed so that the next time Next is called, it will return a different seemingly random number than the one previously returned.

  All the “internals” of the Random class completely deterministic. This means that if you take several instances of the Random class with the same initial state, which is specified through the constructor parameter seed, and for each instance call certain methods in the same order and with the same parameters, then in the end you will get the same results.

  So what's wrong with the above code? The bad thing is that we use a new instance of the Random class inside each iteration of the loop. The Random constructor, which takes no parameters, takes the current date and time as its seed. The iterations in the loop will “scroll” so quickly that the system time “will not have time to change” upon their completion; thus, all instances of Random will receive the same value as their initial state and will therefore return the same pseudo-random number.

  How to fix it?

  There are many solutions to the problem, each with its own pros and cons. We'll look at a few of them.

  Using a Cryptographic Random Number Generator

  .NET contains an abstract class RandomNumberGenerator from which all implementations of cryptographic random number generators (hereinafter referred to as cryptoRNGs) must inherit. .NET also contains one of these implementations - meet the RNGCryptoServiceProvider class. The idea of ​​a crypto-RNG is that even if it is still a pseudo-random number generator, it provides a fairly strong unpredictability of results. RNGCryptoServiceProvider uses several sources of entropy, which are essentially "noise" in your computer, and the sequence of numbers it generates is very difficult to predict. Moreover, "in-computer" noise can be used not only as an initial state, but also between calls to subsequent random numbers; thus, even knowing the current state of the class, it will not be enough to calculate both the next numbers that will be generated in the future, and those that were generated previously. In fact, the exact behavior is implementation dependent. In addition, Windows can use specialized hardware that is a source of "true randomness" (for example, a radioactive isotope decay sensor) to generate even more secure and reliable random numbers.

  Let's compare this with the previously discussed Random class. Let's say you called Random.Next(100) ten times and saved the results. If you have enough computing power, you can, based solely on these results, calculate the initial state (seed) with which the Random instance was created, predict the next results of calling Random.Next(100), and even calculate the results of previous method calls. This behavior is extremely unacceptable if you are using random numbers for security, financial purposes, etc. Crypto RNGs operate significantly slower than the Random class, but they generate a sequence of numbers, each of which is more independent and unpredictable from the values ​​of the others.

  In most cases, poor performance isn't a deal breaker - a bad API is. RandomNumberGenerator is designed to generate sequences of bytes - that's all. Compare this with the methods of the Random class, where it is possible to obtain a random integer, fractional number, and also a set of bytes. Another useful property is the ability to obtain a random number in a specified range. Compare these possibilities with the array of random bytes that RandomNumberGenerator produces. You can correct the situation by creating your own wrapper (wrapper) around RandomNumberGenerator, which will convert random bytes into a “convenient” result, but this solution is non-trivial.

  However, in most cases, the "weakness" of the Random class is fine if you can solve the problem described at the beginning of the article. Let's see what we can do here.

  Use one instance of the Random class for multiple calls

  Here it is, the root of the solution to the problem is to use only one instance of Random when creating many random numbers using Random.Next. And it's very simple - see how you can change the above code:
  // This code will be better Random rng = new Random(); for (int i = 0; i< 100; i++) { Console.WriteLine(GenerateDigit(rng)); } ... static int GenerateDigit(Random rng) { // Предположим, что здесь много логики return rng.Next(10); }
  Now each iteration will have different numbers... but that's not all. What happens if we call this block of code twice in a row? That's right, we'll create two Random instances with the same seed and get two identical sets of random numbers. The numbers in each set will be different, but these sets will be equal among themselves.

  There are two ways to solve the problem. Firstly, we can use not an instance, but a static field containing an instance of Random, and then the above piece of code will create only one instance, and will use it, calling it as many times as necessary. Secondly, we can completely remove the creation of a Random instance from there, moving it “higher”, ideally to the very “top” of the program, where a single Random instance will be created, after which it will be transmitted to all places where random numbers are needed. This is a great idea, nicely expressed by dependencies, but it will work as long as we only use one thread.

  Thread safety

  The Random class is not thread safe. Considering how much we like to create a single instance and use it throughout a program for the entire duration of its execution (singleton, hello!), the lack of thread safety becomes a real pain in the ass. After all, if we use one instance simultaneously in several threads, then there is a possibility that its internal state will be reset, and if this happens, then from that moment on the instance will become useless.

  Again, there are two ways to solve the problem. The first path still involves using a single instance, but this time using resource locking via a monitor. To do this, you need to create a wrapper around Random that will wrap calls to its methods in a lock statement, ensuring exclusive access to the instance for the caller. This path is bad because it reduces performance in thread-intensive scenarios.

  Another way, which I will describe below, is to use one instance per thread. The only thing we need to make sure is that we use different seeds when creating instances, so we can't use default constructors. Otherwise, this path is relatively straightforward.

  Secure provider

  Fortunately, the new generic class ThreadLocal , introduced in .NET 4, makes it very easy to write providers that provide one instance per thread. You just need to pass a delegate to the ThreadLocal constructor, which will refer to getting the value of our instance itself. In this case, I decided to use a single seed value, initializing it using Environment.TickCount (which is how the parameterless Random constructor works). Next, the resulting number of ticks is incremented every time we need to get a new Random instance for a separate thread.

  The class presented below is completely static and contains only one public (open) method GetThreadRandom. This method is made a method rather than a property, mainly for convenience: this will ensure that all classes that need an instance of Random will depend on Func (a delegate pointing to a method that takes no parameters and returns a value of type Random), and not from the Random class itself. If a type is intended to run on a single thread, it can call a delegate to obtain a single instance of Random and then use it throughout; if the type needs to work in multi-threaded scenarios, it can call the delegate every time it needs a random number generator. The class below will create as many instances of the Random class as there are threads, and each instance will start from a different initial value. If we need to use the random number provider as a dependency in other types, we can do this: new TypeThatNeedsRandom(RandomProvider.GetThreadRandom) . Well, here is the code itself:
  using System; using System.Threading; public static class RandomProvider ( private static int seed = Environment.TickCount; private static ThreadLocal randomWrapper = new ThreadLocal (() => new Random(Interlocked.Increment(ref seed)));
  public static Random GetThreadRandom() ( return randomWrapper.Value; ) )

  Simple enough, right? This is because all the code is aimed at producing the correct instance of Random. Once an instance is created and returned, it doesn’t matter what you do with it next: all further issuances of instances are completely independent of the current one. Of course, the client code has a loophole for malicious misuse: it can take one instance of Random and pass it to other threads instead of calling our RandomProvider on those other threads.

  Interface design problems

  It would be very nice if RNG providers in the framework had separate “sources of randomness”. In this case, we could have a single, simple and convenient API that would be supported by both the insecure-but-fast implementation and the secure-but-slow one. Well, there's no harm in dreaming. Perhaps similar functionality will appear in future versions of the .NET Framework. Perhaps someone not from Microsoft will offer their own implementation of the adapter. (Unfortunately, I won't be that person...implementing something like this correctly is surprisingly complex.) You can also create your own class by deriving from Random and overriding the Sample and NextBytes methods, but it's not clear exactly how they should work, or even your own Implementing Sample can be much more complex than it seems. Maybe next time…