Generating Random Numbers in .NET
Translation of the article Random numbers widely known in narrow circles of John Skit. I stopped at this article, because in my time I ran into the problem described in it.
Looking through the topics on .NET and C # on StackOverflow, you can see countless questions mentioning the word “random”, in which, in fact, the same eternal and “unkillable” question is raised: why the System.Random random number generator “does not It works and how to fix it. This article is devoted to the consideration of this problem and how to solve it.
On StackOverflow, in newsgroups and mailings, all questions on the topic “random” sound like this:
As an example of code, the following is given:
So what is wrong here?
The Random class is not a true random number generator; it contains a pseudo random number generator. Each instance of the Random class contains some internal state, and when calling the Next method (or NextDouble , or NextBytes ), the method uses this state to return a number that appears random. After that, the internal state is changed so that the next time you call the Next method, it returns another seemingly random number that is different from the one returned earlier.
All the "insides" of the class Random are completely deterministic . This means that if you take several instances of the Random class with the same initial state, which is set through the parameter of the seed constructor, 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 class Random within each iteration of the loop. The Random constructor, which takes no parameters , accepts the current date and time as a seed (the initial state). Iterations in the cycle "scroll" so quickly that the system time "does not have time to change" after they end; thus, all Random instances will get the same value as the initial state and therefore will return the same pseudo-random number.
There are many solutions to the problem, each with its own pros and cons. We will look at a few of them.
.NET contains the abstract class RandomNumberGenerator , from which all implementations of cryptographic random number generators (hereinafter, cryptoGSS) should be inherited. One of such implementations contains and .NET - meet the class RNGCryptoServiceProvider . The idea of ​​cryptoGSS is that even if it is still a pseudo-random number generator, it provides a rather unpredictable result. RNGCryptoServiceProvider uses several sources of entropy, which are actually “noises” in your computer, and the sequence of numbers it generates is very difficult to predict. Moreover, “intracomputer” noise can be used not only as an initial state, but also between calls to the following random numbers; thus, even knowing the current state of the class, this is not enough for calculating both the following numbers that will be generated in the future and those that were generated earlier. In fact, the exact behavior depends on the implementation. In addition, Windows can use specialized hardware, which is the source of “true coincidences” (for example, it can be a radioactive isotope decay sensor) to generate even more protected and reliable random numbers.
Compare this with the previously considered class Random. Suppose you called Random.Next (100) ten times and saved the results. If you have enough computational power, then, based solely on these results, you can calculate the initial state (seed) with which the Random instance was created, predict the following results of the Random.Next call (100) and even calculate the results of previous method calls. This behavior is disastrously unacceptable if you use random numbers for security, for financial purposes, etc. CryptoGSCH work significantly slower than the Random class, but generate a sequence of numbers, each of which is more independent and unpredictable from the values ​​of the others.
In most cases, lower performance is not an obstacle - it is a bad API. RandomNumberGenerator is designed to generate sequences of bytes - that's all. Compare this with the methods of the class Random, where there is the possibility of obtaining a random integer number, a fractional number, and a set of bytes. Another useful feature is the possibility of obtaining a random number in the specified range. Compare these possibilities with the random byte array that the RandomNumberGenerator produces. You can rectify the situation by creating your own wrapper (wrapper) around the RandomNumberGenerator, which will convert random bytes into a “convenient” result, but this solution is nontrivial.
However, in most cases, the “weakness” of the Random class is quite appropriate if you can solve the problem described at the beginning of the article. Let's see what can be done here.
Here it is, the root of the solution to the problem is to use only one instance of Random when creating a set of random numbers using Random.Next. And it's very simple - see how you can change the above code:
Now in each iteration there will be different numbers, ... but that's not all. What happens if we call this block of code two times in a row? That's right, we will create two Random instances with the same initial value and get two identical sets of random numbers. In each set the numbers will differ, but between them these sets will be equal.
There are two ways to solve the problem. First, we can use a non-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, invoking it as many times as necessary. Secondly, we can generally remove from there the creation of the Random instance, moving it “higher”, ideally to the very “top” of the program, where a single Random instance will be created, after which it will be transferred to all places where random numbers are needed. This is a great idea, which is beautifully expressed by dependencies, but it will work as long as we use only one thread.
The class Random is not thread safe. Considering how we like to create one copy and use it throughout the program throughout the entire time it is executed (singleton, hello!), The absence of thread-safety becomes a real thorn. After all, if we use one instance at the same time in several streams, then there is a probability that its internal state will be reset, and if this happens, then from that moment the instance will become useless.
Again, there are two ways to solve the problem. The first path still assumes the use of a single instance, however this time using the lock of the resource through the monitor. To do this, you need to create a wrapper around Random, which will wrap the call to its methods in the lock statement, which provides exclusive access to the instance for the caller. This path is bad because it reduces performance in multi-threaded scenarios.
Another way that I will describe below is to use one instance for each stream. The only thing we need to make sure that when creating instances, we use different initial values ​​(seed), and therefore we can not use the default constructors. Otherwise, this path is relatively straightforward.
Fortunately, the new generic class ThreadLocal <T> , which appeared in .NET 4, greatly facilitates the writing of 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 initial value (seed), initializing it with the help of Environment.TickCount (this is how the Random constructor works without parameters). Further, the received number of ticks is incremented each time we need to get a new Random instance for a separate stream.
The class below is completely static and contains only one public (open) method GetThreadRandom. This method is made by method rather than property, mainly due to convenience: thanks to this, all classes that need a Random instance will depend on Func <Random> (delegate pointing to a method that takes no parameters and returns a value of type Random) not from the Random class itself. If a type is designed to work in one stream, it can call a delegate to get a single instance of Random and then use it everywhere; if the type should work in multi-threaded scenarios, it can call a delegate whenever 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 with a different initial value. If we need to use a random number provider as a dependency in other types, we can do this:
Simple enough, isn't it? That's because all the code is aimed at issuing the correct instance of Random. After the copy is created and returned, it is completely unimportant what you will do with it further: all further copies of the copies are completely independent of the current one. Of course, the client code has a loophole for malicious misuse: it can get one instance of Random and transfer it to other threads instead of calling to those other threads of our RandomProvider.
One problem still remains: we use a weakly protected random number generator. As mentioned earlier, there is a much safer in all respects version of the RNG in the RandomNumberGenerator, whose implementation is in the RNGCryptoServiceProvider class. However, its API is quite difficult to use in standard scripts.
It would be very nice if the RNG providers in the framework had separate “sources of randomness”. In this case, we could have a single, simple and convenient API, which would be supported by both unsafe-but-fast and safe-but-slow implementations. Well, dreaming is not bad. Perhaps this functionality will appear in the next versions of the .NET Framework. Probably, someone not from Microsoft will offer the implementation of the adapter. (Unfortunately, I will not be this someone ... the correct implementation of such an idea is surprisingly difficult.) You can also create your own class by inheriting it from Random and overriding the Sample and NextBytes methods, but it’s unclear exactly how they should work, and even Sample implementation can be much more complicated than it seems. Maybe next time…
Looking through the topics on .NET and C # on StackOverflow, you can see countless questions mentioning the word “random”, in which, in fact, the same eternal and “unkillable” question is raised: why the System.Random random number generator “does not It works and how to fix it. This article is devoted to the consideration of this problem and how to solve it.
Formulation of the problem
On StackOverflow, in newsgroups and mailings, all questions on the topic “random” sound like this:
I use Random.Next to generate multiple random numbers, but the method returns the same number when it is called multiple times. The number changes each time the application is started, but within the framework of one program execution it is constant.
As an example of code, the following is given:
// ! ! for (int i = 0; i < 100; i++) { Console.WriteLine(GenerateDigit()); } ... static int GenerateDigit() { Random rng = new Random(); // , return rng.Next(10); } So what is wrong here?
Explanation
The Random class is not a true random number generator; it contains a pseudo random number generator. Each instance of the Random class contains some internal state, and when calling the Next method (or NextDouble , or NextBytes ), the method uses this state to return a number that appears random. After that, the internal state is changed so that the next time you call the Next method, it returns another seemingly random number that is different from the one returned earlier.
All the "insides" of the class Random are completely deterministic . This means that if you take several instances of the Random class with the same initial state, which is set through the parameter of the seed constructor, 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 class Random within each iteration of the loop. The Random constructor, which takes no parameters , accepts the current date and time as a seed (the initial state). Iterations in the cycle "scroll" so quickly that the system time "does not have time to change" after they end; thus, all Random instances will get the same value as the initial state and therefore will 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 will look at a few of them.
Using a cryptographic random number generator
.NET contains the abstract class RandomNumberGenerator , from which all implementations of cryptographic random number generators (hereinafter, cryptoGSS) should be inherited. One of such implementations contains and .NET - meet the class RNGCryptoServiceProvider . The idea of ​​cryptoGSS is that even if it is still a pseudo-random number generator, it provides a rather unpredictable result. RNGCryptoServiceProvider uses several sources of entropy, which are actually “noises” in your computer, and the sequence of numbers it generates is very difficult to predict. Moreover, “intracomputer” noise can be used not only as an initial state, but also between calls to the following random numbers; thus, even knowing the current state of the class, this is not enough for calculating both the following numbers that will be generated in the future and those that were generated earlier. In fact, the exact behavior depends on the implementation. In addition, Windows can use specialized hardware, which is the source of “true coincidences” (for example, it can be a radioactive isotope decay sensor) to generate even more protected and reliable random numbers.
Compare this with the previously considered class Random. Suppose you called Random.Next (100) ten times and saved the results. If you have enough computational power, then, based solely on these results, you can calculate the initial state (seed) with which the Random instance was created, predict the following results of the Random.Next call (100) and even calculate the results of previous method calls. This behavior is disastrously unacceptable if you use random numbers for security, for financial purposes, etc. CryptoGSCH work significantly slower than the Random class, but generate a sequence of numbers, each of which is more independent and unpredictable from the values ​​of the others.
In most cases, lower performance is not an obstacle - it is a bad API. RandomNumberGenerator is designed to generate sequences of bytes - that's all. Compare this with the methods of the class Random, where there is the possibility of obtaining a random integer number, a fractional number, and a set of bytes. Another useful feature is the possibility of obtaining a random number in the specified range. Compare these possibilities with the random byte array that the RandomNumberGenerator produces. You can rectify the situation by creating your own wrapper (wrapper) around the RandomNumberGenerator, which will convert random bytes into a “convenient” result, but this solution is nontrivial.
However, in most cases, the “weakness” of the Random class is quite appropriate if you can solve the problem described at the beginning of the article. Let's see what can be done here.
Use one instance of 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 a set of random numbers using Random.Next. And it's very simple - see how you can change the above code:
// 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 in each iteration there will be different numbers, ... but that's not all. What happens if we call this block of code two times in a row? That's right, we will create two Random instances with the same initial value and get two identical sets of random numbers. In each set the numbers will differ, but between them these sets will be equal.
There are two ways to solve the problem. First, we can use a non-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, invoking it as many times as necessary. Secondly, we can generally remove from there the creation of the Random instance, moving it “higher”, ideally to the very “top” of the program, where a single Random instance will be created, after which it will be transferred to all places where random numbers are needed. This is a great idea, which is beautifully expressed by dependencies, but it will work as long as we use only one thread.
Thread safety
The class Random is not thread safe. Considering how we like to create one copy and use it throughout the program throughout the entire time it is executed (singleton, hello!), The absence of thread-safety becomes a real thorn. After all, if we use one instance at the same time in several streams, then there is a probability that its internal state will be reset, and if this happens, then from that moment the instance will become useless.
Again, there are two ways to solve the problem. The first path still assumes the use of a single instance, however this time using the lock of the resource through the monitor. To do this, you need to create a wrapper around Random, which will wrap the call to its methods in the lock statement, which provides exclusive access to the instance for the caller. This path is bad because it reduces performance in multi-threaded scenarios.
Another way that I will describe below is to use one instance for each stream. The only thing we need to make sure that when creating instances, we use different initial values ​​(seed), and therefore we can not use the default constructors. Otherwise, this path is relatively straightforward.
Secure provider
Fortunately, the new generic class ThreadLocal <T> , which appeared in .NET 4, greatly facilitates the writing of 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 initial value (seed), initializing it with the help of Environment.TickCount (this is how the Random constructor works without parameters). Further, the received number of ticks is incremented each time we need to get a new Random instance for a separate stream.
The class below is completely static and contains only one public (open) method GetThreadRandom. This method is made by method rather than property, mainly due to convenience: thanks to this, all classes that need a Random instance will depend on Func <Random> (delegate pointing to a method that takes no parameters and returns a value of type Random) not from the Random class itself. If a type is designed to work in one stream, it can call a delegate to get a single instance of Random and then use it everywhere; if the type should work in multi-threaded scenarios, it can call a delegate whenever 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 with a different initial value. If we need to use a 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<Random> randomWrapper = new ThreadLocal<Random>(() => new Random(Interlocked.Increment(ref seed)) ); public static Random GetThreadRandom() { return randomWrapper.Value; } } Simple enough, isn't it? That's because all the code is aimed at issuing the correct instance of Random. After the copy is created and returned, it is completely unimportant what you will do with it further: all further copies of the copies are completely independent of the current one. Of course, the client code has a loophole for malicious misuse: it can get one instance of Random and transfer it to other threads instead of calling to those other threads of our RandomProvider.
Interface design issues
One problem still remains: we use a weakly protected random number generator. As mentioned earlier, there is a much safer in all respects version of the RNG in the RandomNumberGenerator, whose implementation is in the RNGCryptoServiceProvider class. However, its API is quite difficult to use in standard scripts.
It would be very nice if the RNG providers in the framework had separate “sources of randomness”. In this case, we could have a single, simple and convenient API, which would be supported by both unsafe-but-fast and safe-but-slow implementations. Well, dreaming is not bad. Perhaps this functionality will appear in the next versions of the .NET Framework. Probably, someone not from Microsoft will offer the implementation of the adapter. (Unfortunately, I will not be this someone ... the correct implementation of such an idea is surprisingly difficult.) You can also create your own class by inheriting it from Random and overriding the Sample and NextBytes methods, but it’s unclear exactly how they should work, and even Sample implementation can be much more complicated than it seems. Maybe next time…
Source: https://habr.com/ru/post/165459/
All Articles