msmcdoug at iinet.net.au
Mon Feb 6 22:18:47 EST 2006
Arthur Flexser wrote:
> An interesting mathematical problem, more or less equivalent to
> finding a formula for the expected number of dart throws when there
> are N squares and i darts, and a dart must be rethrown if it hits a
> square already occupied by another dart. Any takers?
I can think of one approach. Place the numbers from 1 to 338 in an
array. Choose a random number from 1-338 and that's your first number.
Then remove that number from the array by shifting all the numbers above
that down 1 space in the array. Then generate a random number from
1-337. And so on...
Trouble is, shifting numbers takes time, although one can use mempcy for
example. But at least it's deterministic and order N, unlike re-throwing
'darts' as your remaining squares diminish.
The other problem is getting the random number in the correct range in
the first place. One solution is to use the modulus of a very large
random number. As long as the number is large enough (eg. 32 bits), it
shouldn't affect the uniform distribution too much.
More information about the Coco