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.

For a project I am working on, I have access to a CSPRNG that outputs a random integer in the interval $[0, 2^n-1]$ for any integer $n$ greater than 0. I cannot use the zero values, so I have my RNG code in a while loop that runs until the random number is !==0. For small $n$ it is very likely that the while loop will run more than once, even more than twice (for $n=8$, the probability is $1/65536$). While this is not the bottleneck in my program, I want to eliminate the while loop and replace it with a linear transformation on the the generated random integer to get the integers I need in $[1, 2^n-1]$.

Is there a transformation that can be performed on the interval $[0, 2^n-1]$ to yield integers in $[1, 2^n-1]$ while retaining the uniform distribution of the random numbers?

(Would this be better posted in math.se?)

share|improve this question
    
Are you sure that your PRNG really has an output range of $2^{n-1} + 1$ different values (e.g. that $2^{n-1}$ itself is a possible value)? This looks a bit unusual. –  Paŭlo Ebermann Dec 15 '12 at 19:02
    
@PaŭloEbermann you are correct, I entered the interval incorrectly. Fixed now, thank you. –  ampersand Dec 15 '12 at 19:06

2 Answers 2

up vote 6 down vote accepted

Assuming that $n > 1$ so as to avoid a trivial special case, there is no function $g(\cdot)$ (linear or otherwise) that will transform a discrete random variable $X$ uniformly distributed on $\{0,1, 2, \ldots, 2^{n}-1\}$ into a discrete random variable $Y$ uniformly distributed in $\{1, 2, \ldots, 2^{n}-1\}$. This is because each value of $X$ has probability $2^{-n}$ attached to it, and this gets mapped onto the $Y$ value $g(X)$. Thus, for any $m \in \{1, 2, \ldots, 2^{n}-1\}$, $P\{Y=m\}$ is necessarily an integer multiple of $2^{-n}$ including, possibly, a zero multiple. It follows that the best one could do is to get a random variable $Y$ that takes on all values in $\{1, 2, \ldots, 2^{n}-1\}$ except one with equal probability $2^{-n}$, and this exceptional value occurs with probability $2\times2^{-n}=2^{-(n-1)}$.

On the other hand, if $X$ were a continuous random variable uniformly distributed on the interval $[0,2^n-1]$, the answer would be easy: $Y = 1+\frac{2^n-2}{2^n-1}X$ is a continuous random variable uniformly distributed on the interval $[1,2^n-1]$.

share|improve this answer
    
You must exclude $n=1$, because it is possible to generate a $Y$ taking the single value $1=2^1-1$ from pretty much anything. Also in "$n\in\{1,2,\ldots,2^{n}-1\}$" the left $n$ is not meant to be the same as the right $n$. My demonstration would be that in order for a suitable mapping to exist, $2^n-1$ (cardinality of destination) must divide $2^n$ (cardinality of source), and that's impossible for $n>1$. I upvoted nevertheless. –  fgrieu Dec 17 '12 at 17:57
    
@fgrieu Thanks for the comment about $n > 1$, the bad choice of notation, and the upvote. I have edited my answer to incorporate your corrections. –  Dilip Sarwate Dec 17 '12 at 19:16

No, there is no way to do it the way you want.

Just stick with the while loop. There is nothing wrong with using a while loop. As you seem to realize, the while loop will almost never execute more than one iteration, so it will perform extremely well. You don't say why you find the straightforward solution (the while loop) problematic, so I'm sticking with my answer: just use the while loop.

share|improve this answer

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.