6 ms·

Randomness in .NET

garganzol 8y ago
A useful snippet from the article: "RNGCryptoServiceProvider is generally a safer choice when you need to generate random bytes. Creating an instance of this class is expensive, so it’s better to populate a 400-byte array than call the constructor 100 times to populate a 4-byte array."
- eterm 8y ago
  Both options there feel like the wrong solution. Why would you call the constructor 100 times to popuate 100 4-byte arrays? It's a service, surely the best approach to call the constructor once, then populate 100 4-byte arrays by calling GetBytes 100 times from the same service? It is explicit code without the downside of the expensive constructor. edit for clarification: It's true that getting all the data at once will still be much faster because it'll save all the other overhead, but it's not the constructor at fault there.
Insanity 8y ago
I might be missing something, but the three predicated values are not in the "nextSeed" table? Whereas the original three are. EDIT: I feel like I miss something in the explanation. Can anyone explain how the seed table is actually used?
- Insanity 8y ago
  Edit again: I think I figured it out(?). The previous values are 'recorded' in the seed array, but the last one (2012846163) is what you put the offset to for generating the next one. The next one is generated and in it's turn becomes the 'seed' etc. So the new values wouldn't be in the array _yet_ at the point we inspected. But all we have to do is 'replay' the RNG starting at the 'previous recorded value' to be predicting it correctly?
- lowleveldesign 8y ago
  The seed array is an internal state of the PRNG algorithm. It evolves over time and PRNG uses values from this array (plus some additional parameters, such as inext or inextp) to generate new "random" numbers. Thus, after seeding, there is no real randomness in the non-cryptographic PRNGs. To learn more, have a look at Marsenne Twister, which is also quite popular and has a nice description in Wikipedia [1]. [1] https://en.wikipedia.org/wiki/Mersenne_Twister https://en.wikipedia.org/wiki/Mersenne_Twister
  - Insanity 8y ago
    Thanks for the link! I kind of figured it out over time, but the explanation helps! And thanks for the interesting article btw, just realised you're the author :-)
    - lowleveldesign 8y ago
      Thanks :)
iainmerrick 8y ago
The algorithm used in the .NET Core is the same as in the .NET Framework [...] There is a difference, however, when we use the default constructor. “Core” and “Framework” have different implementations of the same class? Who names these things?
- yawgmoth 8y ago
  .NET Standard is an interface of which .NET Core and .NET Framework are implementations. I agree that it's confusing terminology at first, but for daily drivers of .NET languages, it should be pretty transparent.
  - lovich 8y ago
    As a .NET dev it is transparent, but it makes it incredibly annoying to Google anything. Core and Standard are both words that might show up on any webpage and they both share the name .NET. I've almost started wishing that Microsoft started assigning a reference guid to their products to ease searching about them since many of their products follow the same pattern of having similar names that are only differentiated by a common English word
  - SketchySeaBeast 8y ago
    It's somehow effectively doubled the number of search results for any one topic, only half of which will work. But you're right, for a daily user you learn quickly to treat as another criteria to sift through to get relevant results.
    - deleted 8y ago
      [deleted]
nestorD 8y ago
Two vital information on .Net PRNG : - It is not thread-safe (and might start outputting a serie of 0 when called in parallel) - There is a bug (acknowledged by Microsoft but not fixed for backward compatibility reasons) in the implementation meaning that the generator has an abnormally short period and is, overall, less random looking.
- adrianN 8y ago
  I'm really bummed out over the fact that you can't change the way a random number generator generates numbers because apparently people depend on the exact algorithm.
  - OskarS 8y ago
    It does make some sense. Lets say you're making a game with a procedural world (e.g. something like Minecraft) which the player explores and makes changes to. Instead of storing the entire (potentially infinite) world, you just store the world seed and the changes players make. In that case, if the algorithm underlying the PRNG changes, the entire game would break. There's enough scenarios like this that making a change to a PRNG algorithm is a very dangerous and breaking change. People rely on the fact that, given the same seed, you get the same sequence of values.
    - iainmerrick 8y ago
      You should use your own PRNG in that case. I understand not wanting to change the implementation now, but users should never have assumed it would be stable in the first place.
      - OskarS 8y ago
        I mean, yeah. You probably should. But it's entirely reasonable of a game developer to say "I'm not an expert in random numbers, but Microsoft has lots of smart engineers, I'm sure they did their research and provided a good implementation". The actual answer is that you shouldn't just provide a default "Random" class, you should provide a more general class with a pluggable algorithm.
redcalx 8y ago
I think this is the github issue referred to: https://github.com/dotnet/corefx/issues/23298 https://github.com/dotnet/corefx/issues/23298 I wrote some replacement classes that address all of the known issues, here: https://github.com/colgreen/Redzen/tree/master/Redzen/Random https://github.com/colgreen/Redzen/tree/master/Redzen/Random https://www.nuget.org/packages/Redzen/ https://www.nuget.org/packages/Redzen/
- ygra 8y ago
  > I think this is the github issue referred to I think so, too. Because it was not only referred to, but also linked ;-)
  - redcalx 8y ago
    Heh, fair enough :) Not easy to find though eh (v. similar colour for normal and anchor text).
    - bhandziuk 8y ago
      It was hard to see. It also isn't underlined like a normal link.
zbigniewc 8y ago
Thank you for sharing - I will have to put some work into integrating this with my software that is unfortunately based on a tripleton design pattern, but it's worth the effort.
- lowleveldesign 8y ago
  Oh, tripleton might require a special PRNG: http://dilbert.com/strip/2001-10-25 http://dilbert.com/strip/2001-10-25 :)
japanuspus 8y ago
The blog-post by fuglede with a detailed analysis of the implications of the RNG-bug is well worth a read: https://fuglede.dk/en/blog/bias-in-net-rng/ https://fuglede.dk/en/blog/bias-in-net-rng/
- ygra 8y ago
  Isn't there already bias in that computation because the range for the random numbers includes more even than odd numbers since it's the interval [0, 2147483647)?
  - fuglede 8y ago
    Author here; thanks for the interest! First of all, you're completely right. I do actually mention this fact just before the start of the section "An experiment". Here, the argument is that the bias this odd/even mismatch introduces is orders of magnitudes smaller than what is introduced by the rounding errors; that is, a perfect theoretical RNG drawing from that range would not produce nearly as biased a result (and conversely, if you were to run the snippet in the blog post using `rng.Next(2, int.MaxValue)` or `rng.Next(0, int.MaxValue - 2)`, you wouldn't see the same bias, even though the ranges are still odd/even-biased to about the same extent).

A useful snippet from the article: "RNGCryptoServiceProvider is generally a safer choice when you need to generate random bytes. Creating an instance of this class is expensive, so it’s better to populate a 400-byte array than call the constructor 100 times to populate a 4-byte array."

eterm 8y ago
Both options there feel like the wrong solution. Why would you call the constructor 100 times to popuate 100 4-byte arrays? It's a service, surely the best approach to call the constructor once, then populate 100 4-byte arrays by calling GetBytes 100 times from the same service? It is explicit code without the downside of the expensive constructor. edit for clarification: It's true that getting all the data at once will still be much faster because it'll save all the other overhead, but it's not the constructor at fault there.

Insanity 8y ago

I might be missing something, but the three predicated values are not in the "nextSeed" table? Whereas the original three are. EDIT: I feel like I miss something in the explanation. Can anyone explain how the seed table is actually used?

Insanity 8y ago
Edit again: I think I figured it out(?). The previous values are 'recorded' in the seed array, but the last one (2012846163) is what you put the offset to for generating the next one. The next one is generated and in it's turn becomes the 'seed' etc. So the new values wouldn't be in the array _yet_ at the point we inspected. But all we have to do is 'replay' the RNG starting at the 'previous recorded value' to be predicting it correctly?
lowleveldesign 8y ago
The seed array is an internal state of the PRNG algorithm. It evolves over time and PRNG uses values from this array (plus some additional parameters, such as inext or inextp) to generate new "random" numbers. Thus, after seeding, there is no real randomness in the non-cryptographic PRNGs. To learn more, have a look at Marsenne Twister, which is also quite popular and has a nice description in Wikipedia [1]. [1] https://en.wikipedia.org/wiki/Mersenne_Twister https://en.wikipedia.org/wiki/Mersenne_Twister
- Insanity 8y ago
  Thanks for the link! I kind of figured it out over time, but the explanation helps! And thanks for the interesting article btw, just realised you're the author :-)
  - lowleveldesign 8y ago
    Thanks :)

iainmerrick 8y ago

The algorithm used in the .NET Core is the same as in the .NET Framework [...] There is a difference, however, when we use the default constructor. “Core” and “Framework” have different implementations of the same class? Who names these things?

yawgmoth 8y ago
.NET Standard is an interface of which .NET Core and .NET Framework are implementations. I agree that it's confusing terminology at first, but for daily drivers of .NET languages, it should be pretty transparent.
- lovich 8y ago
  As a .NET dev it is transparent, but it makes it incredibly annoying to Google anything. Core and Standard are both words that might show up on any webpage and they both share the name .NET. I've almost started wishing that Microsoft started assigning a reference guid to their products to ease searching about them since many of their products follow the same pattern of having similar names that are only differentiated by a common English word
- SketchySeaBeast 8y ago
  It's somehow effectively doubled the number of search results for any one topic, only half of which will work. But you're right, for a daily user you learn quickly to treat as another criteria to sift through to get relevant results.
  - deleted 8y ago
    [deleted]

nestorD 8y ago

Two vital information on .Net PRNG : - It is not thread-safe (and might start outputting a serie of 0 when called in parallel) - There is a bug (acknowledged by Microsoft but not fixed for backward compatibility reasons) in the implementation meaning that the generator has an abnormally short period and is, overall, less random looking.

adrianN 8y ago
I'm really bummed out over the fact that you can't change the way a random number generator generates numbers because apparently people depend on the exact algorithm.
- OskarS 8y ago
  It does make some sense. Lets say you're making a game with a procedural world (e.g. something like Minecraft) which the player explores and makes changes to. Instead of storing the entire (potentially infinite) world, you just store the world seed and the changes players make. In that case, if the algorithm underlying the PRNG changes, the entire game would break. There's enough scenarios like this that making a change to a PRNG algorithm is a very dangerous and breaking change. People rely on the fact that, given the same seed, you get the same sequence of values.
  - iainmerrick 8y ago
    You should use your own PRNG in that case. I understand not wanting to change the implementation now, but users should never have assumed it would be stable in the first place.
    - OskarS 8y ago
      I mean, yeah. You probably should. But it's entirely reasonable of a game developer to say "I'm not an expert in random numbers, but Microsoft has lots of smart engineers, I'm sure they did their research and provided a good implementation". The actual answer is that you shouldn't just provide a default "Random" class, you should provide a more general class with a pluggable algorithm.

redcalx 8y ago

I think this is the github issue referred to: https://github.com/dotnet/corefx/issues/23298 https://github.com/dotnet/corefx/issues/23298 I wrote some replacement classes that address all of the known issues, here: https://github.com/colgreen/Redzen/tree/master/Redzen/Random https://github.com/colgreen/Redzen/tree/master/Redzen/Random https://www.nuget.org/packages/Redzen/ https://www.nuget.org/packages/Redzen/

ygra 8y ago
> I think this is the github issue referred to I think so, too. Because it was not only referred to, but also linked ;-)
- redcalx 8y ago
  Heh, fair enough :) Not easy to find though eh (v. similar colour for normal and anchor text).
  - bhandziuk 8y ago
    It was hard to see. It also isn't underlined like a normal link.

zbigniewc 8y ago

Thank you for sharing - I will have to put some work into integrating this with my software that is unfortunately based on a tripleton design pattern, but it's worth the effort.

lowleveldesign 8y ago
Oh, tripleton might require a special PRNG: http://dilbert.com/strip/2001-10-25 http://dilbert.com/strip/2001-10-25 :)

japanuspus 8y ago

The blog-post by fuglede with a detailed analysis of the implications of the RNG-bug is well worth a read: https://fuglede.dk/en/blog/bias-in-net-rng/ https://fuglede.dk/en/blog/bias-in-net-rng/

ygra 8y ago
Isn't there already bias in that computation because the range for the random numbers includes more even than odd numbers since it's the interval [0, 2147483647)?
- fuglede 8y ago
  Author here; thanks for the interest! First of all, you're completely right. I do actually mention this fact just before the start of the section "An experiment". Here, the argument is that the bias this odd/even mismatch introduces is orders of magnitudes smaller than what is introduced by the rounding errors; that is, a perfect theoretical RNG drawing from that range would not produce nearly as biased a result (and conversely, if you were to run the snippet in the blog post using `rng.Next(2, int.MaxValue)` or `rng.Next(0, int.MaxValue - 2)`, you wouldn't see the same bias, even though the ranges are still odd/even-biased to about the same extent).