roy@phri.UUCP (Roy Smith) (11/11/86)
In article <267@bath63.UUCP> ma_jpb@bath63.UUCP (Bennett) writes: > I recall that when I was an undergraduate being taught a novel rounding > scheme for floating point, attributed I believe to David Wheeler of > Cambridge University. [...] The mechanism was to add a random number in > the range 0 to 1 in the last digit and then truncate. Which brings up a point which has been bothering me for a long time. Why don't computers come with hardware random number generators? It doesn't seem like it would be too hard (i.e. expensive) to build a bank of 32 white noise generators hooked up to zero-crossing detectors. Make the digital outputs a hardware register you could access, and *presto*, instant U(0,2^32), and fast too. On my Sun-3/50, I get about 26 user cpu seconds for 1,000,000 calls to random(III), vs. about 4 user cpu seconds for that many calls to "long Random () {return (1);}". That makes about 22 uSec per random integer. With white noise generators you should be able to do it a lot faster, and get more random numbers to boot. BTW, on a Vax-11/750, I get 61 and 30 seconds, for about 31 uSec per random integer, with a much greater subroutine call overhead. Of course, you have to make sure the register changes faster than you can read it to prevent the numbers from being badly correlated, but that doesn't seem too difficult. If an instruction time is O(100 nSec), the tightest loop that reads a register should be O(5 MHz). All you need is a 50 MHz bandwidth noise source and comparator for each bit, which doesn't seem too hard. Don't even have to bother latching the outputs -- who cares if they change while you're reading them? Oh yes, don't forget to put a conventional software rand() routine in the library too -- handy for testing programs with a reproducible string of "random" numbers. -- Roy Smith, {allegra,cmcl2,philabs}!phri!roy System Administrator, Public Health Research Institute 455 First Avenue, New York, NY 10016 "you can't spell unix without deoxyribonucleic!"
roy@phri.UUCP (Roy Smith) (11/14/86)
In article <2490@phri.UUCP> I wrote: > Why don't computers come with hardware random number generators? [...] > On my Sun-3/50 [it takes] about 22 uSec per random integer. With white > noise generators you should be able to do it a lot faster, and get more > random numbers to boot. Let me rephrase that a bit. As Edward Wang <ucbvax!edward> rightfully pointed out, 22 uSec to get a random integer is not anything you should be sweating about. For most applications, the time to pick random numbers compared to whatever processing you do with those numbers is pretty trivial. The real reason I want a random number register based on a white noise generator is to get more random random numbers. If the reader was left with the impression that I was mostly concerned about speed, I apologise. The misunderstanding is entirely the fault of my sloppy writing. If you need a system call to access this register, you're sure to lose in the speed department anyway, and lose big. But do you really need a system call? Why not a "read processor register" instruction that's executable in user mode and lets you read the value of the random register, time of day clock, CPU type and serial number, etc. My diversion into the timing of random(III) was only to show that there isn't any reason why a read of the random register need be as fast as a typical CPU register read would be. If a typical instruction time on your machine was, say 100nS, it wouldn't make much difference if reading the random register took 1uS, or even 10 uS, would it? Starting a 10 uSec timer each time you read the register and blocking subsequent reads until the timer expired would be simple, and even if you did as few as 100 instructions between random reads, you would never block. So, with my point hopefully made clear this time, I re-ask the question. Is there any merit to this, or is it off-the-wall? Would the cost of adding the random hardware be justified by the use it would get? -- Roy Smith, {allegra,cmcl2,philabs}!phri!roy System Administrator, Public Health Research Institute 455 First Avenue, New York, NY 10016 "you can't spell deoxyribonucleic without unix!"
henry@utzoo.UUCP (Henry Spencer) (11/15/86)
> Which brings up a point which has been bothering me for a long > time. Why don't computers come with hardware random number generators? > It doesn't seem like it would be too hard (i.e. expensive) to build a bank > of 32 white noise generators hooked up to zero-crossing detectors... My understanding is that the problem is avoiding bias in the resulting numbers. Building a noise generator isn't hard, but one would like the probability of a 0 to be roughly equal to the probability of a 1. Getting this sort of balance, and *keeping* it, apparently is almost impossible without constant tweaking. It's viable for specialized applications like generating encryption keys, but too much hassle to be built into every computer. I wonder, though, if it would be feasible to automate the de-biasing? Each bit would have a counter, incremented on 1 and decremented on 0. (This assumes that the bits change synchronously, or can be induced to do so for counting purposes at least.) Every 15 minutes, say, a daemon would wake up and inspect the counters; those that were significantly different from zero would indicate bias developing in those bits. The daemon could then adjust the noise generators via DACs. Counter overflow wouldn't be an issue provided it was remembered. The daemon could do arbitrarily sophisticated filtering to track things like component drift. -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,decvax,pyramid}!utzoo!henry
perry@vu-vlsi.UUCP (Rick Perry) (11/15/86)
I think the idea of hardware random number generators is an excellent one. It's all too easy for the average joe (who didn't do his doctoral thesis on super-duper pseudo-random number generation) to implement or use exisiting pseudo-random number generators that are not very good. Other problems with the pseudo methods (like the common linear congruential method) is that the least significant bits might not be very random, certain operations on the generated numbers (like using MOD's) might destroy the randomness, and successive samples may be highly correlated. It would be great to have an easy to use, dependable, fast hardware generator of really random numbers.
nather@ut-sally.UUCP (Ed Nather) (11/16/86)
In article <7320@utzoo.UUCP>, henry@utzoo.UUCP (Henry Spencer) writes: > > Which brings up a point which has been bothering me for a long > > time. Why don't computers come with hardware random number generators? > > It doesn't seem like it would be too hard (i.e. expensive) to build a bank > > of 32 white noise generators hooked up to zero-crossing detectors... > > My understanding is that the problem is avoiding bias in the resulting > numbers. Building a noise generator isn't hard, but one would like the > probability of a 0 to be roughly equal to the probability of a 1. Getting > this sort of balance, and *keeping* it, apparently is almost impossible > without constant tweaking. It's viable for specialized applications like > generating encryption keys, but too much hassle to be built into every > computer. > There are several different ways to build a "hardware random number generator" mostly based on the detection of radiactive decay, which is a completely random process. When I proposed such a scheme to Computer Scientist who wanted a fast one, he replied "Oh, I don't want anything THAT random!" What he was trying to explain was that he would be unable, with such a device, to reproduce the same set of numbers again and again, which he would need to debug the program calling for the random number. And indeed, by definition, you wouldn't get the same set of numbers twice -- if you did, the generator would be broken! -- Ed Nather Astronomy Dept, U of Texas @ Austin {allegra,ihnp4}!{noao,ut-sally}!utastro!nather nather@astro.AS.UTEXAS.EDU
radford@calgary.UUCP (11/18/86)
In article <7320@utzoo.UUCP>, henry@utzoo.UUCP (Henry Spencer) writes: > > ... Why don't computers come with hardware random number generators? > My understanding is that the problem is avoiding bias in the resulting > numbers. Building a noise generator isn't hard, but one would like the > probability of a 0 to be roughly equal to the probability of a 1. Getting > this sort of balance, and *keeping* it, apparently is almost impossible > without constant tweaking... How about taking the exclusive-or of several such random bit generators? This converges exponentially toward probability 1/2 as the number of bits xor'ed increases. Radford Neal The University of Calgary
rbl@nitrex.UUCP ( Dr. Robin Lake ) (11/19/86)
In: >From: nather@ut-sally.UUCP (Ed Nather) >Subject: Re: random number generator in hardware >Message-ID: <6364@ut-sally.UUCP> >References: <317@zuring.mcvax.UUCP> <267@bath63.UUCP>, <2490@phri.UUCP> <7320@utzoo.UUCP> it is mentioned that: >In article <7320@utzoo.UUCP>, henry@utzoo.UUCP (Henry Spencer) writes: > > Which brings up a point which has been bothering me for a long > > time. Why don't computers come with hardware random number generators? > > It doesn't seem like it would be too hard (i.e. expensive) to build a bank > > of 32 white noise generators hooked up to zero-crossing detectors... >There are several different ways to build a "hardware random number generator" >mostly based on the detection of radiactive decay, ... Just such a random number generator was built as a Master's thesis project in the Engineering Design Center at Case Western Reserve University (then Case Institute of Technology) in 1960 -1961. I've forgotten the grad student's name, but I believe the advisor was Dr. Harry Mergler, who is still around CWRU. Robin Lake Standard Oil R&D
henry@utzoo.UUCP (Henry Spencer) (11/21/86)
> > My understanding is that the problem is avoiding bias in the resulting > > numbers... > > How about taking the exclusive-or of several such random bit generators? > This converges exponentially toward probability 1/2 as the number of > bits xor'ed increases. Only if the generators drift independently, which in general they won't: things like temperature and aging effects will be similar for all. -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,decvax,pyramid}!utzoo!henry
lambert@mcvax.uucp (Lambert Meertens) (11/24/86)
>>> My understanding is that the problem is avoiding bias in the resulting >>> numbers... >> >> How about taking the exclusive-or of several such random bit generators? >> This converges exponentially toward probability 1/2 as the number of >> bits xor'ed increases. > > Only if the generators drift independently, which in general they won't: > things like temperature and aging effects will be similar for all. By xor'ing cumulatively a single random bit generator another random bit generator is obtained with guaranteed probability 1/2. There may still be a serial correlation because of bias in the original one, but unless it was far of the mark, that drops off fast over larger time spans. Now, xor'ing several of these "cumulative" generators makes the serial-correlation effect drop exponentially with the # of generators involved. It does not matter if the original set drifts together. A technique that has mentioned on the net before to turn a random bit generator with bias but whose bits are independent into another one with independent bits without bias is to group the output in twos, discard 00's and 11's, and turn 10's and 01's into 0's and 1's, respectively: 111101100100001101010101111010101001110110000100000000010100 = =\|\|\| = = =\|\|\|\| =\|\|\|\|\| =\|\| =\| = = = =\|\| = 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 This is good only if the consuming process can afford to wait for the next output bit. The random device can start to compute its next output immediately after it has been polled, and with some engineering tricks you can make sure that there is always an output bit ready with epsilon probability that it was not theoretically fully random. -- Lambert Meertens, CWI, Amsterdam; lambert@mcvax.UUCP
dupuy@amsterdam.columbia.edu (Alexander Dupuy) (11/24/86)
henry@utzoo.UUCP (Henry Spencer) replies to an earlier post: > > > How about taking the exclusive-or of several such random bit generators? > > This converges exponentially toward probability 1/2 as the number of > > bits xor'ed increases. > >Only if the generators drift independently, which in general they won't: >things like temperature and aging effects will be similar for all. Actually, the xor scheme works best if the generators all drift in the same direction. Taking four generators which have drifted to 75% ones and 25% zeros, and hooking them up in a two-level xor tree gives you the following probability table: f(a,b,c,d) = (a^b)^(c^d) a b c d (a^b)^(c^d) Prob (256ths) ---------- ----------- ------------- 1 1 1 1 0 81 1 1 1 0 1 27 1 1 0 1 1 27 1 1 0 0 0 9 1 0 1 1 1 27 1 0 1 0 0 9 1 0 0 1 0 9 1 0 0 0 1 3 0 1 1 1 1 27 0 1 1 0 0 9 0 1 0 1 0 9 0 1 0 0 1 3 0 0 1 1 0 9 0 0 1 0 1 3 0 0 0 1 1 3 0 0 0 0 0 1 ----------- 136 120 53% 47% 3% drift is not bad considering the generators are each 25% off. This works well for odd as well as even numbers of generators. This setup is vulnerable to drift if generator pairs drift in _opposite_ directions, but with careful design, the factors you mention will tend to prevent this. @alex ---- arpa: dupuy@columbia.edu uucp: ...!seismo!columbia!dupuy
radford@calgary.UUCP (Radford Neal) (11/25/86)
In article <3915@columbia.UUCP>, dupuy@amsterdam.columbia.edu (Alexander Dupuy) writes: > > ME: > > > How about taking the exclusive-or of several such random bit generators? > > > This converges exponentially toward probability 1/2 as the number of > > > bits xor'ed increases. > > > >Henry Spencer: > >Only if the generators drift independently, which in general they won't: > >things like temperature and aging effects will be similar for all. > > Actually, the xor scheme works best if the generators all drift in the same > direction. Taking four generators which have drifted to 75% ones and 25% > zeros... > > [ 47% vs. 53% results] > > 3% drift is not bad considering the generators are each 25% off. > This works well for odd as well as even numbers of generators. This > setup is vulnerable to drift if generator pairs drift in _opposite_ > directions, but with careful design, the factors you mention will tend > to prevent this. Your results are in agreement with the general formula, which I think is p(zero) = ( 1 + (2z-1)^N ) / 2 where z is the original, drifted, zero probability (assumed the same for all generators), and N is the number of bits XOR'ed. To prove this: 1 = 1^N = (z + (1-z)) ^ N = sum over i [ C(N,i) (1-z)^i z^(N-i) ] (z - (1-z)) ^ N = sum over i [ C(N,i) (1-z)^i z^(N-i) (-1)^i ] subtracting these two expansions: 1 - (z - (1-z)) ^ N = 2 * sum over odd i [ C(N,i) (1-z)^i z^(N-i) ] but the right side is simply the sum of those terms of the binomial probability distribution which will result in the XOR being one (odd number of one's). So the probability of the result being one is: p(one) = ( 1 - (2z-1)^N ) / 2 and the probability of zero is thus: p(zero) = ( 1 + (2z-1)^N ) / 2 If the generators don't all drift in the same way, things may be more complicated, but I don't think the results are neccessarily bad. Consider the XOR of two generators, one of which has zero probability 0.4 and the other of which has zero probability 0.7: p(zero) = 0.4*0.7 + 0.7*0.4 = 0.56 which is closer to 0.5 than either of the inputs. Radford Neal The University of Calgary
leichter@yale.UUCP (Jerry Leichter) (12/01/86)
Josh Benaloh (decvax!yale!benaloh, or benaloh@Yale) has a tech report on the subject of combining "poor" random number generators to make better ones. (He calls the process "coin fairing".) It turns out that XOR isn't always the best approach (where you measure "fairness" of the resulting coin with the number of tosses of the unfair coin you had to take). Simple way to see the general model: Suppose you decide to toss your poor coin 10 times. This gives you 10 bits, in one of 1024 combinations. List them in numeric order (as binary numbers) along a line, and plot the proba- bility of each combination, given the unfairness of the coin, above its value. Now, what you want to do is divide the area under your curve into two regions, one that you will consider a total toss of 0, another that you will consider a total toss of 1. You want the areas of the two regions to be as close as possible. XOR'ing simply uses the parity of the 10 bits to divide the regions. Majority vote uses the total number of bits (you have to decide on some rule to deal with 5 of each). There are many other possibilities; most, of course, require too much computation, relative to any possible improvement, to be of much value. I stated the example using 10 tosses of the same biased coin, but of course I could as well have used 10 coins, or 5 coins each tossed twice, and so on. In general, you can do quite well IF the various "poor" random numbers you start with are not correlated with each other. Getting rid of correlations is very difficult; if you don't know the correlations, it may not be possible. There's some general theoretical work on this, in a model that's probably not too useful for building hardware, but Vijay and Umesh Vazirani. (Sorry, I don't have a reference - try the last couple of STOC and FOCS conferences.) -- Jerry
campbelr@hpisof0.HP (Bob Campbell) (12/19/86)
/ hpisof0:comp.arch / dupuy@amsterdam.columbia.edu (Alexander Dupuy) / 10:33 am Nov 24, 1986 / henry@utzoo.UUCP (Henry Spencer) replies to an earlier post: > > > How about taking the exclusive-or of several such random bit generators? > > This converges exponentially toward probability 1/2 as the number of > > bits xor'ed increases. > >Only if the generators drift independently, which in general they won't: >things like temperature and aging effects will be similar for all. Actually, the xor scheme works best if the generators all drift in the same direction. Taking four generators which have drifted to 75% ones and 25% zeros, and hooking them up in a two-level xor tree gives you the following probability table: f(a,b,c,d) = (a^b)^(c^d) a b c d (a^b)^(c^d) Prob (256ths) ---------- ----------- ------------- 1 1 1 1 0 81 1 1 1 0 1 27 1 1 0 1 1 27 1 1 0 0 0 9 1 0 1 1 1 27 1 0 1 0 0 9 1 0 0 1 0 9 1 0 0 0 1 3 0 1 1 1 1 27 0 1 1 0 0 9 0 1 0 1 0 9 0 1 0 0 1 3 0 0 1 1 0 9 0 0 1 0 1 3 0 0 0 1 1 3 0 0 0 0 0 1 ----------- 136 120 53% 47% 3% drift is not bad considering the generators are each 25% off. This works well for odd as well as even numbers of generators. This setup is vulnerable to drift if generator pairs drift in _opposite_ directions, but with careful design, the factors you mention will tend to prevent this. @alex ---- arpa: dupuy@columbia.edu uucp: ...!seismo!columbia!dupuy ----------
cik@l.cc.purdue.edu (Herman Rubin) (12/21/86)
If the streams are independent, the difference between the probability of 0 and the probability of 1 is the product of the differences in the various streams. -- (Usual disclaimer line.) Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 (decvax,ihnp4,uiucdcs)!pur-ee!stat-l!cik (decwrl,hplabs,ucbvax)!purdue!stat-l!cik hrubin@l.cc.purdue.edu