Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!cmcl2!phri!roy
From: roy@phri.UUCP (Roy Smith)
Newsgroups: comp.arch
Subject: random number generator in hardware
Message-ID: <2490@phri.UUCP>
Date: Tue, 11-Nov-86 14:23:26 EST
Article-I.D.: phri.2490
Posted: Tue Nov 11 14:23:26 1986
Date-Received: Wed, 12-Nov-86 10:06:03 EST
References: <317@zuring.mcvax.UUCP> <267@bath63.UUCP>
Reply-To: roy@phri.UUCP (Roy Smith)
Organization: Public Health Research Inst. (NY, NY)
Lines: 38
Original-Subject: Re: Floating point accuracy


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!"