home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12534 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  1.9 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!mips!sdd.hp.com!uakari.primate.wisc.edu!ames!agate!linus!linus.mitre.org!truth!jrv
  2. From: jrv@truth.uucp (Vanzandt)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Scaled random number (Was: Matt Dillon's DICE (Amiga C) and rand() function)
  5. Message-ID: <1992Aug19.175913.29022@linus.mitre.org>
  6. Date: 19 Aug 92 17:59:13 GMT
  7. References: <4476@teslab.lab.oz.au>
  8. Sender: news@linus.mitre.org (News Service)
  9. Organization: The MITRE Corp., Bedford, Ma.
  10. Lines: 39
  11. Nntp-Posting-Host: truth.mitre.org
  12.  
  13. In article <4476@teslab.lab.oz.au> andrew@teslab.lab.oz.au (Andrew Phillips) writes:
  14. >ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
  15. >
  16. >: Suppose you want to generate integers in the range 0..N-1,
  17. >: with each integer being equally likely, and that you have
  18. >: a rand() function which delivers integers in the range 0..RANDMAX
  19. >: with each integer being equally likely.
  20. >: Then r%N will indeed give you integers in the range 0..N-1,
  21. >: but unless (RANDMAX+1)%N == 0, they will NOT be equally likely.
  22. >
  23. >The proper way is to use the most significant digits:
  24. >
  25. >#include <stdlib.h>
  26. >
  27. >#define RANDN(N)    ((int)((rand()*(unsigned long)N)/(RAND_MAX+1)))
  28. >
  29. >Andrew Phillips (andrew@teslab.lab.oz.au) Phone +61 (Aust) 2 (Sydney) 287 6551
  30.  
  31. The division still doesn't give _equally_likely_ integers.  Suppose 
  32. RAND_MAX==7, N==3, and r=rand().  We have the following 8 equally likely
  33. possibilities:
  34.     r    r*3/8
  35.     0    0
  36.     1    0
  37.     2    0
  38.     3    1
  39.     4    1
  40.     5    1
  41.     6    2
  42.     7    2
  43. ...so 0 is more likely than 2.  I believe you must discard the original random
  44. number if r/N >= RAND_MAX/N, then you can use r%N or r*N/(RAND_MAX+1).  
  45. If this is done in a function then three divisions, or else two divisions 
  46. and a multiplication, are required.  If it's done in the calling program 
  47. and N doesn't change, then one of the divisions can be moved outside the loop.
  48.  
  49.                      - Jim Van Zandt <jrv@mbunix.mitre.org>
  50.  
  51. P.S. Should this be in the FAQ?
  52.