Good, Portable Random Number Generator for C++?

Discussion in 'Mac Programming' started by ArtOfWarfare, Jan 9, 2013.

  1. macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #1
    Is there a good, portable random number generator available for C++?

    By "good", I mean I don't have to include a line of code to seed it, it'll be different with each run of the program, and the pattern won't be apparent.

    I know that rand() is available, but issues with it include:
    1 - You have to seed it.
    2 - It's implementation dependent, and there's no requirement for it to actually have a non-predictable pattern. An implementation could be as simple as:

    Code:
    int rand() {
        return 0;
    }
    And it would conform to C99's definition of rand(). (Am I using the right terms here?)

    If I were writing this program for just OS X and iOS, I'd use arc4rand()... does anyone have anything comparable I could use in C++?
     
  2. macrumors 603

    Joined:
    Aug 9, 2009
    #2
    Google the source for arc4rand.

    I did it myself a while ago, because I needed a PRNG in an embedded microcontroller project. It wasn't hard to find C implementations.

    You will still need a source for initial entropy, and that source may need to be tailored to the platform. For example, one of the default sources in the source I got was the uninitialized stack area. On an embedded uC, that's an extremely predictable source, because the call sequence that leads up to the initialization is always identical. So for me, the hard part wasn't the PRNG itself, but coming up with a usable source of initial entropy.

    A typical default source on a non-embedded computer is the /dev/random device (or its equivalent). If you know that device will be present, use it. Otherwise the task of gathering entropy becomes harder.
     
  3. dmi
    macrumors regular

    Joined:
    Dec 21, 2010
    #3
  4. ytk
    macrumors regular

    Joined:
    Jul 8, 2010
    #4
    Code:
    cout << "Please roll a die and type in the result: " ;
    cin >> result ; 
    
    :D

    Seriously, though, any pseudorandom number generator is going to have to be seeded somehow, and will by definition have a predictable pattern. The only way around this is with a dedicated hardware random number generator (of which, technically, a thrown die is an example).

    As chown33 said, if the problem is that you don't have any way of generating the initial entropy required to seed the generator on your system, then you're simply not going to find any library that will work for you. If you do have access to something like a continuously running timer, then what's the problem with seeding? If you really want, you can write a wrapper around random() (which is a better replacement for rand() and already part of stdlib.h) that reseeds the PRNG each time you call it. That would make it less "predictable", anyway, assuming you didn't call it so quickly that you ever generate numbers with the same random seed twice in succession.
     
  5. macrumors 6502

    Joined:
    Sep 13, 2010
    #5
    Several are part of the C++ Standard and should come with any compiler that has kept up over the last few years. Have you looked for:

    #include <random>

    Your other requirements are either easy to deal with or impossible to achieve using ordinary equipment.
     
  6. macrumors 6502a

    Joined:
    Jun 14, 2012
    Location:
    Columbia, MD
    #6
    I would begin by looking for code samples to the generators discussed here: http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
     
  7. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #7
    Open terminal, enter "man arc4random" and read carefully.

    You can't produce better random numbers. Well, if you can, you are not looking for advice on macrumors :D
     
  8. macrumors 603

    Cromulent

    Joined:
    Oct 2, 2006
    Location:
    The Land of Hope and Glory
    #8
    I'd be curious how the new random number generator built into modern Intel CPUs compares to this in terms of quality. Since the Intel implementation contains a hardware based entropy source I would guess it was better. It would definitely be faster.

    http://en.wikipedia.org/wiki/RdRand
     
  9. macrumors 603

    Joined:
    Aug 9, 2009
    #9
    Faster, but not portable.
     
  10. thread starter macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #10
    This is very cool, but unfortunately, as chown said, not sufficiently portable.

    I'd like my app to run on darn near any OS... OS X, iOS, Android, Windows XP, 7, RT, or 8... and it must be C++. So being able to seed with a clock isn't an actual issue, but I prefer systems where I don't need to handle seeding (IE, the way arc4rand() doesn't need to be seeded first.)
     
  11. ytk
    macrumors regular

    Joined:
    Jul 8, 2010
    #11
    :confused: What's the point of bloating your program unnecessarily with some third-party random number library instead of just using the perfectly good built-in random number function, all to avoid a single line of code?
     
  12. macrumors 601

    Mr. Retrofire

    Joined:
    Mar 2, 2010
    Location:
    www.emiliana.cl
    #12
    Other device/machine specific information includes:
    - Current configuration data in preference files (user specific).
    - Current uptime (microseconds or nanoseconds).
    - Number of files in a certain folder (user specific).
    - All names of all files in a certain folder (user specific).
    - Noise from the microphone & camera pictures (user specific).
    - Random seed files from other (open source) applications (openssl for example).

    For preshared keys (SHA-2 (512-Bit) or SHA-3 based), i would use noise from a non-silent street/city recorded via a stereo recorder like the WS-803 or WS-813. This device supports the lossless PCM format in WAV files (41 kHz). If someone can predict 1 GB of this noise, then i'm the emperor of china! ;-)
     
  13. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #13
    Which "perfectly good built-in random number function" do you mean? The one in the Standard C library?
     
  14. thread starter macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #14
    I would assume that's what they meant.

    I have, for the time being, decided to just use it and, to ensure "fairness" to the best of my ability, I include something like:

    Code:
    unsigned char n = (from user input);
    int maxFairRand = (MAX_RAND / n) * n;
    int rand = random();
    while (rand > maxFairRand)
        rand = random();
    unsigned char r = rand % n
    As much as I can control it, this ensures that lower numbers won't be more common than higher numbers. (All of my numbers are 255 or lower... Thus why r and n are both unsigned chars.)

    I'm just doing a school homework assignment that involved an RNG as a portion of it. I figure overdoing an assignment is always fun, so I tried that here.
     
  15. macrumors member

    Joined:
    Sep 28, 2009
    #15
    seed sources

    Any thoughts on these for "random seeds"
    Internal: system clock milliseconds
    External: Earthquake web site richter scale fractions.
     
  16. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #16
    Well, arc4random_uniform (n) does exactly that and I can guarantee that it will be of higher quality. And it automatically has a random seed. Some implementations of random () are of pathetic quality. For example, if you throw two dice until you get two different results, what is the probability that the first dice shows a higher number than the second? There are random number generators out there where the answer is not "50%".

    ----------

    Internal: date in nanoseconds, xor'd with the time since the computer has started in processor cycles.

    Better: /dev/random.
     
  17. ytk
    macrumors regular

    Joined:
    Jul 8, 2010
    #17
    random(). If your primary concern is portability, why use anything else? random() works fine for anything, and is part of the POSIX specification so you're going to be able to use it on pretty much any platform you like (and I'd argue that any platform that isn't POSIX-compliant is one I don't like. :D ).
     
  18. jon3543, Jan 10, 2013
    Last edited: Jan 10, 2013

    macrumors 6502

    Joined:
    Sep 13, 2010
    #18
    I see that you're trying to account for the bias inherent in trying to alter the range of rand(), but there are a couple of mistakes in it. See the C FAQ for a correct approach:

    http://c-faq.com/lib/randrange.html

    As for the code you presented, I don't recognize random() and MAX_RAND. For Standard C, I know about rand() and RAND_MAX, which are in <stdlib.h>. Since you asked about C++ in your original question, I gave you a C++ answer in my earlier reply:

    In case it isn't clear, the Standard C++ <random> library is not remotely the same thing as C's far more primitive and less capable rand() function.

    ETA: As you say you're doing homework and like to overdo things, do you understand why the C FAQ code I linked to uses unsigned int and the constant 1u in the statement, "unsigned int x = (RAND_MAX + 1u) / N;" Hint: It could have achieved the same thing with ((unsigned int) RAND_MAX+1)/N. One or the other is necessary!
     
  19. thread starter macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #19
    The <random> library wasn't recognized when I tried compiling the code on a computer running Windows 7.

    I'm guessing it's to account for zero? But no... that doesn't make sense...

    Suppose RAND_MAX is 4 and I want one of 3 values.

    My code, would do 4 / 3 = 1, then * 3 = 3.

    Which means it could return 0, 1, 2, or 3... I see the issue here... I should discard values >= maxFairRand rather than only greater than it.

    Or is that not the issue you're getting at?
     
  20. macrumors 6502

    Joined:
    Sep 13, 2010
    #20
    I'm pretty sure it was included at least as far back as Visual Studio 2010. I assume there's still a free compiler available for VS2012. In any case, just to see what's in it, google /msdn random vc++/. The 2nd hit I get is:

    http://msdn.microsoft.com/en-us/library/bb982398.aspx

    The dropdown "Other Versions" says it was in VS2008.

    That, plus the need to add 1 to RAND_MAX to accurately capture the number of possible values rand() can return, which goes from 0 to RAND_MAX, inclusive. Off-by-one errors lurk everywhere.

    The question I posed in my "ETA" concerns some lower-level behavior, which is still very important to understand. If you get it, great; if not, post something.
     

Share This Page