On Mon, 15 Sep 1997 15:59:24 +0100 Brian Jones writes: >I now have the David Reinagels 16bit Random Number algorithm - >thanks. > >I am looking to generate a random number in the range 0-1, then 0-2, >then 0-3,...... upto 0-49. > > I figured the easiest way might be for range 0-n > >if n<=15 sum first n+1 bits in rand (16 bit number) [...] Results based on "summing the bits" won't be uniformly distributed. There is only one number having zero ones, 16 have one one, more have 2, etc. up to results of 7, 8, or 9 which are most likely. Then the likelyhood of finding larger numbers of ones decreases until there is only a 1/2^16 chance of getting a result of 16. Also, a 16-bit linear feedback shift register can never contain all zeros (it will become stuck there), so the result of 0 will never occur. I see two reasonably simple ways to generate a number from 0 to n: 1) Crank the register 6 times and take the low 6 bits as a random number from 0 to 63. If this result is <=n, keep it, otherwise repeat until an in-range result occurs. This method is simple but it takes a variable and perhaps long time to come up with a result, especially for small n. It could work well if n is only slightly less than 63. Enhancements such as using only enough bits to guarantee a result >=n is possible (i.e. log2(n) bits) would help reduce the number retries. 2) Crank the register and divide new contents by n+1, remainder will be a number from 0 to n. This should have almost uniform distibution, except 0 won't be found quite as often as the others. Cranking the register more than once will make the results less predictable, though I'm not sure how many times (on the order of log2(n) I suppose) are necessary. A divide where the denominator (and thus remainder) fit in 8 bits is reasonably fast and easy to do on a PIC. These were only for "casual" random munbers for Morse code practice as I remember. Using only a 16-bit register doesn't generate a lot of "randomness". >For 43<=n<=50 I will probably have to generate 2 random nos and add >(eg for 0-50 generate one in range 0-15 and one 0-35 and add). Again this is not evenly distributed. The sum of uniformly distributed munbers approaches a normal (bell-shaped curve) distribution; results in the mid-range are most likely. This is exactly the same problem as taking the sum of the bits of a number, since they are uniformly distributed between 0 and 1.