mdr@reed.UUCP (Mike Rutenberg) (03/18/87)
How do people currently use RANDOM NUMBERS? Simulations? Anything else? How do you generate them? Do you think your results would benefit from using truly random numbers rather than pseudo-random stuff? Is it of enough interest to justify some time and effort? I must say that I don't really understand how people actually use random numbers, and if people really care how random they are. Is it technically not an important issue, that people just don't think about it, or that getting really random numbers to the application is just too difficult? Mike Rutenberg -- Reed College -- Portland, Oregon -- 503/774-9192
simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) (03/18/87)
In article <5712@reed.UUCP> mdr@reed.UUCP (Mike Rutenberg) writes: >How do people currently use RANDOM NUMBERS? Simulations? Anything else? A few years ago I was doing research in PSI (no joke) and needed a truely random source of numbers. Not wanting to get involved with radioactive decay (and for other reasons wanting to use electronic circuits) I built an electronic random number generator which was then attached to a single bit of a digital input port on an IBM-PC. The random number generator consisted of a variable-duration pulse generator. When the pulse was long (past a certain point), a comparator output a "1" which was fed to the I/O port and fed back to the pulse generator to shorten the duration of the pulse. Likewise, when the output was a "0" the duration of the pulse was lengthened. Extensive FFT analysis of the output of the generator showed it to have roughly uniform frequency distriubtuion with the exception of a high energy point around 100KHZ. As the sampling rate was under 10HZ, this did not present a major problem. Incidently, I didn't discover any PSI effects. Simson L. Garfinkel -- --- Overheard in a terminal room: "What an interesting pattern that is on your shirt. May I trace it with my finger?"i
martin@entropy.ms.washington.edu (Don Martin) (03/19/87)
In article <5712@reed.UUCP>, mdr@reed.UUCP (Mike Rutenberg) writes: > How do people currently use RANDOM NUMBERS? Simulations? Anything else? > > How do you generate them? > > Do you think your results would benefit from using > truly random numbers rather than pseudo-random stuff? For most applications real random numbers are undesirable. Consider debugging a monte-carlo or simulation program when you cannot repeat the sequence that led to the problem. Also, the better psuedo random number generators are quite good for most applications. Thus there is little motivation to come up with hardware to substitute for a short simple and reasonably fast program. ( the time spent computing random numbers is usually only a small fraction of the program time. Thus speeding up random number generation does not usually result in much overall improvement. ) It is very hard to get a really good hardware random number generator. Very small effects can signifcantly bias the results. I tried breadboarding a fast counter and using the time that I held down a switch to get a random number and found that even this was biassed. Try reading the intro to 1000000 Random Digits ( one of the few fictional works published by RAND Corp ;-) . This will give you an idea of of the problems. > Is it of enough interest to justify some time and effort? My guess is prbably not. There have been one or two attempts to do this and sell one time pad systems. Don Martin martin@entropy
phm@stl.UUCP (03/19/87)
In article <5712@reed.UUCP> mdr@reed.UUCP (Mike Rutenberg) writes: >How do people currently use RANDOM NUMBERS? Simulations? Anything else? > >How do you generate them? > >Do you think your results would benefit from using >truly random numbers rather than pseudo-random stuff? >Is it of enough interest to justify some time and effort? > I remember that back in the early '50s, there were machines that had an instruction_code which would give you a random number in the accumulator, derived from the electronic noise in the valves. (Not tubes - they were British :-) ! ) As I recall, it wasn't very popular, because the only way to get predictable values for debugging was to put in a patch to a routine to avoid it, and we didn't have such new-fangled things as assembler languages in those days. -- Regards, Peter Mabey (phm@stl ...!mcvax!ukc!stl!phm +44-279-29531 x3596)
mdr@reed.UUCP (Mike Rutenberg) (03/19/87)
"For most applications real random numbers are undesirable. Consider
debugging a monte-carlo or simulation program when you cannot repeat
the sequence that led to the problem." [Don Martin]
I agree that tracking a specific bug in a Monte-Carlo simulation is
easier with a repeatable sequence, but what about running the thing for
real. Especially for long running simulations, I'm not sure how much I
trust psudeo-random generator libraries, especially if I have a pretty
good sense of just how random my hardware is.
I find it a little curious that people are trying to simulate particles
and other widgets using predictable perturbations (i.e. psudeo-random
numbers) - it feels like playing with fire unless you really understand
exactly how the simulation might be effected by the flavor of random numbers
you're using -- AND THAT'S EXACTLY WHY YOU ARE DOING THE SIMULATION.
Am I confused?
Mike
ps. From all I can tell, hardware random numbers are quite a bit slower
to generate than psuedo-random numbers, but then there are hybrid schemes.
--
Reed College -- Portland, Oregon -- 503/774-9192dew@esl.UUCP (Douglas Wood) (03/20/87)
In article <5712@reed.UUCP> mdr@reed.UUCP (Mike Rutenberg) writes: >How do people currently use RANDOM NUMBERS? Simulations? Anything else? In experimental high energy physics, random numbers are used for two main uses: 1) simulating detector noise, Landau fluctuations in gas, photon statistics in phototubes, etc. 2) Physics of collisions are described as probabilities rather than certainty as to what happens when. In the first example, the Monte Carlo (models based on random numbers) must simulate the detector in the situation of the physics measurements. In the second example, the Physics must be generated with the frequency of occurrence expected in nature to see if an effect is observable against normal background events. >How do you generate them? There are many methods. Knuth's books have good methods. >Do you think your results would benefit from using >truly random numbers rather than pseudo-random stuff? Truly random numbers can not be generated by a machine. However, a bad random number generator can bias the results of a calculation. So, one must pay attention to one's random number generator. Correlation coefficients are one of the tests of random numbers. There are others. Hope this helps. dew@esl.uucp
outer@utcsri.UUCP (Richard Outerbridge) (03/20/87)
> How do you generate them? > For DES keys I use a set of "Dungeons and Dragons" dice and a backgammon cup. Two eight-sided dice, one four-sided die, and a parity adjustment table to get the least significant bit right. Master keys and such are rarely if ever changed, and the more random they are to begin with the better. For session keys I use a function based on the clock drift between two asynchronous processors by having the slave spin a seed while idle. Then the seed gets encrypted using another time-varying number as a key. -- Richard Outerbridge <outer@utcsri.UUCP> (416) 961-4757 Payload Deliveries: N 43 39'36", W 79 23'42", Elev. 106.47m.
hrubin@osupyr.UUCP (03/21/87)
There are purposes for which pseudo-random numbers are acceptable; In these cases quasi-random numbers are even better. However, no inexpensive pseudo-random generator has any good independence properties. What I do is to use a physically generated set exclusive or-ed with a reasonably good pseudo-random process, and the physical random numbers are stored on disk or similar device. It is rare that I would trust the results of a calculation using only pseudo-random numbers. -- Herman Rubin Until mid May: Department of Statistics, Cockins Hall, 1958 Neil Avenue Ohio State University, Columbus OH43210 hrubin@osupyr or cbosgd!osu-eddie!osupyr!hrubin or ts0474@ohstvma.bitnet "Permanent": Department of Statistics, Purdue University, West Lafayette IN47907 hrubin@l.cc.purdue.edu or ihnp4!pur-ee!stat-l!hrubin or hrubin@purccvm.bitnet
braner@batcomputer.UUCP (03/21/87)
[] In some simulations I do I need _MANY_ random numbers (say 1E8 numbers...), and calculating them _IS_ a major portion of the program run time (especially if I need nonuniform numbers, e.g. lognormal). I worry mostly about them being autocorrelated, a common flaw in simple-minded generators. I currently use home-made assembly-language routines (for the 68000 chip). My basic uniform generator yields a 32-bit random integer in about 36 microsec (_including_ the overhead of calling from a high-level language and returning the value into a variable in that language). Other AL routines return floating-point results that are either uniform (60 usec), approximately normal, exponential, or lognormal (about 100-200 usec for these). (All timings with an 8 Mhz CPU.) My generator has limited resolution (32 bits), hence not very good in the extreme tails. And the transcendental functions are implemented using look-up tables, for speed rather than accuracy. But the basic generator passed all the uniformity and autocorrelation tests I could devise. I recommend using integer rather than FP randoms in simulations whenever possible, for speed. E.g., to simulate an event that happens with prob p (a constant), calculate "intp = (integer) (K*p)" _outside_ the loop, and use "if random() < intp then do it" inside the loop. (K is 2^32, or whatever fits your _integer_ random() generator.) (Those of you for whom all this is boring, obvious, old-hat stuff, please forgive me...) - Moshe Braner
piner@pur-phy.UUCP (03/21/87)
Just a point of information. It is possible to get a real random number from a computer. On Z-80 machines (like the TRS-80) it is possible to read the memory refresh register. The register can have any value between 0 and 64k. The "RANDOMIZE" function in BASIC uses this register to start a psuedo-random number sequence. Since the time you select to look at the register is random, the number read is random. It is important to note that the randomness here is dependent on when the human hits the key to start the program. If you write a program to read the register in a loop, you will get a periodic series. Richard Piner piner@pur-phy.UUCP
peter@entropy.UUCP (03/21/87)
In article <2156@pur-phy.UUCP>, piner@pur-phy.UUCP writes: > Just a point of information. It is possible to get a real random > number from a computer. On Z-80 machines (like the TRS-80) it is > possible to read the memory refresh register. The register can > have any value between 0 and 64k. The "RANDOMIZE" function in > BASIC uses this register to start a psuedo-random number sequence. > Since the time you select to look at the register is random, > the number read is random. In order to get useful random numbers they have to be independent (in the sense of probability theory) and uniformly distributed. The fact that the register can take on any value between 0 and 64k, and you don't know which, doesn't make it a random number, just an unpredictable one. In statistical applications random numbers are used to evaluate (using Monte Carlo methods) procedures that are not amenable to mathematical analysis. There it is important to produce random numbers that have prescribed properties, i.e. that can pass tests of uniformity and independence.
srt@duke.UUCP (03/21/87)
In article <2156@pur-phy.UUCP> piner@pur-phy.UUCP (Richard Piner) writes: >Just a point of information. It is possible to get a real random >number from a computer. On Z-80 machines (like the TRS-80) it is >possible to read the memory refresh register. The register can >have any value between 0 and 64k. The "RANDOMIZE" function in >BASIC uses this register to start a psuedo-random number sequence. First let me say that I haven't worked on a Z-80 in a while, but back when I was using them extensively in hardware work, the refresh register was only 7 bits long. Why 7? Well, that's all they needed for the "new-fangled" (at the time) 16k dynamic RAM chips. Anyway, I have heard that they extended it to 8 bits for 64k RAMs, but I doubt that it's the 16 bits that you imply. You must be very careful with small range random seeds. I remember reading a tech. report at Bell Labs about the different attempts they made at a crypt function. One of the first attempts (the first maybe, I don't remember) used a 16 bit random seed to shake up the crypt function a bit. They used some function to extend this to more precision (32 bits maybe?) because they figured that trying all 32 bit keys would be computationally infeasable. The method of attack seems obvious now, but didn't surface until Dennis Ritchie broke the crypt function by simply trying the 64k possible initial seeds. So even though they used 32 bits to shake up the crypt function, there were only 64k possible ways to do it. Sorry that last paragraph sounds a bit sketchy, but my memory is fading fast, and as I think the paper was marked "proprietary" it was left behind when I left Bell Labs. Anyway, the warning is clear: A 16 bit random seed only produces 64k possible random sequences out of 64k! possible sequences. This is clearly not very random, and should not be used as the basis for any cryptographic system that is supposed to be "secure." -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt@cs.duke.edu "There ain't nothin' in the world that a T-Bone Shuffle won't cure."
emh@wayback.UUCP (03/22/87)
In article <5722@reed.UUCP> mdr@reed.UUCP (Mike Rutenberg) writes: > "For most applications real random numbers are undesirable. Consider > debugging a monte-carlo or simulation program when you cannot repeat > the sequence that led to the problem." [Don Martin] If a Monte Carlo simulation program is being tested, or is new enough that there is a resonable probability of bug-problems, then the sequence of random numbers can be stored on a peripheral. In this way, problems are reproducable and "true" random numbers can be used. >I agree that tracking a specific bug in a Monte-Carlo simulation is >easier with a repeatable sequence, but what about running the thing for >real. Especially for long running simulations, I'm not sure how much I >trust psudeo-random generator libraries, especially if I have a pretty >good sense of just how random my hardware is. >I find it a little curious that people are trying to simulate particles >and other widgets using predictable perturbations (i.e. psudeo-random >numbers) - it feels like playing with fire unless you really understand >exactly how the simulation might be effected by the flavor of random numbers >you're using -- AND THAT'S EXACTLY WHY YOU ARE DOING THE SIMULATION. >Am I confused? It depends on what is being modeled and how precise the model needs to be specified. Usually, the model used is approximate and the level of approximation is known to make effects of correlations in the pseudorandom number generator insignificant. For Monte Carlo experiments that study very subtle effects, the difference between pseudo-randon, quasi-random and random can become significant. For these experiments, the accuracy and precision of the models used must be very high. -- Ed Hummel AT&T Bell Laboratories ihnp4!wayback!emh
karn@faline.UUCP (03/24/87)
"Anyone who uses deterministic computer techniques to generate random numbers is, of course, living in a state of sin" -John von Neumann (quoted from memory) > For DES keys I use a set of "Dungeons and Dragons" dice and a backgammon > cup.... Not being into D&D, I use a pair of ordinary 6-sided dice. Roll one die from each hand, being careful to keep them separate. If a die comes up 5 or 6, roll it again. Now you will have a pair of numbers ranging from 1 to 4 which I will call L and H. Compute (L-1)*4 + (R-1). The result is a single 4-bit number evenly distributed between 0 and 15. Repeat 16 times and you'll have your DES key. With a little practice this becomes pretty quick. Speaking of DES, I have taken the public-domain DES posted to net.sources a while back and worked on it a bit. It now runs a lot faster, thanks to operations on longs instead of 8-bit-bytes. (It is, nevertheless, still portable as long as you set the LITTLE_ENDIAN flag appropriately before compiling). You first call an initialization function; this takes an argument saying whether you want standard DES (slow) or DES without the initial and final permutations (faster and just as secure, but incompatible with hardware chips). This function allocates space for and precomputes a number of internal tables for things like combined S and P boxes. When done, you call another function to free the internal table space. I have written a few applications around it, including "descert", which takes the NBS test data posted a while back and verifies the DES function; "des", an encrypt/decrypt filter functionally compatible with the Sun Micro command of the same name; "descalc", a simple program for interactively encrypting and decrypting single blocks of hex data; "radlogin", an experimental DES-authenticated UNIX login program for amateur packet radio. The whole bunch works fine on the PC as well as under UNIX on both big-endian and little-endian machines. I'll post the combination to the net as soon as I figure out what newsgroup I'm supposed to use. Phil
karn@faline.UUCP (03/26/87)
My own feeling is that if you MUST use a deterministic algorithm to generate random numbers, then use the Data Encryption Standard. Pick a random number for use as a key (use a pair of dice as I previously described) and encrypt an incrementing 64-bit integer. From everything I've read, most of the existing "simple" methods for generating random numbers have some horrible properties. The excellent book Numerical Recipies also recommends DES as a random number generator, and gives listings in Fortran and Pascal. The main problem, of course, is that software DES is slow but with hardware chips this problem goes away. The Sun-3 Workstation has space for an AMD 9518 chip, although it doesn't seem to come as standard equipment. On the other hand, even software DES may not be that bad, depending on how many random numbers you need and what else you have to do with each one once you get it. A stock PC/AT running my DES (soon to appear on net.sources) can do about 5400 encryptions (each yielding 64 random bits) per minute. Phil
braner@batcomputer.UUCP (03/27/87)
[] The book "numerical recipes" includes code for both DES and some other, much simpler but not naive, random number generators. They specifically recommend _not_ to use DES for the generation of random numbers, if you need a lot of them in a hurry. (When I need them, I need many millions!) Of course, if you have DES _hardware_... I wrote a speeded-up version of the 'ran2' routine in that book, in C. (And also some much faster routines in 68000 AL.) - Moshe Braner PS: I looked for the book by Kennedy and Gentle but didn't find it. Could somebody post the "modified shift register" method from it?
karn@faline.UUCP (03/29/87)
I never said DES made a FAST random number generator, only that it made a "good" one (in its statistical properties). I thought I said that. Another word of warning: quite a few companies sell "encryption" programs for the IBM PC that are much faster than software DES. Note my use of quotes; they are TERRIBLE both as encryption packages and as random number generators. For example, "lock/unlock" by SoftLogic Solutions (the guys who brought DoubleDos to the world) encrypts a file containing binary zeros to the pattern FBFFFBFFFBFFFB... with the key I used. Pretty bad. Phil
mdr@reed.UUCP (04/02/87)
In my original posting I asked: >How do people currently use RANDOM NUMBERS? Simulations? Anything else? >How do you generate them? I've been getting lots of notes from people asking why I don't know about Knuth's Seminumerical Algorithms. Thank you for those notes, and I do have the book. My intention was to ask How do **you** generate the random numbers that *you* use? Answers I expected and got were similar to: "I use RANDU" or "I use D&D dice" or "I use the spatial distribution of tea leaves in an empty cup XORed with activity counts from decaying cobalt" Mike ps. Shame on you all - How could you possibly misinterpret my ambiguous language?? -- Reed College -- Portland, Oregon -- 503/774-9192
martin@entropy.UUCP (04/06/87)
In article <444@faline.UUCP>, karn@faline.UUCP writes: > My own feeling is that if you MUST use a deterministic algorithm to > generate random numbers, then use the Data Encryption Standard. Pick a > random number for use as a key (use a pair of dice as I previously > described) and encrypt an incrementing 64-bit integer. From everything > I've read, most of the existing "simple" methods for generating random > numbers have some horrible properties. > > The excellent book Numerical Recipies also recommends DES as a random > number generator, and gives listings in Fortran and Pascal. The main > problem, of course, is that software DES is slow but ......... This is an understatement. DES algorithms are VERY slow. The Num. Recipies is a prime example. I expect that Phil has speeded it up to the point where it might be marginally usable but that does not mean that it is a good choice. I don't think that DES has been tested very well as a random number generator. Nor did Num. Recipies recomend it as a uniform random number generator, it was proposed as a method of generating binary sequences. I will agree that the distinction between binary sequences and random binanary numbers is thin. For most applications, I would recomend the shuffle algorithm in Numerical Recipies rather than DES. If I wanted to check my application with another generator I would add a shift regester ( modulo add or XOR ) to the shuffle. Don Martin martin@entropy
karn@faline.UUCP (04/09/87)
> This is an understatement. DES algorithms are VERY slow. The Num. > Recipies is a prime example. I expect that Phil has speeded it up > to the point where it might be marginally usable but that > does not mean that it is a good choice. I don't think that DES > has been tested very well as a random number generator.... The Numerical Recipes DES is very slow mainly because it was written in Fortran, a language with virtually no bit-twiddling facilities. My DES (in the pipeline for mod.sources) can do 5400 encryptions/minute on the PC/AT, and about 70,000/minute on the VAX-8650. Not blazingly fast, but not bad either considering the results ARE statistically random. As they say in the book, the fact that DES has withstood all known attacks except perhaps those of the NSA implies that DES is a very good random number generator. Statistical testing of ciphertext is one of the most fundamental cryptoanalytic tools. Phil