| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 794.1 | | SMURF::DIKE | | Wed Dec 02 1987 17:07 | 5 |
| Flip the coin to make a binary number (eg 1 for heads, 0 for tails)
with enough digits to make a number lager than n. If the generated
number is < n, that's it. If not, try again.
Jeff
|
| 794.2 | Not as general as .1, but more elegant | SQM::HALLYB | Khan or bust! | Wed Dec 02 1987 22:15 | 4 |
| If the coin is, say, an MS65 $5 Gold Liberty, then you could trade
it in for a very large table of random numbers.
John :-)
|
| 794.3 | | CLT::GILBERT | Builder | Thu Dec 03 1987 11:38 | 41 |
| function coin_flip: boolean; { The fair coin }
external;
function rand(x: real): boolean; { Return true with probability x }
begin
if x <= 0 then rand := false
else if x >= 1 then rand := true
else if coin_flip then rand := rand(2*x-1)
else rand := rand(2*x);
end;
To understand this, imagine the interval from 0 to 1, with x being the
leftmost part of this range.
|<---x---> | | -or- |<------x--|---> |
0 � 1 0 � 1
The coin flip determines whether we got to the left or right of �.
We expand the selected region and recurse.
To choose one of n possibilities, the same approach can be used.
function randint(n:integer): integer; { Return random number 1..n }
begin
randint := r2( 1, n+1 );
end;
function r2( lo,hi:real ): integer;
var
ilo,ihi: integer;
begin
ilo := trunc(lo);
ihi := trunc(hi);
if (ilo=ihi) or ((ihi=hi) and (ilo=ihi-1))
then r2 := ilo
else if coin_flip then r2 := r2( (lo+hi)/2, hi )
else r2 := r2( lo, (lo+hi)/2 )
end;
I s'pose it would be nice to restate these without using floating-point.
|
| 794.4 | divide choices in half, flip, discard, repeat til done | VIDEO::OSMAN | type video::user$7:[osman]eric.vt240 | Fri Dec 04 1987 09:03 | 18 |
| If I understand you correctly, you want to select just ONE out of n choices,
with equal probability, and you want to use just one coin.
First, arrange your choices from left to right, and draw a line down the
middle.
Flip the coin, and heads mean you through away the left
choices, and tails means you through away the right half.
Then repeat: Divide the remaining choices into a left and right half,
flip, through one half away.
This method will let you choose amongst thousands of choices in less
than 20 flips, although dividing them in half each time might
be time-consuming.
/Eric
|
| 794.5 | 2^i=n ? | BLITZN::ROBERTS | Peace .XOR. Freedom ? | Fri Dec 04 1987 12:10 | 7 |
| RE: .4
Eric, I'm interested in both cases. Your method, though, would
seem to work only when n is an integral power of two.
/Dwayne
|