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 >
Wrap
Text File
|
1991-12-25
|
8KB
|
233 lines
December 22, 1991
Restrictions
This archive and the files in it are: Copyright 1991 by Daniel Wolf
They are NOT Public Domain. All rights are reserved worldwide.
This archive consists of 2 files:
Rand6.Doc the text file you are now reading
Rand executable Amiga CLI/Shell command, version 6 of Rand
This archive is freely distributable if and only if the following conditions
and terms are observed:
1. Absolutely NO commercial use is made, including but not limited to:
a. inclusion or use of any part of Rand or Rand6.doc within any
commercial program
b. inclusion or use of any part of Rand or Rand6.doc within any
commercially marketed 'freely distributable' disk collection
by any 'for profit' business
2. Officially registered, non-profit, Amiga User Groups are exempt from
the above restriction so long as only a nominal (not to exceed $5) charge
is made for any 'club disk' on which Rand AND Rand6.doc appear. The same
applies to Amiga User Group BBS's and non-commercial BBS's (for which no
explicit 'download charge' or 'membership fee' is charged).
3. Permission is hereby granted to post this archive on non-commercial
BBS's and Compuserve, Genie, Bix, UseNet, and the Fred Fish collection.
4. Under no circumstances may this archive be distributed without full
inclusion of both Rand6 and Rand6.doc (this file) so that the origin and
copyright ownership of Rand and Rand6.doc are clearly visible to all. Any
posting of this archive MUST include this Rand6.doc file as well as Rand.
5. Any other posting or use must be with written permission of Daniel Wolf
(address below).
NEW VERSION 6 and SPEED CONSIDERATIONS
This archive is version 6, substantially faster and smaller than the versions
posted earlier. A more rigorous timing analysis was made of this version.
A special timing version was arranged to run the inner loop generating 32768
random 32-bit numbers a total of 1000 times. Here are some results:
System Total Time ~Calc Time #'s/sec nanosec/number
68020 16mhz 64 63 520,000 1920
68040 1.3 18 17 1,930,000 518
68040 2.0 13.5 12.5 2,620,000 381
I've allowed approximately 1 second on each system for program load and
time to write 1 file of 32,768 randoms to ram:. The PP&S 040 was run under
1.3 with 'no copyback' and under 2.0 'with copyback'. The 020 was equipped
with 32-bit ram (Amiga 1000 with Lucas/Frances system). All operations
were done with Rand in ram: and all files were read from and written to ram:.
I've managed to shave the inner loop to less than 10 instructions, and after
some empirical testing against other variations, I think this one is the best
optimized for speed. I'd be interested to learn results on other systems.
Purpose
Rand is a deceptively tiny (500 bytes) powerful random number generator which
is based on the revolutionary new technique published by Marsaglia, Narasimhan,
and Zaman (Computer Physics Communications, Vol 60, 1990, pp 345-349).
In that paper, Marsaglia et al. describe their method and state the
availability of an assembly code version of this random number algorithm
for MSDOS type computers. Of course, we NEED it on the Amiga, so here it is.
This new technique produces extremely long sequences of random number of
very high quality (they meet a wide variety of 'randomness tests') at very
high speed. It is called the 'subtract with borrow, lagged Fibonacci'
technique, but I will refer to it by the initials of its authors, MNZ.
There has been a great deal of interest in random number generators in the
programming community for a variety of reasons and a need for improved
generators is ever present. This program is an implementation of the MNZ
algorithm for Amiga computers, written in optimized 68xxx assembly language.
The small size of Rand makes it easy to incorporate into your C: directory,
from which you can invoke it in AmigaDos scripts and ARexx scripts. It
should be quite beneficial to those who need to generate large quantities
of random numbers for statistical (Monte Carlo simulations) and related
applications.
Usage
Input Requirement
Rand requires a 'seed' (like most other random number generators do), which
can come from any file at least 132 bytes long. The 'seed' file is specified
on the CLI command line by standard Amiga file indirection.
Output Format
The output of this version of Rand one of two formats:
a. a 4K file of 1024 32-bit random numbers in 'raw' form (default)
b. a 8K file of 1024 32-bit random numbers as hex ascii (H option, below).
The output file is also specified by standard Amiga file indirection.
Options
There are two CLI command line options:
a. the command can be followed by a 1 or 0, which specify two alternative
random number sequences (which are equally 'random') for any given seed
b. if you use the 1 or 0 option (and ONLY if you use it) you can also
specify the H (or h) option which will make the output file in hex ascii
format instead of the default 'raw' format.
Command Line Format
The calling format for Rand is:
Rand <seedfile >outputfile
If you wish to use only the 1,0 option, it will look like this:
Rand <seedfile >outputfile 1 or
Rand <seedfile >outputfile 0
If you also wish to specify the output format as HEX ASCII, it looks like:
Rand <seedfile >outputfile 1 H or
Rand <seedfile >outputfile 0 H or
Rand <seedfile >outputfile 1 h or
Rand <seedfile >outputfile 0 h
Remember, if you want to use the H (or h) option, you MUST also use the
1,0 option. The options must be separated by 1 space and in the order
shown above.
Examples
Here's a typical usage:
Rand <c:dir >ram:randoms
will create a file of 4096 bytes (1024 32-bit numbers) called 'randoms'
in your ram: disk. Since everyone has a c:dir file (or at least that
assumption is pretty reasonable on the Amiga), this should always work
as a test situation. You can substitute 's:startup-sequence' for 'c:dir',
etc. Just about any file with at least 132 bytes and some 'variety' in it
will work as a seed file.
More Important Information
Remember, if you always use rand with the same 'seed' file, you'll always
get the same output file of random numbers. In order to get the most out
of Rand, you must use various different 'seed' files to create different
random number sequences.
Since this version of Rand only produces 1024 32-bit numbers, you can
call Rand the first time with some seed file, then call it again with
the previous output file as the seed file, like this:
Rand <c:dir >ram:randoms1
(use the numbers in ram:randoms1, then call Rand again using randoms1 as seed)
Rand <ram:randoms1 >ram:randoms2
(use the numbers in ram:randoms2, then call Rand again using randoms2 as seed)
Rand <ram:randoms2 >ram:randoms1
(use the numbers in ram:randoms1, then call Rand again using randoms1 as seed)
.
.
.
etc.
Simply alternate ram:randoms1 and ram:randoms2 as your source of 1024 random
32-bit numbers and seed file for the next run.
Magic
The amazing thing about the MNZ method is that the 'period' (time before
the sequence repeats) for this random number generator is a truly
astronomical 2^1407! That's right, it will generate a sequence of
10 (followed by 414 zeroes) 32-bit numbers before it repeats!
If you wish to see the mathematical reasoning behind this fact, refer
to the papers by Marsaglia, et al.
The other terrific feature is that this algorithm is FAST (especially
when written in efficient assembler) since it only uses simple subtraction
and some quick memory moves. Other popular random number generators use
at least one multiplication and one division. This method is MUCH faster,
and the 'period' is MUCH longer than other known generators. To paraphrase
Marsaglia, et al., this generator could operate all of Las Vegas' games
of chance for zillions of years and no one ('cept us arithmetic junkies) would
be the wiser.
PrograMagic
This program is only 500 bytes long! It's CLI/Shell only (or you'll CRASH).
Commercial Announcement
If you need commercial applications of this technology for games,
cryptography, single random bits, other sizes of random numbers, etc.,
either licensed source code or custom programming, contact:
Daniel Wolf, Ph.D.
MegageM
1903 Adria
Santa Maria, CA 93454
805-349-1104 Compuserve 70250,626
Alternate versions which generate 1 million or more random numbers at once
and various types of random numbers at one time are available for a nominal
charge.