Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Use case: I have a random number generator that can generate random numbers in a range that is limited by a number $x$, say $x$ ranges from $2$ to $2^{(n - 1)} - 1$ exclusive. In this case $n$ is $16$, i.e. we can generate a number from $0$ to $32767$ exclusive. Programmers will directly identify the upper bound to be a possitive, signed value of 16 bits.

Now I want to generate a bounded number from $0$ to $y$, where $y$ ranges from $2$ to $2^n - 1$, i.e. we can generate a number from $0$ to $65535$ exclusive. Yes, this is an unsigned value of 16 bits. Is there an algorithm that can do this efficiently? Loops are allowed; the random in the range $0$ to $x$ may be generated repeatedly.

If this is not possible, I have no problem allowing $0$ to $65533$ exclusive because $32766 * 2 = 65532$ and generating $65533$ and $65534$ could significantly increase the complexity.

All generated random values must have a uniform distribution.

share|improve this question
    
Tried quite a few things myself, fortunately I do know a workaround if I can generate 16 bits of full random data with help of 32 bit calculations, but that's not very efficient in this particular case. –  Maarten Bodewes - owlstead May 12 at 19:34
    
"All generated random values must have a normal distribution" is a non-issue, once you have a uniform distribution you can convert it to a normal distribution efficiently via inverse-transform sampling or specialized methods like Box-Muller. Focus on getting a uniform distribution (rejection sampling will probably be fast enough, except perhaps for pathological values of $x$). –  Thomas May 12 at 20:08
    
@Thomas thanks, fixed –  Maarten Bodewes - owlstead May 12 at 22:28

1 Answer 1

up vote 5 down vote accepted

I assume $R(x)$ is the original generator, returning $r$ uniformly distributed with $0\le r<x$ for $x<2^{n-1}$, as does Java's int nextInt(int) for $n=32$; and we want to extend that to $R'(y)$, returning $r$ uniformly distributed with $0\le r<y$ for $y<2^n$. $R$ and $R'$ should treat an argument less than $2$ in the same way (perhaps accept it and return $0$, or reject if somehow). Out of laziness I'll only handle $n$ even and $n>2$, which covers practical use cases.

If $y<2^{n-1}$, $R'(y)=R(x)$ is fine.

If $y=a\cdot b$ with $a>1$ and $b>1$, $R'(y)=b\cdot R(a)+R(b)$ is fine. That is useful when $y$ is known at compilation time and composite.

Else (when $y\ge2^{n-1}$ and prime), there is no method guaranteed to work with a finite number of invocations of $R$, and we must use some iterative method.


Out of my head (not tested), a possible line of action when $y$ is known only at runtime:

  • if $y<2^{n-1}$, return $R(y)$.
  • if $y$ is even, return $2\cdot R(y/2)+R(2)$.
  • if $y=2^n-1$, return $(2^{n/2}-1)\cdot R(2^{n/2}+1)+R(2^{n/2}-1)$.
  • repeat
    • let $r:=R((y+1)/2)$
    • if $R(2)\ne0$, return $r$.
    • if $r\ne0$, return $y-r$.

Notes:

  1. With the assumption that $n$ is even, we can handle $y=2^n-1$ as $(2^{n/2}+1)\cdot(2^{n/2}-1)$.
  2. When $R((y+1)/2)$ is computed, this is valid since $1<(y+1)/2<2^{n-2}$.
  3. At each iteration of the loop (which occurs only for odd $y$), the value returned (if any) is correctly distributed because:
    • $r$ is returned with odds $1/2$, and then is uniform on $[0\dots(y-1)/2]$
    • $y-r$ is returned with odds $1/2-1/(y+1)$, and then is uniform on $[(y+1)/2\dots y-1]$
    • the "repeat" loop continues with odds $1/(y+1)$, which is at most $1/2^{n-2}$, and thus low for practical $n$.

We can lower the expected number of calls to $R$ (by $46\%$ for $n=16$ and $2^{n-1}\le y<2^n-1$) by accumulating $n-2$ uniform bits (and a sentinel) in a variable $b$ surviving across invocations, set to $0$ initially (in the C programming language, that could be static short b = 0; in the body of a function). It is however at the expense of increased complexity, and perhaps of thread-safety, and thus a bad idea in most practical situations! The algorithm (not tested) can become:

  • if $y<2^{n-1}$, return $R(y)$.
  • if $y=2^n-1$, return $(2^{n/2}-1)\cdot R(2^{n/2}+1)+R(2^{n/2}-1)$.
  • repeat
    • let $b:=\begin{cases}R(2^{n-2})+2^{n-2}& \text{if }b<4\\\lfloor b/2\rfloor&\text{otherwise}\end{cases}$
    • let $r:=R(\lfloor(y+1)/2\rfloor)$
    • if $b$ is even, return $r$.
    • if $y$ is even, return $y-1-r$.
    • if $r\ne0$, return $y-r$.
share|improve this answer
    
I've accepted this answer, if I find anything not right in my results, I'll adjust the calculations, it looks OK at first sight but you know how it is with proving randomness. –  Maarten Bodewes - owlstead May 16 at 19:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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