Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is stream (sequence) of uniform random integers $x_i$, each integer in $[0,N-1]$ range, where N is not power of 2.
I need to convert it to sequence of integers [0..255] (bytes), such that uniformity in input numbers results in uniformity in output numbers. And non-uniformity in input number results in some non-uniformity in output numbers.

I am thinking about doing $L=\sum{x_i N^{i}}$ (using multiple-precision library), then representing L in base 256 (taking bytes from L in binary). Is this good ? Is there better method ?

share|improve this question
    
Have you considered just truncating the binary representation of $x_i$ and taking only the least significant byte? That's as close as you are going to get to a uniform distribution. No matter what transformation you use, the sequence of bytes will not have a uniform distribution since $N$ is not a power of $2$. –  Dilip Sarwate Jan 11 '12 at 22:22
add comment

2 Answers

It may depend on what you mean by uniformity, but if you mean random and independent with a uniform distribution then you can probably move on to the next issue.

There is a problem that powers of $N$ are not powers of 256 (unless this is an infinite stream) so with your suggestion you cannot be sure that all your bytes are equally likely. There are ways around this involving rejection sampling: e.g. if $N=258$ you might simply ignore every time $256$ or $257$ appears.

If it is an infinite stream of numbers then $L$ will be infinite and it might be better to look at $\sum{x_i N^{-i}}$ written in base $256$ instead. [This illustrates the uniformity issue: there are apparently numbers which may be normal in one base but not another.]

Be aware that in any method, it is possible (though perhaps with probability zero) that you do not find out which way to round the calculation of some bytes. More realistically there is a positive though small probability you will have to wait a long time to find even a few bytes.

share|improve this answer
add comment

If you have a decent random number generator available, then just choose the least $K=2^k>N$ and do the following at each step: generate a random number from $0$ to $K-1$. If it is greater than $N-1$, accept it and write down its bits just halting the stream for this step. If not, discard it, accept one number from the stream, and write down its bits. This may slow you down twice on the intake speed but you gain a lot from getting rid of arbitrarily precision arithmetic. If there is no bias in the original sequence, the new sequence will have none either. If there was a bias in the original one, it can get diluted a bit but still will be present. Also, you can recover the original sequence from the new one (just read your numbers and drop the excessively high ones).

share|improve this answer
add comment

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.