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

Golang, 84 78 71 bytes

import."math/rand"
func R(n int)int{q:=n+1;for;q>=n;q=Int(){};return q}

Simple rejection sampling.

Note: since the math/rand seed is a constant 1, the caller must seed unless a constant result is desired.

Test: https://play.golang.org/p/FBB4LKXo1r No longer practically testable on a 64-bit system, since it's returning 64-bit randomness and using rejection testing.

package main

import "fmt"
import "time"

/* solution here *//* end solution */

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}

Answer 2

Braingolf, 16 bytes

Uv2.# ,-^r[R>v]R

Try it online!

Takes longer than 60 seconds on TIO, but will terminate in a finite amount of time

Explanation

Uv2.# ,-^r[R>v]R  Implicit input from commandline args
U                 Pop top of stack and push range 0...n
 v                Switch to stack 2
  2.              Push two 2s
    #<space>      Push 32 (codepoint of space)
      ,           Swap top 2 items on stack
       -          Subtract top of stack from 2nd to top
        ^         Raise 2nd to top of stack to top of stack
                  This whole bit makes 2^30 on the 2nd stack
         r        Pops top of stack and pushes a random integer <= to popped item
                  This uses Python3's randrange, between 0 and the popped item
          [...]   While loop runs X times where X is the previously generated random number
           R>     Move top of stack1 to bottom of stack1
             v    Switch back to stack2 for loop counting
               R  Switch back to stack1 for implicit output
                  Implicit output of top of stack

So in short, this generates range [0...n], then generates a random number less than or equal (<=) to 2^30, it then rotates the range that number of times, and outputs the top of the stack at the end.

Answer 3

MMIX, 36 bytes (9 instrs)

Obvious rejection sampling method (Java version). Assumes TRAP 82,78,71 gets a randomly generated uint64_t from the OS.

(jxd)

00000000: 36010000 f7010000 00524e47 1e02ff00  6¢¡¡ẋ¢¡¡¡RNGœ£”¡
00000010: fe020006 26ffff02 32ffff01 45fffffb  “£¡©&””£2””¢E””»
00000020: f8030000                             ẏ¤¡¡

Disassembly:

rndr    NEGU $1,0,$0        // y = 2^64 - n
        PUT  rD,0
0H      TRAP 82,78,71       // loop: tmp = sysrand()
        DIVU $2,$255,$0
        GET  $2,rR          // z = tmp % n
        SUBU $255,$255,$2   // tmp -= z
        CMPU $255,$255,$1
        BP   $255,0B        // if(tmp > y) goto loop
        POP  3,0            // return n

Bonus: version from https://arxiv.org/pdf/1805.10941.pdf (except that we always calculate the remainder):

00000000: f7010001 e3010000 1e010100 fe010006  ẋ¢¡¢ẉ¢¡¡œ¢¢¡“¢¡©
00000010: 00524e47 1aff00ff 32ffff01 41fffffd  ¡RNGȷ”¡”2””¢A””’
00000020: fe000003 f8010000                    “¡¡¤ẏ¢¡¡

rndr    PUT  rD,1
        SET  $1,0
        DIVU $1,$1,$0
        GET  $1,rR          // r = 2^64 % n
0H      TRAP 82,78,71       // loop: tmp = sysrand()
        MULU $255,$0,$255   // rH:tmp = tmp * n
        CMPU $255,$255,$1
        BN   $255,0B        // if(tmp < r) goto loop
        GET  $0,rH
        POP  1,0            // return rH

Answer 4

CBL(not COBOL), 4 5 bytes

CBL is a 2d array-based language that I am working on. It has no interpreter (yet), but I plan to make one soon. The code that I have created may not be up to date with the current progress on the language, but I will try. I will also explain the code.

CBL has gone through some major changes recently. This is the updated version.

’0’ſr

A breakdown of this is as follows:

'0'ſr

'0'   «--numeric literal 0
   ſ  «--previous value (not the 0. it is the value from the previous link
    r «--random function takes the first two as input

This should solve the problem with rule no.2

As long as the interpreter uses uniform randomness (which it will), this should count. If you have any questions or suggestions, leave a comment.

Answer 5

Bash + coreutils, 20 bytes

Golfed

seq 0 $1|shuf|sed 1q

shuf - generate random permutations

Shuf will use the following code: to generate permutations:

permutation = randperm_new (randint_source, head_lines, n_lines);

which ends up in randint_genmax

/* Consume random data from *S to generate a random number in the range
0 .. GENMAX.  */

randint
randint_genmax (struct randint_source *s, randint genmax) 
{
      ...

      randread (source, buf, i);

      /* Increase RANDMAX by appending random bytes to RANDNUM and
         UCHAR_MAX to RANDMAX until RANDMAX is no less than
         GENMAX.  This may lose up to CHAR_BIT bits of information
         if shift_right (RANDINT_MAX) < GENMAX, but it is not
         worth the programming hassle of saving these bits since
         GENMAX is rarely that large in practice.  */
      ...
}

which, in turn, will read a few bytes of the random data from the low-level source of randomness:

/* Consume random data from *S to generate a random buffer BUF of size
   SIZE.  */

void
randread (struct randread_source *s, void *buf, size_t size)
{
  if (s->source)
    readsource (s, buf, size);
  else
    readisaac (&s->buf.isaac, buf, size);
}

i.e. at the low-level, there is no direct dependency between the shuf input value and the data read from the source of randomness (aside from computing the required byte buffer capacity).

Answer 6

Thunno 2 +, 5 bytes

ƓwwɼŒ

Try it online!

Port of Dennis's Jelly answer. Just like that answer, this won't finish for a very long time since \$(16!)!\$ is so big.

Explanation

ƓwwɼŒ  # Implicit input
       # Increment implicitly
Ɠ      # Push 16 to the stack
 ww    # Take the factorial twice
   ɼ   # Random item from [1..that]
    Π # Modulo by (input + 1)
       # Implicit output