Go Back   MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Reply
 
Thread Tools Search this Thread Display Modes
Old Jan 9, 2013, 01:18 PM   #1
ArtOfWarfare
macrumors 603
 
ArtOfWarfare's Avatar
 
Join Date: Nov 2007
Send a message via Skype™ to ArtOfWarfare
Good, Portable Random Number Generator for C++?

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++?
__________________
Don't tell me Macs don't last: 2007 iMac, 2007 Mac Mini, 2008 MacBook Air, all Vintage.
(iMac obsoletion: April 28, 2015, MBA: October 14, 2015, Mac Mini: March 9, 2016)
ArtOfWarfare is offline   0 Reply With Quote
Old Jan 9, 2013, 02:02 PM   #2
chown33
macrumors 603
 
Join Date: Aug 2009
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.
chown33 is offline   0 Reply With Quote
Old Jan 9, 2013, 02:11 PM   #3
dmi
macrumors member
 
Join Date: Dec 2010
Actually, there's a requirement that it have a predictable pattern.

What is sufficiently non-apparent for a particular intended application depends on your particular needs.

These may be suitable for some purposes:
http://www.math.sci.hiroshima-u.ac.j...at/MT/emt.html
http://csrc.nist.gov/groups/ST/toolk...om_number.html
dmi is offline   0 Reply With Quote
Old Jan 9, 2013, 02:32 PM   #4
ytk
macrumors regular
 
Join Date: Jul 2010
Code:
cout << "Please roll a die and type in the result: " ;
cin >> result ;


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.
ytk is offline   2 Reply With Quote
Old Jan 9, 2013, 03:08 PM   #5
jon3543
macrumors 6502
 
Join Date: Sep 2010
Quote:
Originally Posted by ArtOfWarfare View Post
Is there a good, portable random number generator available for C++?
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.
jon3543 is offline   0 Reply With Quote
Old Jan 9, 2013, 03:16 PM   #6
phr0ze
macrumors 6502a
 
Join Date: Jun 2012
Location: Columbia, MD
Quote:
Originally Posted by ArtOfWarfare View Post
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++?
I would begin by looking for code samples to the generators discussed here: http://en.wikipedia.org/wiki/Cryptog...mber_generator
__________________
2012 11" MBA i7/8/256
2011 Mac Mini
Black iPad Air 64GB Verizon
Black iPhone 5S 32GB ATT
phr0ze is offline   0 Reply With Quote
Old Jan 9, 2013, 05:08 PM   #7
gnasher729
macrumors G5
 
gnasher729's Avatar
 
Join Date: Nov 2005
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
gnasher729 is offline   0 Reply With Quote
Old Jan 9, 2013, 05:19 PM   #8
Cromulent
macrumors 603
 
Cromulent's Avatar
 
Join Date: Oct 2006
Location: The Land of Hope and Glory
Quote:
Originally Posted by gnasher729 View Post
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
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
__________________
Neural Advance - Mac OS X, UNIX and Windows Development
Last.fm Profile | Extreme Metal Reviews
MP 4x 2.66Ghz Xeons / 6GB RAM / 640GB + 500GB + 750GB + 1TB HDDs / ATI Radeon 4870 / iPad 3
Cromulent is offline   0 Reply With Quote
Old Jan 9, 2013, 07:14 PM   #9
chown33
macrumors 603
 
Join Date: Aug 2009
Quote:
Originally Posted by Cromulent View Post
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
Faster, but not portable.
chown33 is offline   0 Reply With Quote
Old Jan 9, 2013, 07:34 PM   #10
ArtOfWarfare
Thread Starter
macrumors 603
 
ArtOfWarfare's Avatar
 
Join Date: Nov 2007
Send a message via Skype™ to ArtOfWarfare
Quote:
Originally Posted by Cromulent View Post
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
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.)
__________________
Don't tell me Macs don't last: 2007 iMac, 2007 Mac Mini, 2008 MacBook Air, all Vintage.
(iMac obsoletion: April 28, 2015, MBA: October 14, 2015, Mac Mini: March 9, 2016)
ArtOfWarfare is offline   0 Reply With Quote
Old Jan 10, 2013, 01:42 AM   #11
ytk
macrumors regular
 
Join Date: Jul 2010
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?
ytk is offline   0 Reply With Quote
Old Jan 10, 2013, 02:34 AM   #12
Mr. Retrofire
macrumors 601
 
Mr. Retrofire's Avatar
 
Join Date: Mar 2010
Location: www.emiliana.cl
Quote:
Originally Posted by chown33 View Post
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.
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! ;-)
__________________

“Only the dead have seen the end of the war.”
-- Plato --
Mr. Retrofire is offline   0 Reply With Quote
Old Jan 10, 2013, 03:46 AM   #13
gnasher729
macrumors G5
 
gnasher729's Avatar
 
Join Date: Nov 2005
Quote:
Originally Posted by ytk View Post
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?
Which "perfectly good built-in random number function" do you mean? The one in the Standard C library?
gnasher729 is offline   0 Reply With Quote
Old Jan 10, 2013, 08:22 AM   #14
ArtOfWarfare
Thread Starter
macrumors 603
 
ArtOfWarfare's Avatar
 
Join Date: Nov 2007
Send a message via Skype™ to ArtOfWarfare
Quote:
Originally Posted by gnasher729 View Post
Which "perfectly good built-in random number function" do you mean? The one in the Standard C library?
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.
ArtOfWarfare is offline   0 Reply With Quote
Old Jan 10, 2013, 10:24 AM   #15
osxabsd
macrumors member
 
Join Date: Sep 2009
seed sources

Any thoughts on these for "random seeds"
Internal: system clock milliseconds
External: Earthquake web site richter scale fractions.
osxabsd is offline   0 Reply With Quote
Old Jan 10, 2013, 12:28 PM   #16
gnasher729
macrumors G5
 
gnasher729's Avatar
 
Join Date: Nov 2005
Quote:
Originally Posted by ArtOfWarfare View Post
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.
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%".

----------

Quote:
Originally Posted by osxabsd View Post
Any thoughts on these for "random seeds"
Internal: system clock milliseconds
External: Earthquake web site richter scale fractions.
Internal: date in nanoseconds, xor'd with the time since the computer has started in processor cycles.

Better: /dev/random.
gnasher729 is offline   0 Reply With Quote
Old Jan 10, 2013, 02:13 PM   #17
ytk
macrumors regular
 
Join Date: Jul 2010
Quote:
Originally Posted by gnasher729 View Post
Which "perfectly good built-in random number function" do you mean? The one in the Standard C library?
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. ).
ytk is offline   0 Reply With Quote
Old Jan 10, 2013, 02:59 PM   #18
jon3543
macrumors 6502
 
Join Date: Sep 2010
Quote:
Originally Posted by ArtOfWarfare View Post
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.
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:

Quote:
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.
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!

Last edited by jon3543; Jan 10, 2013 at 03:05 PM.
jon3543 is offline   0 Reply With Quote
Old Jan 10, 2013, 06:42 PM   #19
ArtOfWarfare
Thread Starter
macrumors 603
 
ArtOfWarfare's Avatar
 
Join Date: Nov 2007
Send a message via Skype™ to ArtOfWarfare
Quote:
Originally Posted by jon3543 View Post
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.
The <random> library wasn't recognized when I tried compiling the code on a computer running Windows 7.

Quote:
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!
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?
__________________
Don't tell me Macs don't last: 2007 iMac, 2007 Mac Mini, 2008 MacBook Air, all Vintage.
(iMac obsoletion: April 28, 2015, MBA: October 14, 2015, Mac Mini: March 9, 2016)
ArtOfWarfare is offline   0 Reply With Quote
Old Jan 10, 2013, 06:59 PM   #20
jon3543
macrumors 6502
 
Join Date: Sep 2010
Quote:
Originally Posted by ArtOfWarfare View Post
The <random> library wasn't recognized when I tried compiling the code on a computer running Windows 7.
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.

Quote:
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?
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.
jon3543 is offline   0 Reply With Quote

Reply
MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Similar Threads
thread Thread Starter Forum Replies Last Post
Resolved: Random Question Generator newtomac123 iPhone/iPad Programming 4 Apr 21, 2014 04:10 PM
Random sequences generator Bond J. Mac Applications and Mac App Store 1 Sep 2, 2013 03:06 PM
Can't they do that number generator thing to see if a beta is coming out? tymaster50 iOS 7 5 Aug 20, 2013 12:46 PM
Making a good Password Generator app petisjioweelsha Mac Programming 5 Oct 9, 2012 01:24 PM
Xcode random sting generator fizy45 iPhone/iPad Programming 1 Jul 23, 2012 02:43 AM

Forum Jump

All times are GMT -5. The time now is 03:37 PM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps

Mobile Version | Fixed | Fluid | Fluid HD
Copyright 2002-2013, MacRumors.com, LLC