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

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.
• How are you going to confirm that the output is uniformly random? It may be that a given language / library will output uniformly random numbers, but manipulation could result in non-uniform output. (e.g. rng() provides 0-100, if n = 75, and function is rng()%75, then 0-25 will be more common...) Mar 1, 2017 at 16:12
• @Baldrickk By the wisdom of crowds :) We can only read the code and think about it.
– user9206
Mar 1, 2017 at 16:13
• The sad conclusion of asking the simplest possible probability-theory question: randomness and probability are very poorly understood. :( (And reading rules is hard, apparently.) Mar 1, 2017 at 22:11
• This comes to mind: Random Number Mar 2, 2017 at 9:05
• Why did you accept the x86 answer when there are three shorter ones? Mar 30, 2017 at 16:30

# Golang, 8478 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))
}

• if you use import."math/rand" then Int31 is available in the global namespace and you can save 4 bytes, also intis guaranteed to be at least 32 bits, saving you another 6 bytes Mar 1, 2017 at 13:18
• Use := syntax for another 3 bytes Mar 1, 2017 at 13:30
• Using int instead of int32 doesn't save any bytes since we need to cast the result of Int31() - 3*int + () = 11 bytes versus 2*int32 = 10 bytes. Mar 1, 2017 at 21:53
• No need to cast, there is an Int() function in the rand package, also, you can remove the space after import Mar 2, 2017 at 8:59

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

# 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


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

• Welcome to Code Golf! This looks like a really neat language. I have a bounty for +100 for interesting new languages, so when you finish the interpreter let me know! Jun 5, 2021 at 14:31
• @RedwolfPrograms I may not get started on the interpreter until late June. Jun 6, 2021 at 23:52
• From your explanation, it seems as if the r function is using two arguments, 0 and , (the input), to pick a random number in that range. If so, this unfortunately contravenes rule 2 of the challenge. Jun 12, 2021 at 11:22

# 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)
{
...

/* 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
{
if (s->source)
else
}


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

• Isn't this giving the input as an argument to your random number generator? Feb 28, 2017 at 11:46
• Even if this is not valid, please submit another bash answer!
– user9206
Feb 28, 2017 at 11:48
• @MartinEnder well, not directly, it just uses the input to define the upper limit for the generated integer range and jot will arrange for all the values in the range to appear in the output with an equal probability (that's probably borderline, but still). Feb 28, 2017 at 11:52
• If I dig deep enough into any random number generator I'm sure I'll find a call into a lower-level RNG that doesn't directly use the original argument. The point of the challenge is to obtain an arbitrary-size uniform distribution from a fixed -size distribution, which you're still not doing. Mar 1, 2017 at 21:56

# 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