home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / sys / atari / st / 20853 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  2.9 KB
  1. Xref: sparky comp.sys.atari.st:20853 comp.sys.atari.st.tech:6796
  2. Path: sparky!uunet!mcsun!uknet!yorkohm!minster!mjl-b
  3. From: mjl-b@minster.york.ac.uk
  4. Newsgroups: comp.sys.atari.st,comp.sys.atari.st.tech
  5. Subject: Re: Assembler routine that generates random numbers?
  6. Message-ID: <727706004.2969@minster.york.ac.uk>
  7. Date: 22 Jan 93 12:33:25 GMT
  8. References: <1993Jan20.203516.18565@prime.mdata.fi>
  9. Reply-To: mjl-b@minster.york.ac.uk (Mathew Lodge)
  10. Organization: Department of Computer Science, University of York, England
  11. Lines: 49
  12.  
  13. In article <1993Jan20.203516.18565@prime.mdata.fi> paetau@mits.mdata.fi (Rasmus Paetau) writes:
  14. >Does anybody know how to generate random numbers on a computer? I know
  15. >of the GEMDOS/BIOS/XBIOS call that does that, but I wonder if it could
  16. >be done faster?
  17.  
  18. The XBIOS call uses the "linear congruential" method of generating pseudo-
  19. random numbers, which works as follows:
  20.  
  21. R(n+1) := [R(n) * a] mod b
  22.  
  23. (Where R(n) is the n'th random number, R(n+1) the n+1'th number, etc)
  24.  
  25. The idea is to choose values of a and b such that long sequences of
  26. non-repeating pseudo-random numbers are obtained. From a computational
  27. viewpoint, it makes sense to make b a power of 2 since the modulo function
  28. then reduces to a simple AND instruction. There are also rules for choosing
  29. good values for a.
  30.  
  31. The XBIOS call is pretty quick -- it's an assembler implementation of the
  32. above, and you're not going to write one that's much quicker! The thing that
  33. takes the time (on a 68000 at least) is the multiplication. There are other
  34. methods that use shift-then-XOR (see the book references below).
  35.  
  36. I remember (it's a long time since I disassembled the code) that when the
  37. XBIOS routine is first called, the generator is seeded with a new number --
  38. but I forget where that number comes from.
  39.  
  40. >I'm supposed to do a program that has to do with
  41. >probability and such things, and I'd like a fast and flexible random
  42. >routine in assembler.. so if anybody has ideas, they're welcome!
  43.  
  44. If you want *truly* random numbers (as opposed to pseudo-random numbers),
  45. then you're going to have to build some hardware. Commercial random number
  46. hardware works by amplifying the quantum noise in a resistor and
  47. thresholding it to generate a stream of random bits.
  48.  
  49. There is quite a lot of literature about random number generation. You might
  50. look at the "Numerical Recipes" book by Press, Flannery et al. (but it has
  51. some mistakes in the section on random numbers). Any good numerical
  52. algorithms book should cover random numbers -- Sedgewick's "Algorithms" has
  53. a small section on it (and it covers the shift-XOR method).
  54.  
  55. >| Rasmus Paetau (paetau@mits.mdata.fi) | I still believe in Falcon030 |
  56.  
  57. Mat
  58.  
  59. | Mathew Lodge                      | "What think you, my lord, of... Love?" |
  60. | mjl-b@minster.york.ac.uk          | "You mean rumpy-pumpy?"                |
  61. | Langwith College, Uni of York, UK |  -- Blackadder II                      |
  62.