wanted: FAST binary random number generator
Byung-Ro Moon
As I need fairly many calls for this, random()%2 (or random() mod 2)
takes too much time as the Unix routine random() or rand() are not so cheap.
Any help will be appreciated.
-- BR
Dan Putnam
: I'm looking for a very FAST and reasonable binary random number generator.
: -- BR
Random number generation algorithms tend to be multi-bit creatures.
How about saving a call to random() in a variable and accessing
the bits sequentially? You should probably check to see if the
random number generator is really giving you independently distributed
bits.
Nick Maclaren
Byung-Ro Moon <mo...@maui.cs.ucla.edu> wrote:
>I'm looking for a very FAST and reasonable binary random number generator.
>As I need fairly many calls for this, random()%2 (or random() mod 2)
>takes too much time as the Unix routine random() or rand() are not so cheap.
The way to do this is the following:
1) Start with a good random number generator - not random(), not
drand48() and DEFINITELY not rand()! I advise Wichmann-Hill, or ask
me for source of my fancier one.
2) Write a simple function that converts the U(0,1) floating-point
number to an integer in the range 0-(2^n-1), and returns the bits
one-by-one for the next n calls. Watch out because some compilers
have broken double<->unsigned long conversions in C.
Alternatively, you could use a specialised bit generator. I don't
advise this, because an even higher proportion of them are total
rubbish than the U(0,1) generators! Most genuine bit generators are
really intended for hardware implementation, anyway.
Nick Maclaren,
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nm...@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
Jochen Ruhland
-0800), Byung-Ro Moon (mo...@maui.cs.ucla.edu) says...
>
>I'm looking for a very FAST and reasonable binary random number
generator.
(GENlib ftp://ftp.neuro.informatik.uni-kassel.de
/pub/NeuralNets/GA-and-NN), routine insprired by
@BOOK( nrasc,
author = "William H. Press and Brian P. Flannery and Saul A.
Teukolsky and William T. Vetterling",
title = "Numerical Recipies",
publisher = "Cambridge University Press",
year = 1986
)
static unsigned long _rand16 = 0;
#define M4 120050L
#define IA4 2311L
#define IC4 25367L
unsigned short rands(void)
{
_rand16 = (_rand16 * IA4 + IC4) % M4;
return (unsigned short) (_rand16 & 0xffff);
}
Set _rand16 to different values each time you start your program to
have "real" random values on every run.
If you don't require a long turnaround for the generator you may
substitute smaller values for the constants, but I don't think that
the code will be faster on modern 32-bit architectures.
wr
--
* FG Neuronale Netzwerke / Uni Kassel *
* Jochen Ruhland *
* Heinrich-Plett-Str. 40 *
* D-34132 Kassel *
* joc...@neuro.informatik.uni-kassel.de *
* Tel: +49-561-804-4376 FAX: -4244 *
If C++ is the answer, I forgot the question.
If we convert one COBOL programmer per minute to Smalltalk, we
should
have a revolution by the time Capt. Kirk and the USS Enterprise
return
from Vulca on impulse power.
Kym Horsell
Something based on Chardenowne's number is probably a reasonably candidate
being easy to generate and provably "normal". But it isn't good on many
"randomness" scores (e.g. auto-corr).
Pseudo-C:
unsigned long bits=0;
unsigned long next=0;
/* to init */
next = some_number;
/* to get next random number */
randbit();
where:
INLINE int randbit(){
static unsigned long ff=0;
bits/=2;
if(bits<=1) bits=next++^(ff^=0x55555555L);
return bits&1;
}
--
R. Kym Horsell
khor...@EE.Latrobe.EDU.AU k...@CS.Binghamton.EDU
Torben AEgidius Mogensen
> I'm looking for a very FAST and reasonable binary random number generator.
> As I need fairly many calls for this, random()%2 (or random() mod 2)
> takes too much time as the Unix routine random() or rand() are not so cheap.
Below I have included an old posting about this very subject. However,
I suggest you use a bit from the middle instead of from the end if you
only need one bit.
Torben Mogensen (tor...@diku.dk)
===================8<---------------------------
From: cla...@chsun.chuug.ch (Claudio Nieder)
Newsgroups: comp.programming
Subject: Re: Please: A super-duper fast random bit generator
Message-ID: <1992May12.2...@chsun.chuug.ch>
Date: 12 May 92 20:44:53 GMT
References: <1992May12....@cc.ic.ac.uk>
Organization: CHUUG Swiss Unix Systems Users Group
Lines: 25
red...@ee.ic.ac.uk (Adrian Redgers) writes:
: Where can I lay my hands on a super "bitwise" rng?
Here is one I found in the amiga.lib. It has a function called fasrrand
which work like this:
1. Get your actual seed (32 bit).
2. shift left seed
3a. If the result is 0, or if the most signifcant bit
of the original seed was 1 (the one which got shifted out)
then perform an exclusive or with $1D872B41.
3b. Otherwise do nothing else.
4. The resulting value is your new seed. Go to 1.
If you need only 1 bit at a time, then get the MSB or LSB of the seed.
A collegue which was also on the search of good random generator took a
look at it, and compared it to other types, e.g. shift and feedback or
modulo types. The result was, that when analyzing probability of the
occurance of 1,computing autocorrelations on the bitstream etc. this
random generator performed very well. So it's not only simple but also
good.
claudio
--
Igor Pechtchanski
> I'm looking for a very FAST and reasonable binary random number generator.
> As I need fairly many calls for this, random()%2 (or random() mod 2)
> takes too much time as the Unix routine random() or rand() are not so cheap.
>
> Any help will be appreciated.
>
> -- BR
In DOS here's a little trick you can use: call random() once, then assign
the result of random() to a pointer. Use that pointer as an integer to
get the bits sequentially. After the last bit, set the pointer to the
value at the location it points to. Then repeat...
For example:
long m;
int *p;
BIT rnd;
p=(int *) random(); /* the random pointer */
m=0x10000; /* the mask */
s=15; /* the shift */
while (...) {
if (!(m>>=1)) {
p=(int *) *p;
m=0x10000;
s=15;
}
rnd=(p&m)>>s--;
}
This (or something like this) should work.
Please, don't flame me, the guy asked for a FAST random number generator,
regardless of methods... Anyway, this won't work on any protected system
(such as UNIX or WINDOWS).
|\ _,,,---,,_ ipec...@its.brooklyn.cuny.edu
ZZZzz /,`.-'`' -. ;-;;,_ ipec...@vaxa.crc.mssm.edu
|,4- ) )-,_. ,\ ( `'-' Igor Pechtchanski
'---''(_/--' `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-. Meow!
Jason Chen Hiung Tai
>Pseudo-C:
>where:
Try this, which appeared in the Australian Personal Computer Magazine
years ago.
unsigned long r =0xF5368A74; /* or generated randomly using slow method */
unsigned RandomBit() {
r = ((((r >> 31) ^ (r >> 6) ^ (r >> 4) ^ (r >> 1) ^ r) & 1) << 31) | (r >> 1);
return r & 1;
}
Alternatively, if true randomness in not very important, then just do a rotate on any predetermined random bit pattern and grab the first (or last) bit.
Jason Tai
Silvere Martin-Michiellot
Just an idea...
On thing that can be done is to read sequentially the bits (or even bytes)
of the memory of your computer (the RAM, boys).
Of course, you have to choose addresses of programs, not data, and, then,
there is a great probability that your average random will be .5 (or 127.5 for
random bytes).
Call me I you think about something faster :-)
-----------------
"Is anyone alive down there ?"
Silvere MARTIN-MICHIELLOT
William Clark Naylor
>As I need fairly many calls for this, random()%2 (or random() mod 2)
>takes too much time as the Unix routine random() or rand() are not so cheap.
random() generates 32 useable random bits. Make a call to random() and
store the result in an int. Shift out the bits from this int 32 times,
then make another call to random() to generate 32 more random bits. Etc.
David M. Tate
>Two methods come to mind:
> 1) using part of a low-level system timer, I am not sure about
> the desired characteristics of your random function,
This is *extremely* dangerous. It's not that hard to get into a loop whose
execution time is a fairly stable near-multiple of 2^n milliseconds for some
n, and thus to get highly-correlated low-order bits from your clock on
successive calls. Ditto for base-10 clock times. This is called 'aliasing',
and will give you horribly anomalous results.
...not to mention that debugging randomized code is a bitch if you can't
reproduce the same stream of pseudorandom numbers on demand.
> 2) if the range is relatively small and/or RAM is sufficent I
> would suggest entering the entire range 1 1/2 times into an
> array and shuffling the array periodically - in short use a
> table lookup for speed.
If you want speed, you can't beat just copying some table of random bits
(derived by coin tosses, or copied from a text, or what have you) into a
large array, and scanning the array repeatedly. For statistical applications
this would be hopelessly inadequate, due to the short period. For games
(or, for that matter, genetic algorithms), it should do just fine. I'd
recommend a prime number of entries, to avoid aliasing problems.
--
David M. Tate Decision-Science Applications, Inc.
dt...@dsava.com 1110 N. Glebe Road, Suite 400
Senior Operations Research Analyst Arlington, VA 22201
(703) 243-2500
Lawrence Chee
Two methods come to mind:
1) using part of a low-level system timer, I am not sure about
the desired characteristics of your random function,
2) if the range is relatively small and/or RAM is sufficent I
would suggest entering the entire range 1 1/2 times into an
array and shuffling the array periodically - in short use a
table lookup for speed.
Lawrence D. Chee
lc...@csc.com
Silvere Martin-Michiellot (syl...@divsun.unige.ch) wrote:
Wilbert Schelvis
Silvere Martin-Michiellot <syl...@divsun.unige.ch> wrote:
>In article t...@vixen.cso.uiuc.edu, dpu...@prairienet.org (Dan Putnam) writes:
>>Byung-Ro Moon (mo...@maui.cs.ucla.edu) wrote:
>>: I'm looking for a very FAST and reasonable binary random number generator.
>>: As I need fairly many calls for this, random()%2 (or random() mod 2)
>>: takes too much time as the Unix routine random() or rand() are not so cheap.
A good method for generating semi-random bit sequences by using
primitive polynomes if GF(2), well known in coding theory. I will not
bother you with the details, but give a simple algorithm.
main()
{
int reg = 5; /* can be any value except 0 */
while(1)
{
reg <<= 1;
reg += (((reg & 0x2000) == 0) == ((reg & 0x0800) == 0));
/* least significant bit of reg is pseudo-random */
printf("%s", (reg & 0x01) ? "1" : "0");
}
}
This algorithm will generate a pseudo-random bit string, with a period
of 2^13 - 1. Longer sequences can also be generated by using long
integers and replacing the values 0x2000 and 0x0800 by
0x00020000 and 0x00008000 (sequence length 2^17 - 1) or
0x00080000 and 0x00020000 (sequence length 2^19 - 1) or
0x00800000 and 0x00200000 (sequence length 2^23 - 1) or
0x20000000 and 0x08000000 (sequence length 2^29 - 1) or
0x80000000 and 0x20000000 (sequence length 2^31 - 1)
respectively.
Gr., Wilbert
--------------------------------------------------------------------------
Wilbert Schelvis Royal PTT Nederland
KPN Research, Neher Laboratories room: LE124
PO BOX 421 phone: +31703326486
2260 AK Leidschendam fax: +31703326477
the Netherlands email: w.a.m.s...@research.ptt.nl
Tom Howland
defy anyone to come up with a faster version.
/* This is an implementation of algorithm AS 183 from the journal
"Applied Statistics".
random() returns a random number between 0.0 and 1.0
*/
static int A = 27134,
B = 9213,
C = 17773;
static int S = 0x19551011;
double random() {
double T = (A = (A*171) % 30269)/30269.0
+ (B = (B*172) % 30307)/30307.0
+ (C = (C*170) % 30323)/30323.0;
return T-(int)T;
}
Tom Howland Internet mailing address: t...@kwi.com
Senior Software Engineer FAX: +1 415 802 7143
Sterling Software, Incorporated Phone: +1 415 802 7100 extension 2072
303 Twin Dolphin Drive, Suite 600 Voice Mail: +1 415 802 7125
Redwood City, California 94065-1417 Long Distance: +1 800 964 0154
world wide web page: http://www.rahul.net/tom
Massimo Marchiori
: Hello,
: Lawrence D. Chee
: lc...@csc.com
: : -----------------
: : Silvere MARTIN-MICHIELLOT
Another trick is to consider the last bit of the time in milliseconds from
startup time (or just the current clock if millisecs is the time unity):
this works fine for accesses that are "random" (eg user-driven), or also in
multi-user environments where the exec time is not deterministic.
Massimo
+-----------------------------------------------------------------------------+
| Massimo Marchiori Dept. of Pure and Applied Mathematics |
| phone: +39 49 831972 University of Padova |
| fax: +39 49 8758596 via Belzoni 7, 35131 Padova, ITALY |
| email: m...@hilbert.math.unipd.it URL: http://www.math.unipd.it/~max |
+-----------------------------------------------------------------------------+
Atte J Moilanen
generators, and here are some comments: Reading from Maddox (1994)
and Press et al. (1992) one gets convincing evidence that many
of that random number generators that have been (and still are)
in common use range from barely adequate to "totally botched".
Meaning that the generators can fail various simple statistical tests.
This implies that there might easily be problems with improvised
binary generators also. Four impressions that one gets from Press et al.
and Maddox:
(1) One group of generators that one should regard with extra
special care are all system supplied rand() generators and
16 or 32 bit integer returning generators of common micro-
computer compilers. These are usually some variants of
linear congruential generators, which are not good.
Also the manual typically does not mention how the generator
works so one doesn't know what one gets.
(2) Never try to break a system supplied random number into
smaller supposedly random pieces (bits etc.)!! This fails
beacuse of serial correlation in low order bits.
(3) "Adding extra randomnes" by messing random numbers up
even more by bit shifts, XORs, etc. operators is a
good way to mess up an otherwise passable rnd num. generator.
(4) Good generators are based on solid thory.
Press at al. (1992) (an excellent book on numerical algorithms) contains
a very entertaining and readable 50 page introduction to random numbers
including theory, references and C code for many "good" generators.
Also two generators for random bits are included. However, the code in
the book is under the lisence "buy the book then
you can use the code" so I'm sorry I can't include the code here.
Knuth (1981) is the book containing much of the theory of random numbers.
Hope this helpes someone.
Atte Moilanen
(Mail. Atte.M...@Helsinki.Fi)
References:
Knuth, D.E. (1981) Seminumerical algorithms, 2nd ed. In The art of
computer programming, vol 2. Reading, MA: Addison-Wesley.
Maddox, J. (1994). The poor quality of random numbers. Nature
vol 372: 403.
Press, W.H. et al. (1992) Numerical receipes in C. The art of scientific
computation. Cambridge: Cambridge university press.
Vattulainen et al. (1994), sited in Maddox (1994).
Phys. Rev. Lett. vol 73: 2513-2
Robert Fry
The ACM has posted a number of articles on random number generators as well. Many
of which take significantly less processing time than linear-congruential methods.
Unfortunately, I do not have a background in mathematics or statistics, so I can't
say how useful any particular algorithm is for your particular needs, but the
July, 1992 issue of the acm 'Transactions on Modeling and Computer Simulation' has
one that only takes 4 instructions (plus procedure overhead) for each number
generated, has a repeat length as high as you want, and which passes several of
the standard statistical tests. And, as the functions are all bit operations, they
are generally less costly than the multiply & divide operations used by Linear
Congruential methods.
Bob
Mick Brown
congruential based which do not give good random bit distributions. (Most
are not suitable for monte carlo simulations either, at least on PC
clones.) Check Knuth: the art of computer programming vol 2, seminumerical
algorithms or Numerical Recipes.
--Mick Brown (lfirra...@bix.com)