Given a number $$\n ≥ 2\$$, a blackbox function $$\f\$$ that takes no arguments and returns a random integer in the range 0...n-1 inclusive, and a number $$\m ≥ n\$$, your challenge is to generate a random integer in the range 0...m-1 inclusive. You may not use any nondeterministic builtins or behaviour, your only source of randomisation is $$\f\$$.

The number you produce must be uniformly random. $$\m\$$ is not limited to powers of $$\n\$$.

One way to do this could be to generate $$\\operatorname{ceil}(\log_n(m))\$$ random numbers, convert these from base $$\n\$$ to an integer, and reject-and-try-again if the result's greater than or equal to $$\m\$$. For example, the following JS could do this:

function generate(n,m,f){
let amountToGenerate = Math.ceil(Math.log(m)/Math.log(n)) // Calculating the amount of times we need to call f
let sumSoFar = 0;
for(let i = 0; i < amountToGenerate; i++){  // Repeat that many times...
sumSoFar *= n;            // Multiply the cumulative sum by n
sumSoFar += f()           // And add a random number
}
if(sumSoFar >= m){          // If it's too big, try again
return generate(n,m,f);
} else {                    // Else return the number regenerated
return sumSoFar
}
}


An invalid solution could look something like this:

function generate(n,m,f){
let sumSoFar = 0;
for(let i = 0; i < m/n; i++){ // m/n times...
sumSoFar += f()             // add a random number to the cumulative sum
}
return sumSoFar
}


This is invalid because it takes the sum of $$\\frac{m}{n}\$$ calls of f, so the randomness is not uniform, as higher/lower numbers have a smaller chance of being returned.

$$\f\$$ is guranteed to produce uniformly random integers, and can be independently sampled as many times as you want.

Instead of taking $$\f\$$ as a function, you may also take it as a stream or iterator of values, or an arbitrarily long list of values. The ranges may be 1...n instead of 0...n-1.

## Scoring

This is , shortest wins!

• A method to steal: Make a list of m outputs from f, if it has a single 0 output its position, otherwise retry.
– xnor
Aug 28 at 6:33
• @tsh 𝑓 is guranteed to produce uniformly random integers. Aug 29 at 1:12

# Jelly, 6 5 bytes

ÇÐṀḊ¿


Try it online!

A monadic link taking m as its argument and expecting the blackbox function to be in the previous link (e.g. header on TIO). Thanks to @JonathanAllan for pointing this out as per this meta post and also for saving a byte with a suggested switch to 1 indexing!

## Explanation

      | Implicit range 1..m
Ḋ¿ | While list length > 1 (literally while the list with its first member removed is non-empty):
ÐṀ   | - Take the list member(s) that are maximal when:
Ç     |   - The supplied function is run for each list member


If the function had to be provided as an argument, here is an alternative:

# Jelly, 8 bytes

ṛ⁴V$ÐṀḊ¿  Try it online! A full program taking m and the Jelly code for f as its two arguments. If it’s mandatory to also take n, this can be provided as an (unused) third argument. ## Explanation  | Implicit range 1..m Ḋ¿ | While list length > 1 (literally while the list with its first member removed is non-empty):$ÐṀ   | - Take the list member(s) that are maximal when:
ṛ⁴V      |   - The supplied function is run for each list member


# Previous answer: Jelly, 16 bytes

³lĊ⁵V¤€ḅʋ⁴¤<³¬$¿  Try it online! A full program that takes n, m and the Jelly code for f as its arguments and prints the resulting random number to STDOUT. ## Explanation  <³¬$¿ | While not < m:
³       ʋ⁴¤      | - Do the following, taking m as the left argument and n as the right:
l               |   - m log n
Ċ              |   - Ceiling
⁵V¤€          |   - Execute f that many times
ḅ         |   - Convert from base n


# Wolfram Language (Mathematica), 40 39 bytes

r&@While@!(r=Nest[nn#3+#2[],0,#])<#&


Try it online!

Input [m, f, n]. Interprets m random digits in base n until the result is in [0, m).

# J, 3732 26 bytes

1 :'$:@[]@.(=&#)I.@:u@$~'


Try it online!

-6 bytes thanks to xnor's suggested method.

Will overflow the stack for larger inputs since it recurses, but works in theory.

# base-n method, modified, 37 32 bytes

1 :'([#.u@#~)/@[^:(]>:1{[)^:_&_'


Try it online!

Uses suggested method, except instead of taking the log first just generates m random base-n digits. This makes it much slower, but saves 5 bytes.

The solution is a J adverb, which modifies the black box function, and takes n as the left arg and m as the right arg.

# base n method, fast, 37 bytes

1 :'([#.>.@^.u@#[)/@[^:(]>:1{[)^:_&_'


Try it online!

# Husk, 1715 13 bytes

Thanks to xnor for the inspiration for the method: here it's taken to an even-more-inefficient extreme by repeatedly generating m random numbers until all except one are zero, and the only non-zero one is 1

€1ḟo=1ΣCm%₁∞


Try it online!

Husk is usually rather badly-suited for challenges involving randomness, since it has no built-in random number generator. So it's very welcome to have a challenge where a random number generator is assumed as a black-box function!

In this case, the black-box random number function is assumed to be located on line 2 (called using the Husk command "₁").
However, obviously, without actually having this function it's tricky to test the code, so the TIO link substitutes the last few bytes m%₁∞ and input n for a pre-generated-by-me list of random integers between zero and one (so n equals 2).

             ∞       # infinitely repeat arg1;
m           # now, for each element n of this list
%₁        # call black-box function ₁, and return the result modulo n;
C            # now cut this infinite list into sublists of length m = arg2
ḟo                 # Return the first sublist for which
Σ              # the sum
=1               # is  equal to 1;
€1                   # what's the index of 1 in this sublist?


Note: the m%₁∞ construction to get the infinite list of random numbers might seem (and is) a bit clunky. This is because (I think), not having any non-deterministic functinos, Husk doesn't have or normally need a higher-order function that will repeat a particular function that takes no arguments.
Luckily in this case, we know that the output of our black-box function is unchanged modulo n, so we can 'use-up' an argument without changing the output.
Here's a Try it online link to the m%₁∞ bit on its own, here with a function on line 2 that simply returns the number 7 each time it's called. Try to pretend that this is a random number...

# R, 7069 62 bytes

(or R>4.1, 56 55 bytes)

Edit: -7 bytes thanks to pajonk

function(m,f){while(sum(F)!=1)for(i in 1:m)F[i]=!f();which(F)}


Try it online!

Port of my Husk answer xnor's approach. Keeps generating sequences of m random numbers until we get one that contains a single 0: then we output the position of the 0. Obviously this is not very efficient, but at least its significantly better than waiting for sequences of all zeros with a single 1 (previous version)...

As explained by Nick Kennedy in his R answer, R] version >4.1 lets us exchange "function" for "\" to save 7 bytes, but unfortunately we can't link to it on TIO or rdrr.io (yet).

• For R<4.1 62 bytes (this approach matches 55 bytes in R>=4.1) Aug 29 at 6:18
• @pajonk - Thanks! Aug 29 at 6:48
• crossed out H is still H Aug 31 at 19:35

# Japt, 12 10 bytes

Based on xnor's suggested method in the challenge comments. Takes m as the first input n as the second and assigns f to variable W. Outputs a singleton array

ÈÊÉ}f@oW ð


Try it or check the distribution over 1000 runs (warning: may take a while to complete)
(All 3 inputs are taken in the header, where each line is assigned to one of Japt's input variables in order. The first line is m, the second n and the 3rd f. Doing this makes no difference to the main programme, saving no bytes; it's done purely to keep everything in one place for easier testing as functions cannot be taken as direct input by Japt.)

## Black box function W

{Vö     :Implicit input of integer V=n
{       :Function
Vö     :  Random int in [0,V)


## Main programme

ÈÊÉ}f@oW ð     :Implicit input of integer U=m
È              :Left function, taking an array as argument
Ê             :  Length
É            :  Subtract 1
}           :End left function
f          :Run the right function continuously, returning the first result that returns falsey (0) when passed through the left function
@         :Right function
o        :  Range [0,U)
W       :  Run each through W
ð     :  0-based indices of truthy (non-zero) elements

• The 4-byte version seems distinctly non-uniform... Aug 28 at 18:22
• Thanks, @DominicvanEssen, meant to remove that after running a similar distribution test over a few runs of 10k; rarely did 2 make an appearance at all, 1 showed up once and 0 never featured. Aug 28 at 18:50

m!l|[x]<-[x|(x,1)<-zip[1..m]l]=x|1>0=m!drop m l


Try it online!

Implements xnor's algorithm

Make a list of $$\m\$$ outputs from $$\f\$$, if it has a single $$\0\$$ output its position, otherwise retry.

However we don't need to make a list since we take a list as the input.

We also use $$\1\dots n\$$ ranges because it saves us 2 bytes.

• For some reason it always seems to output 3 (sorry I don't know Haskell if I am wrong please correct me) Aug 28 at 8:03
• @wasif That's because 3 is the correct answer for the test data provided on TIO. Aug 28 at 8:04

# Python 3.8 (pre-release), 72 bytes

f=lambda m,g:(l:=[g()for x in"1"*m]).count(1)==1and-~l.index(1)or f(m,g)


Try it online!

Uses @xnor's method

-6 and fix thanks to @ovs

Generates the blackbox function for m times, and try to pick the index of 0 from it, if not present recurse.

Looks like the relevant function Dosen't need to take n at all, because it is hardcoded inside g()

Also it is needed to check if list has only one zero, so the choosing remains uniform

• I think it's necessary to check that the list has exactly one zero, because otherwise taking the leftmost one biases towards smaller outputs.
– xnor
Aug 28 at 7:44
• @xnor oh sorry edited now Aug 28 at 7:46
• @ovs I wonder why it dosen't return 0, 0 can be even in the first position of the random items list, then where is the problem? Aug 28 at 8:05
• If l.index(0) evaluates to 0, this is falsy and or f(m,g) results into a recursive call. I think changing to 1-indexing is the easiest fix: tio.run/…
– ovs
Aug 28 at 8:10
• Thank you @ovs !! Aug 28 at 9:12

# R >= 4.1, 67 64 bytes

\(m,f,x=1:m){while(x-max(x))x=x[max(y<-sapply(x,\(z)f()))==y];x}


Try it online!

An R translation of my Jelly answer. TIO link uses function in place of \ since TIO isn’t on R 4.1 yet.

Thanks to @DominicVanEssen for saving 3 bytes!

If it were permissible to require that the Blackbox function take a single unused argument, this would do for 61:

# R >= 4.1, 64 61 bytes

\(m,f,x=1:m){while(x-max(x))x=x[max(y<-sapply(x,f))==y];x}


Try it online!

• Save 3 bytes by rearrangement and changing to while(x-max(x)) Aug 28 at 21:28

# JavaScript (V8), 6361 60 bytes

(m,f,r=(i=m,p)=>i?f()?r(i-1,p):p?r():r(i-1,i):p||r())=>r()-1


Try it online!

Using xnor's method. The recursive function r(i,p) counts down from i = m while i > 0. If finds a zero f() it records position i as p except if there is already a p it restarts by calling r(). If i gets to zero and there is a p it returns p-1 as the result otherwise it restarts.

• Nice answer! By the way, you don't need to take n if you're not using it. Aug 29 at 10:54
• Thanks @emanresu that saves 2 bytes Aug 29 at 11:03
• "The ranges may be 1...n instead of 0...n-1" so I think you can just return p to save another 2 bytes...? Aug 29 at 11:34

# Python 3.8 (pre-release), 70 bytes

h=lambda m,n,f:h(m,n,f)if(s:=sum(n**k*f()for k in range(m)))>=m else s


Try it online!

Generates a random number up to n^m (always larger than m) with n invocations of f, then retries if the result is >=m.

Blows up the stack for large n and m, because n^m is much larger than m.

# Charcoal, 16 bytes

ＮθＷ⊖№υ⁰≔ＥθＮυＩ⌕υ⁰


Try it online! Link is to verbose version of code. Uses the method @xor suggested in a comment to the question. Takes m and a stream of random integers as input. Explanation:

Ｎθ


Input m.

Ｗ⊖№υ⁰


Repeat until the predefined empty list contains exactly one zero.

≔ＥθＮυ


Input m random integers to the predefined empty list.

Ｉ⌕υ⁰


Output the position of the zero.

24 bytes for fastest code:

ＮθＮη≔ηζＷ¬‹ζη≔↨Ｅ↨⊖ηθＮθζＩζ


Try it online! Link is to verbose version of code. Takes input as a stream of random integers. Explanation:

ＮθＮη


Input n and m.

≔ηζ


Start with m as the trial result (because we know it is too big).

Ｗ¬‹ζη


Repeat until a usable result is achieved.

≔↨Ｅ↨⊖ηθＮθζ


Input the minimum number of random digits (obtained by converting m-1 to base n) and convert that to base n.

Ｉζ


Output the final random integer.

# APL(Dyalog Unicode), 19 bytes SBCS

Implements the algorithm suggested by xnor.

{⍸1=∘⍺⍺¨⍣{1=+/⍺}⍳⍵}


Try it on APLgolf!

The blackbox function is called with dummy arguments it ignores, which I think should be fine as there is no way to pass a niladic function to an operator.

⍳⍵ create a range from 1 to n

¨ for each value in the current list ...
⍺⍺ call the blackbox function ...
1= and compare the result to 1 ...
⍣{1=+/⍺} until the result sums to 1

⍸ get all indices of 1's in the resulting boolean mask. This returns a singleton value

3 bytes can be saved by using a full program instead of a dop, but this is quite inconvenient to use:

⍸1=∘⎕¨⍣{1=+/⍺}⍳⎕


Try it on APLgolf!

# Ruby, 60 bytes

f=->n,g,m,r=0,z=1{z>m ?r<m ?r:f[n,g,m]:f[n,g,m,r*n+g[],z*n]}


Try it online!

Use the log() approach, with a recursive function: z is the maximum possible random number for a given iteration, r is the current accumulated value.

# C (gcc), 76 $$\\cdots\$$ 70 67 bytes

i;c;g(n,m,f)int(*f)();{for(;n;)for(n=i=m;i--;)!f()?n-=m,c=i:0;n=c;}


Try it online!

Saved 3 bytes thanks to att!!!

Uses xnor's idea by repeatedly calling $$\f()\$$ $$\m\$$-times and if $$\f()\$$ returns $$\0\$$ once and only once, then returns the time (with $$\0\$$ being the last time and $$\m-1\$$ being the first) that $$\f()\$$ was $$\0\$$.

• 67 bytes
– att
Aug 28 at 18:33
• @att Nice one - thanks! :D Aug 28 at 21:30

# JavaScript (Node.js), 60 bytes

(n,f,m)=>(g=p=>p*m/d^-~p*m/d?g(p*n+f(),d*=n):p*m/d)(0n,d=1n)


Try it online!

Signature: (n: BigInt, f: () => BigInt, m: BigInt) => BigInt

Input / Output BigInt values.

And it would be 47 bytes if we can assume infinite precision of floating point numbers:

n=>f=>g=(m,p=0)=>p*m^-~p*m?g(m/n,p*n+f()):p*m|0


Try it online!

• To my understanding: The second approach generate integers in range $\left[0, m\right)$ with propability $\frac{1}{m}\pm2^{-53}$ each.
– tsh
Aug 30 at 7:40

# Vyxal, 29 bytes

{|n÷£$•⌈(¥†⅛)¾nhβ:nṪt>nh(¼_)}  Try it Online! This is a whole bunch of yucky stuff that is lowkey disturbing. I really need to make functions nicer to deal with in the rewrite. A lambda submission, that takes a single argument, [n, m, f]. ## Explained {|n÷£$•⌈(¥†⅛)¾nhβ:nṪt>nh(¼_)}
{|                             # while the top of the lambda stack is truthy:
n÷                           #   push all the contents of the input onto the stack
£                          #   and place "f" into the register.
\$•⌈                       #   push ceil(log_n(m))
(¥†⅛)                  #   and that many times, push the result of f() onto the global array
¾                 #   push the global array, containing ceil(log_n(m)) numbers
nhβ              #   and convert from base n
:nṪt>         #   push ^ > m
nh(¼_)   #   and clear the global array
}  # close the while loop (we need this because lambda submission)

• If you actually wrap it in a lambda you can save a byte since functions autocall, so the closing is unnecessary. Aug 28 at 7:17

# JavaScript, 55 53 bytes

Takes arguments by currying, i.e. f(r)(m), where r is the black-box randomisation function. The first 3 bytes could be removed by stipulating that the function be pre-assigned to r.

r=>g=(m,y=x=m)=>y?g(m,--y,r()||(--x,z=y)):m+~x?g(m):z


Try it online! (change the values of n & m in the header)