robert.gault at worldnet.att.net
Mon Feb 6 23:15:19 EST 2006
That is exactly what I tried, but shifting the numbers is indeed much
too slow. This method in Basic takes about 40 seconds, while the dart
throw method takes about 5.
However, if the setup was written in assembly, then I think this might
be faster than the dart throw. That would not, however, be a fair
critique of Diego's program.
Mark McDougall wrote:
> 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