6

Possible Duplicates:
How to generate a random number in C?
implementation of rand()
Generating random terrain in Blender3D

I need high quality random numbers in C, but I have no idea what to really do. I need to be able to get numbers from 1-100. Any help or maybe point me to where I can find help.

Community
  • 1
  • 1
akway
  • 1,738
  • 4
  • 21
  • 20
  • 7
    At this point, someone always says "define high quality", so it might as well be me. –  Jul 27 '09 at 21:59
  • What platform are you working on. There's the basic rand(), but each OS has better ways of generating random numbers. If you specify the platform, it will be easier for everyone. – i_am_jorf Jul 27 '09 at 22:02
  • It should at least appear random up to 100 millions runs. – akway Jul 27 '09 at 22:06
  • Note that "appearing random" is surprisingly hard to quantify, and depends on the use you have in mind. – dmckee --- ex-moderator kitten Jul 27 '09 at 22:10
  • It needs to be of the same level of randomness as online gambling sites. – akway Jul 27 '09 at 22:11
  • There's a difference between "high-quality random numbers" and "steady and fair distribution." Which one do you want? – Chris Lutz Jul 27 '09 at 22:14
  • If money is at stake, rand() can be expected to be far too predictable. And at this point, I don't see what distinguishes this question from a dozen other "How do I get good random numbers?" questions... – dmckee --- ex-moderator kitten Jul 27 '09 at 22:18
  • Okay, I need high quality random numbers. As close to true as you can get. – akway Jul 27 '09 at 22:22
  • 4
    Go to Radio Shack. Buy a diode, an NTR resistor, a capacitor and serial cable. Cut off the end of the serial cable that does not fit on your computer. Solder the diode and resistor in series between pins DTR and DSR of the cable. Solder the capacitor between DSR and TXD pins. Write a small C program to do the following: Set DTR to 1. Start Timer. Monitor DSR until it goes to 1. Stop Timer. Calculate resistance from elapsed time. Retreive serveral bits from that value to use as part of random number. Repeat until enough bits have accumulated. Now, you could punt and (modulus) 100... –  Jul 28 '09 at 00:17
  • You had it going on there! Until the modulus. A shame to do all that soldering, just to blow it with a single stroke of the "%". ;-) – Nosredna Jul 28 '09 at 00:23
  • @Nosredna - I was laughing so hard at that... I ran out of room typing and didn't want to continue the comment so I cut it short with the "punt." –  Jul 28 '09 at 00:26
  • The last 1% is always the hardest part. :-) – Nosredna Jul 28 '09 at 00:27
  • 1
    Not a duplicate IMO. None of those other questions mention the requirement here that the output be indistinguishable from random. Now, sure, you can argue exactly what that means, but whatever you decide, the decision affects the answer to the question. None of those other questions requires a secure RNG, and none of them has a decent answer how to scale the value into the range 1-100. – Steve Jessop Jul 28 '09 at 00:31
  • @onebyone, yeah I think you're right. I just read the answers to the other questions and I like some of these better for the particular question the asker asked. – Nosredna Jul 28 '09 at 00:31
  • Aha, this is what I was looking for, I knew the issue had cropped up here before: http://stackoverflow.com/questions/137783/given-a-function-which-produces-a-random-integer-in-the-range-1-to-5-write-a-fun. I think Joel posed this question in a speech at Google. One of those "separate the programmers from the scrubs" deals IIRC, except that anyone with a background in maths and/or AD&D has an absurd home advantage regardless of programming ability. – Steve Jessop Jul 28 '09 at 00:46

8 Answers8

12

This is the simplest method of producing uniformly distributed random numbers in C:

Step 1. Be sure to include the standard library header to get the necessary function prototypes

#include <stdlib.h>

Step 2. Seed the random number generator using srand(). The seed determines where the random numbers start. The sequence of random numbers will always be exactly the same for a given seed. This allows you to have random, yet reproducible results. If you don't need it to be reproducible, a good thing to seed with is the current time, so that the random sequence will be different on each run.

srand(time(NULL));

(be sure to include time.h if you do this). Also, only seed the generator once per program run unless you are generating a huge number (millions or billions) of random numbers. Seeding frequently makes the sequence less random.

Step 3. Get your random number.

rand()

This function returns a random number between 0 and RAND_MAX, which is a macro that is defined as a rather large integer.

Step 4. Get your random number into the range you want. The general formula for doing so is this:

int random_number = rand() % range + min;

Where range is how many (consecutive) numbers you want to choose from, and min is the smallest of these. So to generate a number between 1 and 100, range is 100 and min is 1:

int random_number = rand() % 100 + 1;

Some people object to this formula because it uses the low-order bits of the number given by rand(), and in older implementations of software pseudo-random number generators these were often less random than the high order bits, but on any modern system this method should be perfectly fine.

Tyler McHenry
  • 74,820
  • 18
  • 121
  • 166
  • 1
    This is a bad way of doing it since if favours numbers near the lower end of the scale. If RAND_MAX is something20, then all numbers from 0-20 have an increased chance of getting chosen. It is a slight favouring since RAND_MAX is a very large number, but exists nonetheless. – Rontologist Jul 27 '09 at 22:20
  • ::shrugs:: For application where 'rand()' is acceptable, the bias from the modulus is trivial. If need be, you can always write a wrapper to clip the offending throws and try again. – dmckee --- ex-moderator kitten Jul 27 '09 at 22:29
  • 1
    -1: Using % with rand is very bad. Generate 10,000 random numbers in [1, 100], and you'll see a pretty clear bias. (Consider the case where RAND_MAX = 100, where you'd be twice as likely to roll a 1 as any other number.) – ojrac Jul 27 '09 at 22:31
7

By "fair distribution", I assume you mean that you're not generally satisfied by rand(). In this case, you should probably use OS-specific methods that produce cryptographically secure random numbers - /dev/random or /dev/urandom (depending on your needs) on Unix, and CryptGenRandom or RtlGetRandom on Win32. On Win32 specifically, if you're using VS2005 or later, you may just use rand_s.

Pavel Minaev
  • 99,783
  • 25
  • 219
  • 289
  • +1 for using well-known libraries someone else created. There's no better way to use cryptographically secure anything. – ojrac Jul 27 '09 at 22:34
  • Agree on the need for a great library written by people who spend a lot of time thinking about the problem and testing it. But I'm always interested in whether the gain from employing one of these won't be negated by calling it improperly. – Nosredna Jul 28 '09 at 00:19
  • I'd imagine that it's very probable that if you improperly called the library, you'd be at least as likely to improperly implement it yourself, if not more so. – Kitsune Jul 28 '09 at 00:25
  • Yeah, but at least if you wrote it yourself, you'd know for sure that it was screwed up. :-) – Nosredna Jul 28 '09 at 00:29
3

You can try something like this:

main()
{
  srand(time(0));

  for(int i=0;i<1000;++i)
    printf("%f ", ((float)rand())/RAND_MAX*99+1);

  return 0;
}

It's as uniform a distribution as the standard rand() can give.

Blindy
  • 65,249
  • 10
  • 91
  • 131
  • 1
    I don't think this "appears random up to 100 million runs". For example on Windows, RAND_MAX is 32767. So, once this code is fixed not to sometimes output 101, the values 2, 3, 5, 6... are roughly 0.3% more common than the values 1, 4, 7... I think that in 100M samples that bias should be pretty obvious, and that's even assuming rand() is indistinguishable from random over so many samples. Which it almost certainly isn't, although I can't produce a distinguishing test off the cuff. – Steve Jessop Jul 27 '09 at 22:33
  • As I said, it's as random as rand() can be. There are other rng's out there (like the Mersenne twister) which have better "randomness". And are you sure about the fact that evens having a _slightly_ higher probability matters? I'm dividing it all down to a [0,1] interval and multiplying it back up to [1,100]. – Blindy Jul 27 '09 at 22:37
  • I'm not sure of anything ;-) But in a comment the OP says it should be indistinguishable from random to 100M samples. If this is true, it follows that a 0.3% bias matters. rand() can return 32768 distinct values, and we want to map then onto 100 outputs. So no matter what the source of randomness, 68 outputs are going to be 0.3% more common than the other 32, unless you take the standard precaution of "re-rolling" on a result from `(RAND_MAX - RAND_MAX % 100)` to `RAND_MAX` inclusive. – Steve Jessop Jul 27 '09 at 22:52
  • Sorry, that's the precaution when you're using a modulus. It's not so straightforward when doing a rescale. – Steve Jessop Jul 27 '09 at 23:42
  • A rescale to float or double brings the quirks of floating point representation into play. You can get weird aliasing at the edges of the "bins" when you scale up. – Nosredna Jul 28 '09 at 00:14
  • It doesn't really matter whether you rescale using float, double, or just a lookup table. You can take the modulus, or any other trick you like. If you have 32768 inputs and 100 outputs, then it is impossible to assign equal numbers of inputs to each output. Hence if the input is uniformly distributed, then the output is not. You either need to discard some inputs and pick again, or carry over a remainder from one pick to the next. – Steve Jessop Jul 28 '09 at 00:18
  • Absolutely. Agree. Just pointing out that people often think a conversion to float will save them. But floats aren't continuous. In fact, they are harder to understand than ints, being logarithmic. – Nosredna Jul 28 '09 at 00:26
  • Oh right, I see. Just making sure nobody reads what you wrote and thinks that *avoiding* a float using a modulus will save them, either ;-) – Steve Jessop Jul 28 '09 at 00:35
  • I did that old "do the modulus and loop until valid" trick in a few games. I always had this ticklish feeling that some poor kid somewhere is still waiting for his loop to end with a number in range. :-) – Nosredna Jul 28 '09 at 00:44
  • There are more probable reasons that his PC would stall indefinitely. Insert obligatory Windows joke here. – Steve Jessop Jul 28 '09 at 00:48
  • Heh. This was probably before Windows. – Nosredna Jul 28 '09 at 00:52
  • I wonder if this is the code segment that made it to STL's talk on Going Native 2013. – Carl Oct 21 '13 at 03:18
3

http://mathworld.wolfram.com/RandomNumber.html

This article explains the basics to creating your own random number generator that will outperform the standard C library function if you find it lacking in distribution. It produces a better spread and hence a more random number.

This is critical if you hope to produce something that can not be reverse engineered, like for poker sites.

  • 7
    There are so many good, well debugged PRNGs out there that this is pointless for using. It's for learning from. – dmckee --- ex-moderator kitten Jul 27 '09 at 22:07
  • 5
    Be *very* careful when rolling your own RNG, it's a very easy thing to get wrong and a very hard thing to show that it's wrong. – Kitsune Jul 27 '09 at 22:08
  • 5
    Yea, **DO NOT DO THIS**. People that are much better at this than you or I have done so. http://stackoverflow.com/questions/1046714/what-is-a-good-random-number-generator-for-a-game/1046735#1046735 – GManNickG Jul 27 '09 at 22:09
3

The standard C library has rand which will probably be sufficient, unless you have a need for a prng with a particular statistical distribution..

Jeff Leonard
  • 3,284
  • 7
  • 29
  • 27
2

As an high-quality random number generator, please do not use rand(), or not-Quality-Assured code. It is extremely easy to generate random number incorrectly (check Knuth's funny story in "The art of Computer Programming: Seminumerical Algorithms"). The easiest way to proceed is maybe to use the generators in GNU's scientific library. It installs with one click on *nux, and there are several ports of the GSL to Windows. I've used it. It is easy to call and works well.

gappy
  • 10,095
  • 14
  • 54
  • 73
1

The other posts have good advice. If you really want to dive into the guts of random number generation, take a look at Numerical Recipes in C. Start with Chapter 7.

Pete
  • 10,310
  • 7
  • 53
  • 59
1

If you really need lottery-quality random numbers, I don't think you want a digital algorithm at all.

You want an actual physical process. See Random.org. Are you willing to pay?

Beware programmatic random number generators if you really need random numbers. As we've seen in the answers so far, it's not only hard to write a good random(), it's hard to figure out how to use the output from it correctly, whether by modulo or by scaling. Even code that people see as "obvious" often turns out to be subtly incorrect.

Taking the ints into floats or doubles only brings in all the quirks of floating point numbers (such as their ability to represent more numbers close to zero than close to one).

What are your requirements? Will your numbers need to be certified? Or do you just want really good random numbers? What tests will you employ to see if your random generator is "good?"

Nosredna
  • 83,000
  • 15
  • 95
  • 122
  • On a macro level I want even distribution, each number coming up about 1% of the time. But on a micro level, I want a high volatility, where any section of the 100+ million random numbers appears completely random. – akway Jul 28 '09 at 02:26
  • There are metrics to measure that stuff, but realize that humans are notoriously bad at recognizing randomness, so when you say "appear," do you mean you care more about the appearance of randomness rather than it having been generated in a truly random way? In other words, true random numbers are "streakier" than people expect. Can you live with the true streakiness or would you rather it "look" random to an observer? – Nosredna Jul 28 '09 at 03:27
  • Have you looked through the tools listed at Wikipedia? http://en.wikipedia.org/wiki/Randomness_tests – Nosredna Jul 28 '09 at 03:31