Given a fair coin as input, generate any particular unfair outcome

It is easy to generate a fair coin using a unfair coin, but the reverse is harder to accomplish.

Your program will receive one number X (between 0 and 1, inclusive) as input. The input must not simply be hard-coded as a number in the middle of the source code. It must then return a single digit: a `1` with a probability of X and a `0` otherwise.

Your program is only allowed to use one form of random number generator in the source code: `int(rand(2))` (or an equivalent), which returns either a zero or a one with equal probability. You can include or access this function as many times as you wish in your code. You also have to provide the function yourself as part of the code.

Your program is not allowed to use any other random number generating functions or external sources (such as time and date functions) that could function as a random number generating function. It also cannot access any external files or pass the job along to external programs.

This is code golf, the shortest answer wins.

-
 What form does the input take? If we're guaranteed that it's an IEEE-754 floating point number of a given size, then this is actually pretty easy. – Peter Taylor Sep 6 '12 at 19:12

Python, 81 chars

``````import random
print(sum(random.randint(0,1)*2**-i for i in range(9))<input()*2)+0
``````

Can be off by a bit, but never more than 1%.

-
 Looks much better than 1% to me. I ran your program 100,000 times for probabilities of [0,1] with a step of 0.01 and compared this with `random.random() < desiredProbability` using this script: gist.github.com/3656877 They match up perfectly i.imgur.com/Hr8uE.png – Matt Sep 6 '12 at 14:36 Although, as expected, `random.random() < x` is considerably faster. – Matt Sep 6 '12 at 14:37

Perl, 42 char

``````map\$d+=(rand>.5)/2**\$_,1..99;print\$d<pop|0
``````

Takes arbitrary probability as a command line argument. Builds a uniform random number in `\$d` and compares it to the input.

Earlier, 52 char solution

``````\$p=<>;do{\$p*=2;\$p-=(\$-=\$p)}while\$--(.5<rand);print\$-
``````
-

Mathematica 165

Not streamlined, but some may find the algorithm of interest:

``````d = RealDigits; r = RandomInteger;
f@n_ := If[(c = Cases[Transpose@{a = Join[ConstantArray[0, Abs[d[n, 2][[2]]]], d[n, 2][[1]]],
RandomInteger[1, {Length@a}]}, {x_, x_}]) == {}, r, c[[1, 1]]]
``````

Usage

``````f[.53]
``````

1

Check

Let's see if `f[.53]` really produces the value `1` around 53% of the time. Each test calculates the % for samples of 10^4.

50 such tests are run and averaged.

``````Table[Count[Table[f[.53], {10^4}], 1]/10^4 // N, {50}]
Mean[%]
``````

{0.5292, 0.5256, 0.5307, 0.5266, 0.5245, 0.5212, 0.5316, 0.5345, 0.5297, 0.5334, 0.5306, 0.5288, 0.528, 0.5379, 0.5293, 0.5263, 0.539, 0.5322, 0.5195, 0.5208, 0.5382, 0.543, 0.5336, 0.5305, 0.5303, 0.5297, 0.5318, 0.5243, 0.5281, 0.5361, 0.5349, 0.5308, 0.5265, 0.5309, 0.5233, 0.5345, 0.5316, 0.5376, 0.5264, 0.5269, 0.5295, 0.523, 0.5294, 0.5326, 0.5316, 0.5334, 0.5165, 0.5296, 0.5266, 0.5293}

0.529798

Histogram of results

The base 2 representation of .53 is

.10000111101011100001010001111010111000010100011110110

Proceeding from left to right, one digit at a time:

If RandomInteger[] returns 1, then answer = 1,

Else If second RandomInteger[] returns 0, then answer = 0,

Else If third RandomInteger[] returns 0, the answer = 0,

Else....

If, when all digits have been tested, there is still no answer, then answer = RandomInteger[].

-

``````import System.Random