{"id":1325,"date":"2015-12-09T21:58:33","date_gmt":"2015-12-10T05:58:33","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1325"},"modified":"2015-12-09T23:04:36","modified_gmt":"2015-12-10T07:04:36","slug":"lameness-explained","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1325","title":{"rendered":"Lameness Explained"},"content":{"rendered":"

OK, more than one person wanted explanations of The C++ <random> Lame List<\/a>, so here are some of my thoughts, if only to save people searching elsewhere.<\/p>\n

    \n
  1. Calling rand()<\/code> is lame because it’s an LCG with horrible randomness properties, and we can do better. And if you’re not calling rand()<\/code>, there’s no reason to call srand()<\/code>.<\/li>\n
  2. Using time(NULL)<\/code> to seed your RNG is lame because it doesn’t have enough entropy. It’s only at a second resolution, so in particular, starting multiple processes (e.g. a bringing up bunch of servers) at the same time is likely to seed them all the same.<\/li>\n
  3. No, rand()<\/code> isn’t good enough even for simple uses, and it’s easy to do the right thing these days<\/a>. The lower order bits of rand()<\/code>‘s output are particularly non-random, and odds are that if you’re using rand()<\/code> you’re also using %<\/code> to get a number in the right range. See item 6.<\/li>\n
  4. In C++14 random_shuffle()<\/code> is deprecated, and it’s removed in C++17, which ought to be reason enough. If you need more reason, one version of it is inconvenient to use properly (it uses a Fisher-Yates\/Knuth shuffle so takes an RNG that has to return random results in a shifting range) and the other version of it can use rand()<\/code> under the hood. See item 1.<\/li>\n
  5. default_random_engine<\/code> is implementation-defined, but in practice it’s going to be one of the standard generators, so why not just be explicit and cross-platform-safe (hint: item 10)?. Microsoft’s default is good, but libc++ and libstdc++ both use LCGs as their default at the moment<\/a>. So not much better than rand()<\/code>.<\/li>\n
  6. It is overwhelmingly likely that whatever RNG you use, it will output something in a power-of-two range. Using %<\/code> to get this into the right range probably introduces bias. Re item 3, consider a canonical simple use: rolling a d6. No power of two is divisible by 6, so inevitably, %<\/code> will bias the result. Use a distribution instead. STL<\/a> (and others) have poured a lot of time into making sure they aren’t biased.<\/li>\n
  7. random_device<\/code> is standard, easy to use, and should be high quality randomness. It may not be very well-performing, which is why you probably want to use it for seeding only. But you do want to use it (mod item 8).<\/li>\n
  8. Just know your platform. It might be fine in desktop-land, but random_device<\/code> isn’t always great. It’s supposed to be nondeterministic and hardware based if that’s available… trust but verify, as they say.<\/li>\n
  9. Not handling exceptions is lame. And will bite you. I know this from experience with random_device<\/code> specifically.<\/li>\n
  10. The Mersenne twisters are simply the best randomness currently available in the standard.<\/li>\n
  11. Putting mt19937<\/code> on the stack: a) it’s large (~2.5k) and b) you’re going to be initializing it each time through. So probably not the best. See item 17 for an alternative.<\/li>\n
  12. You’re just throwing away entropy if you don’t seed the generator’s entire state. (This is very common, though.)<\/li>\n
  13. Simply, uniform_int_distribution<\/code> works on a closed interval (as it must – otherwise it couldn’t produce the maximum representable value for the given integral type). If you forget this, it’s a bug in your code – and maybe one that takes a while to get noticed. Not good.<\/li>\n
  14. Forgetting ref()<\/code> around your generator means you’re copying the state, which means you’re probably not advancing the generator<\/a> like you thought you were<\/a>.<\/li>\n
  15. seed_seq<\/code> is designed to seed RNGs<\/a>, it’s that simple. It tries to protect against poor-quality data from random_device<\/code> or whatever variable-quality source of entropy you have.<\/li>\n
  16. Not considering thread safety is always lame. Threads have been a thing for quite a while now.<\/li>\n
  17. thread_local<\/code> is an easy way to get “free” thread safety for your generators.<\/li>\n
  18. You should be using a Mersenne twister (item 10) so just use the right thing for max()<\/code>. Job done.<\/li>\n<\/ol>\n

    If you want more, see rand()<\/code> Considered Harmful<\/a> (a talk by Stephan T Lavavej), or The bell has tolled for rand()<\/code><\/a> (from the Explicit C++ blog), or see Melissa O’Neill’s Reddit thread<\/a>, her talk on PCG<\/a>, and the associated website<\/a>.<\/p>\n

    And of course, cppreference.com<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

    OK, more than one person wanted explanations of The C++ <random> Lame List, so here are some of my thoughts, if only to save people searching elsewhere. Calling rand() is lame because it’s an LCG with horrible randomness properties, and we can do better. And if you’re not calling rand(),…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[],"class_list":["post-1325","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1325","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1325"}],"version-history":[{"count":17,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1325\/revisions"}],"predecessor-version":[{"id":1342,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1325\/revisions\/1342"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1325"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1325"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1325"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}