Random Number

[james blair]

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

[Elaine Jackson]

Re: Random Number

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:
[color=blue][color=green][color=darkred]
>>> import random
>>> randoms=[]
>>> while len(randoms)<5:[/color][/color][/color]
x=random.randin t(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" <talktojamesbla ir@yahoo.com> wrote in message
news:a4648036.0 403271156.78770 6e5@posting.goo gle.com...
| 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

[Paul Rubin]

Re: Random Number

talktojamesblai r@yahoo.com (james blair) writes:[color=blue]
> I am generating a random number using
> random.randint( 1,10000000000)[/color]

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.
[color=blue]
> Whats the possibility that the numbers generated will be same when
> generated by 100 users at the same time?[/color]

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[1],a[2],...,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.
[color=blue]
> Whats the best method to generate random numbers so that they are most
> likely unique??[/color]

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.

[Tim Delaney]

Re: Random Number

"james blair" wrote:
[color=blue]
> Whats the possibility that the numbers generated will be same when
> generated by 100 users at the same time?[/color]

This has already been answered.
[color=blue]
> Whats the best method to generate random numbers so that they are most
> likely unique??[/color]

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 ...
[color=blue][color=green][color=darkred]
>>> import random
>>> random.sample(x range(100000000 0), 5)[/color][/color][/color]
[463302274, 701637929, 319795767, 173458898, 500806835]

and you can then just hand out the values in order ...
[color=blue][color=green][color=darkred]
>>> import random
>>> rand_values = iter(random.sam ple(xrange(1000 000000), 5))
>>> rand_values.nex t()[/color][/color][/color]
724415074[color=blue][color=green][color=darkred]
>>> rand_values.nex t()[/color][/color][/color]
316181550[color=blue][color=green][color=darkred]
>>> rand_values.nex t()[/color][/color][/color]
107217351
rand_>>> rand_values.nex t()
828888162[color=blue][color=green][color=darkred]
>>> rand_values.nex t()[/color][/color][/color]
599821642[color=blue][color=green][color=darkred]
>>> rand_values.nex t()[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in ?
StopIteration

Note that there is one fewer zero in there than you want because ...
[color=blue][color=green][color=darkred]
>>> import random
>>> random.sample(x range(100000000 00), 5)[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in ?
OverflowError: long int too large to convert to int

Tim Delaney

[Dan Bishop]

Re: Random Number

talktojamesblai r@yahoo.com (james blair) wrote in message news:<a4648036. 0403271156.7877 06e5@posting.go ogle.com>...[color=blue]
> 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?[/color]

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.
[color=blue]
> Whats the best method to generate random numbers so that they are most
> likely unique??[/color]

If the probability of collisions is low, use:

def UniqueRandom(a, b):
"Generator for random integers between a and b, inclusive."
alreadyUsedNumb ers = sets.Set()
while True:
randomNumber = random.randint( a, b)
if randomNumber not in alreadyUsedNumb ers:
alreadyUsedNumb ers.add(randomN umber)
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(sampleSpac e)