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.

  • \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 6, 2012 at 19:12

5 Answers 5


Perl, 37 42 char


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

  • 1
    \$\begingroup\$ I'm impressed that you came back 6 years later to optimize this solution. \$\endgroup\$ Commented Dec 17, 2018 at 22:54

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%.

  • \$\begingroup\$ 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 \$\endgroup\$
    – Matt
    Commented Sep 6, 2012 at 14:36
  • \$\begingroup\$ Although, as expected, random.random() < x is considerably faster. \$\endgroup\$
    – Matt
    Commented Sep 6, 2012 at 14:37

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]]]





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}]

{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}


Histogram of results


Explanation (spoiler alert!)

The base 2 representation of .53 is


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,


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


Haskell, 107 chars:

import System.Random
g p|p>1=print 1|p<0=print 0|1>0=randomIO>>=g.(p*2-).f
f x|x=1|1>0=0.0

Wolfram Language (Mathematica), 42 bytes


Try it online!

This is a recursive approach. Ungolfed, the algorithm is:

  • If the input probability p is less than 1/2, then when the coinflip comes up 0, return 0. Otherwise, recurse on 2p; assuming correctness, the overall probability of getting 1 is half of 2p or p.
  • If the input probability p is greater than 1/2, then when the coinflip comes up 1, return 1. Otherwise, recurse on 2p-1; assuming correctness, the overall probability of getting 0 is half of 1-(2p-1) or 1-p.

To make it shorter, we start with the random coinflip, which, in either branch, gets returned half the time. If the coinflip does not match the case when we're supposed to return it, replace it by the result of recursing on 2p modulo 1. (That is, when p is less than 1/2, replace 1; when p is greater than 1/2, replace 0. This is equivalent to replacing ⌈1-2p⌉.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.