Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
???
09/10/07 21:37
Read: times


 
#144342 - on uniformity of pseudo- or real-random
Responding to: ???'s previous message
Each uniform random number generator - pseudo or real - produces an uniformly distributed output numbers only in a given range.

Usually, this range is [0, 2^n-1], i.e. 2^n consecutive numbers.

Often, a different range is needed. As long as this subrange is of form [k, 2^m+k-1] (m <= n) i.e. 2^m consecutive numbers, it's easy to scale: simply mod the pRNG output by 2^(n-m) and add k. The mod means in fact to take the lowest m bits of the pRNG output (it does not need to be mod, it can be any similar operation, i.e. any m bits of the pRNG output will do).

But, for any other form of scaling, care must be taken. If you simply mod the output of pRNG by any number which is not power of two, you will add some bias to some of the output numbers, so the output is not distributed perfectly uniformly anymore. It is easy to calculate the difference and it's upon you how will you cope with it (including accepting the difference if it's small enough).

A typical extreme example is a pRNG outputting numbers in the [0, 3] range uniformly; if you mod the result by 3, you will get twice as many 0s than 1s or 2s.

JW


List of 25 messages in thread
TopicAuthorDate
HOWTO generate a uniformly-distributed random nu            01/01/70 00:00      
   how much code/data/idata/xdata space can you...            01/01/70 00:00      
      I can wait till evening            01/01/70 00:00      
      LFSR            01/01/70 00:00      
         OK but            01/01/70 00:00      
            there is no such thing            01/01/70 00:00      
               event triggered Timer reading            01/01/70 00:00      
                  no, well            01/01/70 00:00      
            LFSRs generally suffer from the "bad seed" problem            01/01/70 00:00      
               Maximal-Length LFSR?            01/01/70 00:00      
                  uniformity is not the only requirement on a pRNG..            01/01/70 00:00      
   most rng's            01/01/70 00:00      
      hummm            01/01/70 00:00      
         pseudorandom is NOT random            01/01/70 00:00      
            A Dilbert            01/01/70 00:00      
   Easy way to have it ???            01/01/70 00:00      
      block cipher, in chaining mode...            01/01/70 00:00      
      on uniformity of pseudo- or real-random            01/01/70 00:00      
         what's xtea prng RANGE ?            01/01/70 00:00      
            its not a dedicated pRNG algorithm....            01/01/70 00:00      
               random float ??            01/01/70 00:00      
                  tell us what is the application            01/01/70 00:00      
                     The application is...            01/01/70 00:00      
                        take any 32 bits...            01/01/70 00:00      
                           OK            01/01/70 00:00      

Back to Subject List