home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 594a.lha / rand_v6 / rand6.doc < prev    next >
Text File  |  1991-12-25  |  8KB  |  233 lines
  1. December 22, 1991
  2.  
  3. Restrictions
  4.  
  5. This archive and the files in it are:  Copyright 1991 by Daniel Wolf  
  6.  
  7. They are NOT Public Domain.  All rights are reserved worldwide.
  8.  
  9. This archive consists of 2 files:
  10.  
  11.     Rand6.Doc    the text file you are now reading
  12.     Rand        executable Amiga CLI/Shell command, version 6 of Rand
  13.  
  14. This archive is freely distributable if and only if the following conditions
  15. and terms are observed:
  16.  
  17. 1.  Absolutely NO commercial use is made, including but not limited to:
  18.  
  19.     a.  inclusion or use of any part of Rand or Rand6.doc within any 
  20.         commercial program 
  21.  
  22.     b.  inclusion or use of any part of Rand or Rand6.doc within any
  23.         commercially marketed 'freely distributable' disk collection
  24.         by any 'for profit' business
  25.  
  26. 2.  Officially registered, non-profit, Amiga User Groups are exempt from
  27. the above restriction so long as only a nominal (not to exceed $5) charge
  28. is made for any 'club disk' on which Rand AND Rand6.doc appear.  The same
  29. applies to Amiga User Group BBS's and non-commercial BBS's (for which no
  30. explicit 'download charge' or 'membership fee' is charged).
  31.  
  32. 3.  Permission is hereby granted to post this archive on non-commercial
  33. BBS's and Compuserve, Genie, Bix, UseNet, and the Fred Fish collection.
  34.  
  35. 4.  Under no circumstances may this archive be distributed without full
  36. inclusion of both Rand6 and Rand6.doc (this file) so that the origin and
  37. copyright ownership of Rand and Rand6.doc are clearly visible to all.  Any
  38. posting of this archive MUST include this Rand6.doc file as well as Rand.
  39.  
  40. 5.  Any other posting or use must be with written permission of Daniel Wolf
  41. (address below).
  42.  
  43.  
  44. NEW VERSION 6 and SPEED CONSIDERATIONS
  45.  
  46. This archive is version 6, substantially faster and smaller than the versions
  47. posted earlier.  A more rigorous timing analysis was made of this version.
  48. A special timing version was arranged to run the inner loop generating 32768
  49. random 32-bit numbers a total of 1000 times.  Here are some results:
  50.  
  51. System        Total Time    ~Calc Time    #'s/sec        nanosec/number
  52.  
  53. 68020 16mhz    64        63          520,000    1920
  54. 68040 1.3    18        17        1,930,000     518
  55. 68040 2.0    13.5        12.5        2,620,000     381
  56.  
  57. I've allowed approximately 1 second on each system for program load and
  58. time to write 1 file of 32,768 randoms to ram:.  The PP&S 040 was run under
  59. 1.3 with 'no copyback' and under 2.0 'with copyback'.  The 020 was equipped
  60. with 32-bit ram (Amiga 1000 with Lucas/Frances system).  All operations
  61. were done with Rand in ram: and all files were read from and written to ram:.
  62.  
  63. I've managed to shave the inner loop to less than 10 instructions, and after
  64. some empirical testing against other variations, I think this one is the best
  65. optimized for speed.  I'd be interested to learn results on other systems.
  66.  
  67.  
  68. Purpose
  69.  
  70. Rand is a deceptively tiny (500 bytes) powerful random number generator which
  71. is based on the revolutionary new technique published by Marsaglia, Narasimhan,
  72. and Zaman (Computer Physics Communications, Vol 60, 1990, pp 345-349).
  73. In that paper, Marsaglia et al. describe their method and state the
  74. availability of an assembly code version of this random number algorithm
  75. for MSDOS type computers.  Of course, we NEED it on the Amiga, so here it is.
  76.  
  77. This new technique produces extremely long sequences of random number of
  78. very high quality (they meet a wide variety of 'randomness tests') at very
  79. high speed.  It is called the 'subtract with borrow, lagged Fibonacci'
  80. technique, but I will refer to it by the initials of its authors, MNZ.
  81.  
  82. There has been a great deal of interest in random number generators in the
  83. programming community for a variety of reasons and a need for improved
  84. generators is ever present.  This program is an implementation of the MNZ
  85. algorithm for Amiga computers, written in optimized 68xxx assembly language.
  86. The small size of Rand makes it easy to incorporate into your C: directory,
  87. from which you can invoke it in AmigaDos scripts and ARexx scripts.  It
  88. should be quite beneficial to those who need to generate large quantities
  89. of random numbers for statistical (Monte Carlo simulations) and related
  90. applications.
  91.  
  92.  
  93. Usage
  94.  
  95.     Input Requirement
  96.  
  97. Rand requires a 'seed' (like most other random number generators do), which
  98. can come from any file at least 132 bytes long.  The 'seed' file is specified
  99. on the CLI command line by standard Amiga file indirection.
  100.  
  101.  
  102.     Output Format
  103.  
  104. The output of this version of Rand one of two formats:
  105.  
  106. a. a 4K file of 1024 32-bit random numbers in 'raw' form (default)
  107. b. a 8K file of 1024 32-bit random numbers as hex ascii (H option, below).
  108.  
  109. The output file is also specified by standard Amiga file indirection.
  110.  
  111.  
  112.     Options
  113.  
  114. There are two CLI command line options:
  115.  
  116. a. the command can be followed by a 1 or 0, which specify two alternative
  117. random number sequences (which are equally 'random') for any given seed
  118.  
  119. b. if you use the 1 or 0 option (and ONLY if you use it) you can also
  120. specify the H (or h) option which will make the output file in hex ascii
  121. format instead of the default 'raw' format.
  122.  
  123.         
  124.     Command Line Format
  125.  
  126. The calling format for Rand is:
  127.  
  128. Rand <seedfile >outputfile
  129.  
  130. If you wish to use only the 1,0 option, it will look like this:
  131.  
  132. Rand <seedfile >outputfile 1             or
  133. Rand <seedfile >outputfile 0
  134.  
  135. If you also wish to specify the output format as HEX ASCII, it looks like:
  136.  
  137. Rand <seedfile >outputfile 1 H            or
  138. Rand <seedfile >outputfile 0 H            or
  139. Rand <seedfile >outputfile 1 h            or
  140. Rand <seedfile >outputfile 0 h
  141.  
  142. Remember, if you want to use the H (or h) option, you MUST also use the
  143. 1,0 option.  The options must be separated by 1 space and in the order
  144. shown above.
  145.  
  146.  
  147.     Examples
  148.  
  149. Here's a typical usage:
  150.  
  151. Rand <c:dir >ram:randoms
  152.  
  153. will create a file of 4096 bytes (1024 32-bit numbers) called 'randoms'
  154. in your ram: disk.  Since everyone has a c:dir file (or at least that
  155. assumption is pretty reasonable on the Amiga), this should always work
  156. as a test situation.  You can substitute 's:startup-sequence' for 'c:dir',
  157. etc.  Just about any file with at least 132 bytes and some 'variety' in it
  158. will work as a seed file.
  159.  
  160.  
  161. More Important Information
  162.  
  163. Remember, if you always use rand with the same 'seed' file, you'll always
  164. get the same output file of random numbers.  In order to get the most out
  165. of Rand, you must use various different 'seed' files to create different
  166. random number sequences.
  167.  
  168. Since this version of Rand only produces 1024 32-bit numbers, you can
  169. call Rand the first time with some seed file, then call it again with
  170. the previous output file as the seed file, like this:
  171.  
  172. Rand <c:dir >ram:randoms1
  173.  
  174. (use the numbers in ram:randoms1, then call Rand again using randoms1 as seed)
  175.  
  176. Rand <ram:randoms1 >ram:randoms2
  177.  
  178. (use the numbers in ram:randoms2, then call Rand again using randoms2 as seed)
  179.  
  180. Rand <ram:randoms2 >ram:randoms1
  181.  
  182. (use the numbers in ram:randoms1, then call Rand again using randoms1 as seed)
  183. .
  184. .
  185. .
  186. etc.
  187.  
  188.  
  189. Simply alternate ram:randoms1 and ram:randoms2 as your source of 1024 random
  190. 32-bit numbers and seed file for the next run.
  191.  
  192.  
  193. Magic
  194.  
  195. The amazing thing about the MNZ method is that the 'period' (time before
  196. the sequence repeats) for this random number generator is a truly
  197. astronomical 2^1407!  That's right, it will generate a sequence of
  198. 10 (followed by 414 zeroes) 32-bit numbers before it repeats!
  199.  
  200. If you wish to see the mathematical reasoning behind this fact, refer
  201. to the papers by Marsaglia, et al. 
  202.  
  203. The other terrific feature is that this algorithm is FAST (especially
  204. when written in efficient assembler) since it only uses simple subtraction
  205. and some quick memory moves.  Other popular random number generators use
  206. at least one multiplication and one division.  This method is MUCH faster,
  207. and the 'period' is MUCH longer than other known generators.  To paraphrase
  208. Marsaglia, et al., this generator could operate all of Las Vegas' games
  209. of chance for zillions of years and no one ('cept us arithmetic junkies) would
  210. be the wiser.
  211.  
  212.  
  213. PrograMagic
  214.  
  215. This program is only 500 bytes long!  It's CLI/Shell only (or you'll CRASH).
  216.  
  217.  
  218. Commercial Announcement
  219.  
  220. If you need commercial applications of this technology for games,
  221. cryptography, single random bits, other sizes of random numbers, etc., 
  222. either licensed source code or custom programming, contact:
  223.  
  224. Daniel Wolf, Ph.D.
  225. MegageM
  226. 1903 Adria
  227. Santa Maria, CA 93454
  228. 805-349-1104  Compuserve 70250,626
  229.     
  230. Alternate versions which generate 1 million or more random numbers at once 
  231. and various types of random numbers at one time are available for a nominal
  232. charge.
  233.