Path: news.io.com!uunet!in1.uu.net!salliemae!newsfeed.internetmci.com!news.
+ mathworks.com!news.kei.com!world!blanket.mitre.org!linus.mitre.org!
+ spectre!eachus
From: eachus@spectre.mitre.org (Robert I. Eachus)
Newsgroups: comp.arch.arithmetic
Subject: Re: Psuedo Random Numbers
Date: 06 Oct 1995 21:30:47 GMT
Organization: The Mitre Corp., Bedford, MA.
Lines: 75
Message-ID:
References: <44vm6r$1q5@bug.rahul.net>
NNTP-Posting-Host: spectre.mitre.org
In-reply-to: Matthew Carlson's message of 5 Oct 1995 04:16:27 GMT
In article <44vm6r$1q5@bug.rahul.net> Matthew Carlson writes
:
> Thanks for all the responses I got with my last question. I have received
> a number of 32 bit random number generators. I am wondering which one is
> the best of those currently available.
My Blum, Blum and Shub based generator of course, but don't take my
word for it, read the original Blum, Blum and Shub paper. :-) (The
Blum, Blum and Shub algorithm is at least as difficult to predict as
it is to factor the modulus. RSA has not been proven to be quite that
difficult, but I also don't think anyone has based an RNG on it.) The
paper is:
A Simple Unpredictable Pseudo-Random Number Generator, by L. Blum, M.
Blum, and M. Shub, SIAM Journal of Computing, Vol 15, No. 2, May 1986.
(Don't believe that the simple applies to the paper, it is very dense
and hard to work through, but worth it.)
Also, it is not clear whether you want an integer generator or a
floating point generator. The ADAR components contain both. They have
a period of 562,085,314,430,582 (the product of 26 bit and 27 bit
special primes). The floating generator can produce all representable
values between 0.5 and 1.0 on most floating point implementations.
(Yes, it produces exactly as many values less than 0.5, but the nature
of floating point is such that there are a lot more representable
values in that range.) The integer generator is based on the same
generator, but maps to a (presumably 32-bit) integer type.
> I also wanted something with more bits, say 64 bits or more. I
> noticed a 48 bit random number generator on SunOs, it is called
> rand48.
I won't call the SunOS generator junk. It is better than that, but
at the execution time overhead cost you should be getting something
much better. The best way to use it is to generate starting seeds for
your own generator.
> Another thing I was wondering is how to convert a 32 bit number
> generator to more bits using the same constant multipliers in the
> alogithm. For instance a Linear Congruential generator has
> constant multipliers A and C. If I up the bits from 32 to 64 do
> these have to be changed? If so will multipling them by the
> largest 32 bit number (4.2 billion or so) do it? This is the main
> sticking point I have been having. I need a generator extemely
> random, no matter the computational power required.
You need to select numbers which work for 64-bits read Knuth (Art
of Computer Programming) or the Park and Miller paper in Comm. ACM
(Random Number Generators: Good ones are Hard to Find, Comm. ACM, 31,
10, 1192-1201). But if you need an "extremely random" generator DON'T
USE LCGs! If you are interested in why, I can provide references.
> Another thing is routines to handle 64 bit and larger integers on a 32
> bit processor. I have written a 32 bit multiplier with 64 bits out, but I
> really don't want to have to reinvent the wheel here. So if you have
> knowledge of where I could find these it would be extemely helpful.
Funny you should mention it. The BBS based generator mentioned
above started out as a test for the portable 64 and 128 bit arithmetic
in the ADAR components. These can be found on the ajpo machine,
sw-eng.falls-church.va.us, and include the RNGs.
Robert I. Eachus
with Standard_Disclaimer;
use Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...
--
Robert I. Eachus
with Standard_Disclaimer;
use Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...