455,536 Members | 1,290 Online Need help? Post your question and get tips & solutions from a community of 455,536 IT Pros & Developers. It's quick & easy.

# Random Number

 P: n/a Hi I am generating a random number using random.randint(1,10000000000) Whats the possibility that the numbers generated will be same when generated by 100 users at the same time? Whats the best method to generate random numbers so that they are most likely unique?? Thanks Jul 18 '05 #1
4 Replies

 P: n/a The probability that the same number will turn up more than once is approximately one in two million. If you're still worried, you might want to try something like this: import random randoms=[] while len(randoms)<5: x=random.randint(1,100) if x in randoms: continue else: randoms.append(x) HTH. BTW it's a lot easier to read "10**10" or "1e10" instead of a big string of zeros. Peace "james blair" wrote in message news:a4**************************@posting.google.c om... | Hi | I am generating a random number using | random.randint(1,10000000000) | Whats the possibility that the numbers generated will be same when | generated by 100 users at the same time? | Whats the best method to generate random numbers so that they are most | likely unique?? | Thanks Jul 18 '05 #2

 P: n/a ta**************@yahoo.com (james blair) writes: I am generating a random number using random.randint(1,10000000000) At least in Python 2.2, 10000000000 is not a valid arg to randint, which has to take two int (not long) values. 10000000000 won't fit in 32 bits. I'm not sure about Python 2.3 or 2.4. Whats the possibility that the numbers generated will be same when generated by 100 users at the same time? There's two levels where you have to think about that questions: 1) Is the underlying generator biased enough to make such a collision more likely than pure chance? That would be a failure of what's called the "poker test" (Knuth vol. 2) and Python's PRNG is supposed to be good about that, so you shouldn't get extra (or too few) collisions that way. 2) What's the likelihood of such a collision if the numbers from the generator are really random? Let N be the number of distinct values, in this case N= approx. 10**10. Let k be how many numbers you draw, i.e. in this case k=100. Let the random numbers be a,a,...,a[N]. If there's no collision, it means that for every i,j with i,j in 1,2,...,k, a[i] != a[j]. There are k**2/2 such (unordered) pairs, and for any i,j, a[i]!=a[j] with probability 1-1/N. So the chance of all the pairs being unequal is (1-1/N)**(k**2/2). That's about exp(-k**2/(2*N)), or about 1 in 2 million for your parameters. The case N=365, k=23 is the famous "birthday paradox". It says that if you have 23 people in a room, there's a better-than-even chance that some two of them have the same birthday. In general, if you have a set of random numbers with N possible values, you can expect to see a collision after seeing O(sqrt(N)) numbers. Those collisions are called "birthday collisions" after the birthday paradox. Whats the best method to generate random numbers so that they are most likely unique?? If they're random, there is a chance that they will collide, and the only way to make that less likely is to use a bigger range. Jul 18 '05 #3

 P: n/a "james blair" wrote: Whats the possibility that the numbers generated will be same when generated by 100 users at the same time? This has already been answered. Whats the best method to generate random numbers so that they are most likely unique?? Realy, there's no "most likely" way. You can either rely on the random number generator (mersenne twister, which is pretty damn good) or you can guarantee that they are unique by a couple of methods: 1. Keep track of which numbers have been generated, and if you get a repeat re-generate it - works well if the total number of numbers to be generated is small and the range is large; 2. Keep track of all the possible values, and as each one is chosen eliminate it from the future possible values. Select values using random.choice(); 3. If you know the maximum number of random values you will ever generate, and you want to guarantee no collisions, Python 2.3 has a superb way of doing it ... import random random.sample(xrange(1000000000), 5) [463302274, 701637929, 319795767, 173458898, 500806835] and you can then just hand out the values in order ... import random rand_values = iter(random.sample(xrange(1000000000), 5)) rand_values.next() 724415074 rand_values.next() 316181550 rand_values.next() 107217351 rand_>>> rand_values.next() 828888162 rand_values.next() 599821642 rand_values.next() Traceback (most recent call last): File "", line 1, in ? StopIteration Note that there is one fewer zero in there than you want because ... import random random.sample(xrange(10000000000), 5) Traceback (most recent call last): File "", line 1, in ? OverflowError: long int too large to convert to int Tim Delaney Jul 18 '05 #4

 P: n/a ta**************@yahoo.com (james blair) wrote in message news:... Hi I am generating a random number using random.randint(1,10000000000) Whats the possibility that the numbers generated will be same when generated by 100 users at the same time? The probability that all 100 numbers will be the same is 1e-1000. But you probably wanted the probability that *any* two numbers will be the same, which is approximately 4.95e-07, or about 1 in 2 million. Whats the best method to generate random numbers so that they are most likely unique?? If the probability of collisions is low, use: def UniqueRandom(a, b): "Generator for random integers between a and b, inclusive." alreadyUsedNumbers = sets.Set() while True: randomNumber = random.randint(a, b) if randomNumber not in alreadyUsedNumbers: alreadyUsedNumbers.add(randomNumber) yield randomNumber If the probability of collisions is high, use: def UniqueRandom(a, b): "Generator for random numbers between a and b, inclusive." sampleSpace = range(a, b + 1) random.shuffle(sampleSpace) return iter(sampleSpace) Jul 18 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion. 