Pick a random number between 0 and n using a constant source of randomness

Question

Task

Given a positive integer n less than 2^30 specified as input in any way you choose, your code should output a random integer between 0 and n, inclusive. The number you generate should be chosen uniformly at random. That is each value from 0 to n must occur with equal probability (see Rules and Caveats).

Rules and Caveats

Your code can assume that any random number generator built into your language or standard library that claims to be uniformly random is in fact uniform. That is you don't have to worry about the quality of the random source you are using. However,

• You do have to establish that if the random source you are using is uniform then your code correctly outputs a uniform random integer from 0 to n.
• Any arguments when calling a built in or library random function must be constant. That is they must be completely independent of the input value.
• Your code may terminate with probability 1 rather than being guaranteed to terminate.

Notes

• randInt(0,n) is not valid as it takes the input as an argument to a builtin or library function.
• rand()%n will not give a uniform random number in general. As an example given by betseg, if intmax == 15 and n = 10, then you will be much more likely to get 0-5 than 6-10.
• floor(randomfloat()*(n+1)) will also not give a uniform random number in general due to the finite number of different possible floating point values between 0 and 1.

Answer 1

x86 machines with rdrand instruction, 10 bytes

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

machine code

0FC7F0 73FB 39F8 77F7 C3

---

The input is in the register rdi and the output in rax.
This respects the SYS V AMD64 ABI so the code effectively implement a C function

unsigned int foo(unsigned int max); 

with 32-bit ints.

The instruction rdrand is described by Intel

RDRAND returns random numbers that are supplied by a cryptographically secure, deterministic random bit generator DRBG. The DRBG is designed to meet the NIST SP 800-90A standard.

Dealing with CSRNG it is implicit that the distribution is uniform, anyway, quoting the NIST SP 800-90A:

A random number is an instance of an unbiased random variable, that is, the output produced by a uniformly distributed random process.

---

The procedure generates a random number and if it is non-strictly greater than the input it is returned.
Otherwise, the process is reiterated.

Since eax is 32-bit, rdrand returns a number between 0 and 2³²-1, so for every n in [0, 2³²-1] the number of expected iterations is 2³²/(n+1) which is defined for all n in [0, 2³⁰).

Answer 2

Jelly, 7 6 bytes

⁴!!X%‘

Thanks to @JonathanAllan for golfing off 1 byte!

Cannot be run on TIO because (16!)! is a huge number.

How it works

⁴!!X%‘  Main link. Argument: n

⁴       Set the return value to 16.
 !!     Compute (16!)!.
   X    Pseudo-randomly choose an integer between 1 and (16!)!.
        Since (16!)! is evenly divisible by any k ≤ 2**30, it is evenly divisible
        by n+1.
    %‘  Take the result modulo n+1.

Answer 3

Mathematica, 29 bytes

Based on Dennis's Jelly answer.

RandomInteger[2*^9!-1]~Mod~#&

I wouldn't recommend actually running this. 2e9! is a pretty big number...

It turns out to be shortest to generate a huge number that is divisible by all possible inputs and the map the result to the required range with a simple modulo.

Rejection Sampling, 34 bytes

My old approach that led to somewhat more interesting code:

13!//.x_/;x>#:>RandomInteger[13!]&

Basic rejection sampling. We initialise the output to 13! (which is larger than the maximum input 2³⁰) and then repeatedly replace it with a random integer between 0 and 13! as long as the value is bigger than the input.

Answer 4

Brachylog, 9 bytes

≥.∧13ḟṙ|↰

Try it online!

This uses 13! like in Martin Ender's answer (13ḟ is one byte less than 2^₃₀).

ṙ is implemented using random_between/3, which, when digging its source, uses random_float/0 which is linked to random/1 which uses the Mersenne Twister algorithm which is uniform for our purposes.

Explanation

≥.           Input ≥ Output
  ∧          And
   13ḟṙ      Output = rand(0, 13!)
       |     Else
        ↰    Call recursively with the same input

Answer 5

Prolog (SWI), 38 bytes

X*Y:-Z is 2^31,random(0,Z,Y),Y=<X;X*Y.

Works by rejection sampling.

Generate a random number between 0 and 2^31-1 = 2147483647 until one less than or equal to the input has been found.

I feel as if I should be able to use a cut instead of the else, but I can't see how.

Answer 6

Labyrinth, 63 bytes

 ?
 #00}__""*_
 ;    #"  _
{-{=  } "><)
!{ : ;"({ +
@  }}:  >`#

(Thanks to @MartinEnder for help with some heavy golfing here.)

Labyrinth is a 2D language, and its only source of randomness is in a situation like the following:

   x
  "<)
 " "
 " "

Assume the instruction pointer is on the x and moving downwards. It next lands on the <, which if the top of stack is 0 (which is always the case in the actual program above) shifts the current row left by 1:

   "
 "<)
 " "
 " "

The instruction pointer is now on the < moving downwards. At a junction, Labyrinth turns based on the top of stack - negative is turn left, positive is turn right and zero is move forward. If the top of stack is still zero at this point, we can't move forward or backward since there's no path, so Labyrinth will randomise between turning left or turning right with equal probability.

Essentially what the program above does is use the randomness feature to generate 100-bit numbers (100 specified by #00 here) and continue looping until it generates a number <= n.

For testing, it'll probably help to use #0" instead for 10-bit numbers, with the " being a no-op path. Try it online!

Rough explanation:

 ?            <--- ? is input and starting point
 #0"}__""*_   <--- * here: first run is *0, after that is *2 to double
 ;    #"  _
{-{=  } "><)  <--- Randomness section, +0 or +1 depending on path.
!{ : ;"({ +        After <, the >s reset the row for the next inner loop.
@  }}:  >`#

 ^    ^
 |    |
 |    The " junction in this column checks whether the
 |    100-bit number has been generated, and if not then
 |    continue by turning right into }.
 |
 Minus sign junction here checks whether the generated number <= n.
 If so, head into the output area (! is output as num, @ is terminate).
 Otherwise, head up and do the outer loop all over again.

Answer 7

Python, 61 bytes

from random import*
lambda n,x=2.**30:int(randrange(x)*-~n/x)

Edit: Updated to avoid forbidden form

Edit2: Saved 2 bytes, thanks @JonathanAllan

Edit3: Paid 2 bytes for a fully functional solution - thanks again @JonathanAllan

Edit4: Removed f=, saving 2 bytes

Edit5: Saved 1 more byte thanks to @JonathanAllan

Edit6: Saved 2 more bytes thanks to @JonathanAllan

By now, git blame would point at me for the bad things, and JonathanAllan for the stuff that helps.

Edit7: When it rains, it pours - another 2 bytes

Edit8: And another 2 bytes

Answer 8

Python 2, 61 bytes

from random import*
lambda n:map(randrange,range(1,2**31))[n]

Pseudo-randomly chooses integers between 0 and k for all values of k between 0 and 2³¹ - 2, then takes the integer corresponding to k = n.

Answer 9

Batch, 64 bytes

@set/ar=%random%*32768+%random%
@if %r% gtr %1 %0 %1
@echo %r%

%random% only gives 15 bits of randomness, so I have to combine two random numbers. Loops until the random value lies within the desired range, so slow for low n; 98 bytes for a faster version:

@set/a"n=%1+1,m=~(3<<30)/n*n,r=%random%*32768+%random%
@if %r% geq %m% %0 %1
@cmd/cset/a%r%%%%n%

Answer 10

Bash (+coreutils), 44 bytes

/dev/urandom based solution

od -w4 -vtu4</d*/ur*|awk '($0=$2)<='$1|sed q

Will read unsigned 32 bit integers from /dev/urandom, and filter them out with awk until it finds one within a given range, then sed q will abort the pipe.

Answer 11

MATL, 12 bytes

Thanks to @AdmBorkBork and to @Suever for telling me how to disable TIO cache.

`30WYrqG>}2M

Try it online!.

This uses a rejection method: generate a random integer from 0 to 2^30-1, and repeat while it exceeds the input n. This is guaranteed to terminate with probability 1, but the average number of iterations is 2^30/n, and so it takes very long for n significantly smaller than 2^30.

`         % Do...while
  30W     %   Push 2^30
  Yr      %   Random integer from 1 to 2^30
  q       %   Subtract 1
  G>      %   Does it exceed the input? If so: next iteration. Else: exit
}         % Finally (execute right before exiting the loop)
  2M      %   Push the last generated integer
          % End (implicit). Display (implicit)

Answer 12

PowerShell, 35 bytes

for(;($a=Random 1gb)-gt"$args"){}$a

Try it online!

Another rejection sampling method. This is an infinite for loop, setting the value of $a to be a Random integer between 0 and 1gb (= 1073741824 = 2^30), and keeps looping so long as that integer is -greaterthan the input $args. Once the loop is complete, we just put $a on the pipeline and output is implicit.

Note: This will take a long time if the input is a small number.

Answer 13

JavaScript (ES6), 55 54 bytes

f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)

Generates integers in the range [0 ... 2^k - 1], where k is the smallest integer such that 2^k is greater than n. Repeats until the result falls into [0 ... n].

Why?

This is based on the following assumptions:

• Internally, the pseudo-random integer values generated by the JS engine to feed Math.random() are uniform over any interval [0 ... 2^k-1] (with k < 32).

• Once multiplied by an exact power of 2, the IEEE 754 float values returned by Math.random() are still uniform over such intervals.

If anyone can confirm or refute these hypotheses, please let me know in the comments.

Demo

Generates 1 million values in [0 ... 2] and displays the outcome statistics.

f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)

for(i = 0, stat = []; i < 1000000; i++) {
  r = f(2);
  stat[r] = (stat[r] || 0) + 1;
}
console.log(stat.join` `)

Answer 14

Haskell, 70 bytes

import System.Random
g n=head.filter(<=n).randomRs(0,2^30)<$>getStdGen

Not a very efficient algorithm but it works. It generates an infinite list of integers (or floats if needed, because of Haskell's type system) bounded by [0,2^30] and takes the first one less than or equal to n. For small n this can take a long time. The random numbers should be uniformly distributed, as specified in the documentation for randomR so all numbers in the interval [0,2^30] should have the same probability (1/(2^30+1)) therefore all the numbers in [0,n] have the same probability.

Alternate Version:

import System.Random
g n=head.filter(<=n).map abs.randoms<$>getStdGen

This version is terrible but it saves a whole byte. randoms uses an arbitrary range defined by the type to generate an infinite list of numbers. This may include negatives so we need to map it with abs to force them positive (or zero). This is extremely slow for any values of n that aren't absurdly large. EDIT: I realized later that this version isn't uniformly distributed because the probability of getting 0 is worse than the other numbers due to the use of abs. To produce some number m the generator could produce m or -m but in the case of 0 only 0 itself will work, therefore its probability is half of the other numbers.

Answer 15

Jelly, 9 bytes

⁴!Ẋ’>Ðḟ⁸Ṫ

Try it online! - code above wont run on TIO since a range of size 16! must be built first (not to mention the fact that they then need to be shuffled and then filtered!), so this is the same thing on a much smaller scale, repeated 30 times for an input of 3 with a bound of 10.

How?

⁴!Ẋ’>Ðḟ⁸Ṫ - Main link: n
⁴         - 16
 !        - factorial: 20922789888000
  Ẋ       - shuffle random: builds a list of the integers 1 through to 16! inclusive and
          - returns a random permutation via Python's random.shuffle (pretty resource hungry)
   ’      - decrement (vectorises - a whole pass of this huge list!)
     Ðḟ   - filter out if: (yep, yet another pass of this huge list!)
    >     -     greater than
       ⁸  -     left argument, n
        Ṫ - tail: return the rightmost remaining entry.

Note: it would be over a thousand time more efficient for the same byte-count if ȷ⁵ would do what one would naively expect and return ten to the ten, but that is not the case since the ⁵ is not evaluated as a literal ten to be used by the number literal ȷ... but rather two separate literals are parsed, ȷ with it's default exponent of three yielding one thousand, and ⁵ yielding ten.

Answer 16

JDK 9 on jshell, 75 59 bytes

n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny()

Usage

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)

• -16 bytes: Thanks Jakob!
• Assumes that we consider jshell to be a valid runtime environment.
• jshell itself, as a runtime environment, doesn't require explicit imports for core libraries and doesn't require semicolons.
• Returns an OptionalInt. Rules don't specify that return type must be a primitive and I'm considering an OptionalInt to be a valid representation of the result.

Answer 17

PHP, 30 bytes

    while($argn<$n=rand());echo$n;

Run with echo <N> | php -Rn '<code>'.

picks a random number between 0 and getrandmax() (2**31-1 on my 64 bit machine);
repeats while that is larger than the input.

This may take a while ... my AMD C-50 (1 GHz) needed between 0.3 and 130 seconds for N=15.

A faster way for average N (46 bytes):

for(;++$i<$x=1+$argn;)$n+=rand()%$x;echo$n%$x;

or

for(;++$i<$x=1+$argn;$n%=$x)$n+=rand();echo$n;

takes N+1 random integers, sums them up and takes the modulo with N+1.
The C-50 needs approx. 8 seconds for 1 million runs.

An invalid solution for 19 bytes:

echo rand(0,$argn);

Answer 18

Python 2, 72 69 bytes

-3 bytes thanks to xnor (override the id built-in as a variable)

from random import*
n=input()
while id>n:id=randrange(2**30)
print id

Try it online!

randrange(2**30) produces a pseudo-uniformly distributed number (Mersenne Twister 2^19937-1) from the range [0,2³⁰). Since n is guaranteed to be below 2³⁰ this can simply be called repeatedly until it is not greater than the input. It will take a long expected time for very low values of n, but usually works within the a minute even for inputs as low as 50.

Answer 19

Java 8, 84 83 80 71 62 bytes

n->{int r;for(;(r=(int)(Math.random()*(1<<30)))>n;);return r;}

-1 byte thanks to @OliverGrégoire.
-3 bytes thanks to @Jakob.
-9 bytes converting Java 7 to Java 8.
-9 bytes by changing java.util.Random().nextInt(1<<30) to (int)(Math.random()*(1<<30)).

Explanation:

Try it here.

n->{        // Method with integer parameter and integer return-type
  int r;    //  Result-integer
  for(;(r=(int)(Math.random()*(1<<30)))>n;);
            //  Loop as long as the random integer is larger than the input
            //  (the random integer is in the range of 0 - 1,073,741,824 (2^30))
  return r; //  Return the random integer that is within specified range
}           // End method

NOTE: May obviously take very long for small inputs.

Example output:

407594936

Answer 20

Python 3, 51 bytes

Here is a python solution with an unorthodox random source.

print(list(set(map(str,range(int(input())+1))))[0])

Try it online!

So to break this down.

int(input())+1

Gets the input number, and adds 1 to it.

set(range(...))

Creates the set {0, 1, 2, 3, 4, ... n} for all possible results.

print(list(...)[0])

Takes the set, converts it to list, and grabs the first item.

This works because in Python 3, the order of set() is established by PYTHONHASHSEED (can't be obtained but is established on script execution).

Admittedly, I am guessing that this is a uniform distribution, as the hash() value is randomly assigned and I am looking at randomly picking the value with a specific hash(), rather then just returning the hash(input()) itself.

If anyone knows whether this is a uniform distribution, or how I could test that, please comment.

Answer 21

Perl 6, 29 bytes

{first 0..$_,^2**30 .roll(*)}

Inspired by Martin Ender's Mathematica solution.

Generates a lazy infinite sequence of random integers between 0 and 2^30-1, and takes the first one that is between 0 and the input.

Try it online!

Answer 22

05AB1E, 11 bytes

žIÝ.rDI›_Ϥ

Try it online!

Explanation

žIÝ          # push the inclusive range [0 ... 2^31]
   .r        # get a random permutation (pythons random.shuffle)
     D       # duplicate this list
      I      # push input
       ›_Ï   # keep only elements from the list not greater than input
          ¤  # take the last one

As the list [0 ... 2147483648] is too large for TIO, the link uses 1.000.000 instead.

Alternate (on average) much faster 11 byte solution

[žIÝ.RD¹›_#

Try it online

Explanation

[             # start loop
 žIÝ          # push the inclusive range [0 ... 2^31]
    .R        # pick a random integer (pythons random.chiose)
      D       # duplicate
       ¹      # push input
        ›_#   # break if random number is not greater than input
              # implicitly output top of stack (the random number)

Answer 23

Python 2, 89 bytes

l=range(2**31)
import random
random.shuffle(l)
n=input()
print filter(lambda x:x<=n,l)[0]

Explanation

L=range(2**31)      # Create a list from 0 to 2^31 exclusive. Call it <L>.
import random       # Import the module <random>.
random.shuffle(L)   # Use 'shuffle' function from <random> module,
                    # to shuffle the list <L>.
n=input()           # Take the input -> <n>.

print
    filter(         # Create a new sequence,
    lambda x:x<=n   # where each element is less than or equal to <n>.
    ,L)             # from the list <L>.
    [0]             # Take the first element.

This is very inefficient, as it creates 2^31 integers, shuffles and filters them.

I see no point in sharing a TIO link, where it's creating such large lists, so here is a TIO link for n = 100.

Try it online!

Answer 24

R, 37 bytes

which.min(sample(2^30)[0:scan()+1])-1

Takes n from stdin. First it generates a random sample of all the integers in the range, then selects the first n+1 values, finds the index of the minimum, and then subtracts one, to generate a number between 0 and n, inclusive. It won't run on TIO because it can't allocate an array of size 2^30 to sample from.

I'm fairly confident this is uniformly random.

Try it online!

Answer 25

Python 3, 51 bytes

lambda n:randrange(1<<31)*n>>31;from random import*

Attempt this online! Includes a test suite.

Here is a proof that this is fair: https://arxiv.org/abs/1805.10941. It's also much faster than a typical modulo reduction because it's just a multiplication and a shift. (although this isn't as noticeable in Python...)

Uses an interesting approach, is O(1), and is the shortest Python answer yet!

Answer 26

C#, 57 bytes

n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

Anonymous function which returns an integer between 0 and n inclusive.

The smaller the input number, the longer the time to return a random value.

Full program:

using System;

class RandomNumber
{
    static void Main()
    {
        Func<int, int> f =
        n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

        // example
        Console.WriteLine(f(100000));
    }
}

Answer 27

SmileBASIC, 38 bytes

INPUT N@L
R=RND(1<<30)ON N<=R GOTO@L?R

Generates random numbers until it gets one that is smaller than the input.

Answer 28

Ruby, 23 15 23 32 29 bytes

->n{1while n<q=rand(2**30);q}

How it works:

• 1while [...]; executes the statement at least once: 1 before while acts as a nop
• Get a random number in the range 0..2^30-1 (lower than 2^30, as specified)
• Repeat if the number is higher than the input parameter (Could take some time when n is small)

Answer 29

Ohm, 26 bytes

IΩ
D31º#╬D0[>?D-+∞;,

Explanation:

IΩ                 ■Main wire
IΩ                 ■Call wire below

D31º#╬D0[>?D-+∞;,  ■"Real main" wire
D                  ■Duplicate input
 31º#╬D            ■Push random_int in [0..2^31] twice
       0[          ■Push input again
         >?    ;   ■If(random_int > input){
           D-+     ■  remove the random_int
              ∞    ■  recursion
               ;   ■}
                ,  ■Print random_int

Answer 30

Go, 63 61 bytes

import."math/rand"
var n=0;func R(){q:=n;for;q<n+1;n=Int(){}}

Use it like this:

func main() {
    n = 5000
    R()
    print(n)
}

Test it live at the go playground