On Number Generators
Ashiq Alibhai
a balanced randomizer? I presume you can code one yourself. I use
whatever the programming language provides. Is there a way to test the
"quality" of it, i.e. to see if it's truly random?
Xub...@gmail.com
repeatedly -- say, 10,000 times thru the cycle -- and see what sort of
'spread' you get in the iterated results. Is it evenly distributed, are
there 'clumps' in the distribuion, or what?
Ashiq Alibhai
their distribution?
Paul E Collins
> This topic comes up from time to time--how do you
> make sure you've got a balanced randomizer? I
> presume you can code one yourself.
It clearly needs to be based on some kind of unpredictable external
value. Typically this might be the time according to the system clock
(combined with whatever other variable flags and settings are
available), which is good enough for most purposes. To do much better
than that, I think you'd need a piece of hardware that samples the
real world in some way (e.g. measuring radioactive decay) - probably
not necessary for an adventure game!
P.
Bert Byfield
> whatever the programming language provides. Is there a way to test the
> "quality" of it, i.e. to see if it's truly random?
My favorite way is to generate a random series of X and Y points in a two-
dimensional grid space, and make a picture. If your picture is like snow,
evenly distributed, the numbers are random. If your picture has bands or
lumps, you don't.
Ben Rudiak-Gould
> This topic comes up from time to time--how do you make sure you've got
> a balanced randomizer? I presume you can code one yourself. I use
> whatever the programming language provides. Is there a way to test the
> "quality" of it, i.e. to see if it's truly random?
You can find freely usable source code for high quality pseudorandom number
generators on the web. The "Mersenne twister" is the most popular right now.
It's overkill for interactive fiction, but so are modern computers in many ways.
I think that the broken PRNGs that are mentioned in the DM4 are those that
produce short repeating patterns when taken modulo a small constant. Try
printing random()%2, random()%2, ... and see what you get. I think that some
C libraries' generators are so bad that they'll produce something like
0,1,0,1,...
-- Ben
Andrew Plotkin
>
> I think that the broken PRNGs that are mentioned in the DM4 are those that
> produce short repeating patterns when taken modulo a small constant.
Yes.
But that was really a 1997-era problem. Modern interpreters get it
right, or right enough.
--Z
"And Aholibamah bare Jeush, and Jaalam, and Korah: these were the borogoves..."
*
If the Bush administration hasn't thrown you in military prison without trial,
it's for one reason: they don't feel like it. Not because you're an American.
Max
> This topic comes up from time to time--how do you make sure you've got
> a balanced randomizer? I presume you can code one yourself. I use
> whatever the programming language provides. Is there a way to test the
> "quality" of it, i.e. to see if it's truly random?
>
Someone gave a reference to the Mersenne Twister, which is a high
quality PRNG, but not easy to code.
The standard basic PRNG is the Linear Congruential Method (it's used in
Java's java.util.Random class).
The pseudocode (from The Design & Analysis of Algorithms by Anany Levitin):
---------------------------------------------
To generate n random numbers (r[1]..r[n])
r[0] = seed
for i = 1 to n:
r[i] = (a*r[i-1] + b) mod m
---------------------------------------------
seed is chosen arbitrarily (e.g. from the clock)
m is a large number - possibly the largest number that fits into the
variable
a should be between 0.01m and 0.99m, with no pattern in its digits, and
a mod 8 = 5
b can be 1
---------------------------------------------
The way to check if it's truly random: it's not. As Von Neumann said,
anyone who contemplates a true random number generator is living in a
state of sin. But there is something called the chi-squared test, which
you may find useful - I don't know it, so look it up.
--Max
Carl Burke
of random number generators. It's the first half of "Seminumerical
Algorithms",
volume 2 of "The Art of Computer Programming"; he spends 190 pages on it.
Linear congruential generators give decent results if you pick the right
parameters;
most generators out there in libraries are pretty good about using provably
good generators these days, but you can roll your own if you feel more
comfortable doing that.
Carl Burke
cbu...@mitre.org
"Ashiq Alibhai" <shiny...@gmail.com> wrote in message
news:1136759011.5...@f14g2000cwb.googlegroups.com...
Ben Rudiak-Gould
> ---------------------------------------------
>
> To generate n random numbers (r[1]..r[n])
>
> r[0] = seed
>
> for i = 1 to n:
> r[i] = (a*r[i-1] + b) mod m
>
> ---------------------------------------------
This is exactly the sort of generator that causes problems with interactive
fiction games! If m is even then r[i] will alternate between even and odd,
so games which make a binary choice based on random()%2 will be completely
predictable. A lot of C libraries use a power of two for m. You can fix this
problem by using a prime m (slow) or by discarding the low bits of each
generated number (faster).
-- Ben
Ashiq Alibhai
the research, how about a quick solution i.e. "implement this
algorithm"?
I'm looking for something simple and basic--doesn't have to be perfect,
as long as it doesn't cause predictable results.
The Wanderer
> Do you mean use the arbitrary seed to generate 10,000 seeds and see
> their distribution?
No. Start with an arbitrary number; use that as the seed to generate
result 1. Log result 1, then feed it in as the seed to generate result
2. Log result 2, then feed it in as the seed to generate result 3. And
so on.
Each result, in addition to being logged for later distribution
analysis, serves as the seed for the next iteration of the loop.
--
The Wanderer
Warning: Simply because I argue an issue does not mean I agree with any
side of it.
Secrecy is the beginning of tyranny.
Dan Shiovitz
The quick solution is to use what your programming language provides.
In almost all cases, the random number generator in modern
languages/libraries is going to be fine. Assuming, perhaps foolishly,
that we're talking about IF languages, TADS and Inform and Hugo and so
on all have totally adequate RNGs in all the modern interpreters.
If for some reason this won't do, and for some reason you don't trust
the built-in RNG in whatever language you're looking in, and you don't
feel up to translating from a description of some algorithm, and you
don't feel up to finding a book in whatever language that has an
implementation, I suggest using a search engine to look for, eg,
"mersenne twister", which should eventually lead you to somewhere like
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/eversions.html
--
Dan Shiovitz :: d...@cs.wisc.edu :: http://www.drizzle.com/~dans
"He settled down to dictate a letter to the Consolidated Nailfile and
Eyebrow Tweezer Corporation of Scranton, Pa., which would make them
realize that life is stern and earnest and Nailfile and Eyebrow Tweezer
Corporations are not put in this world for pleasure alone." -PGW
Roger Firth
news:dq65bf$lja$1...@cascadia.drizzle.com...
>
> The quick solution is to use what your programming language provides.
>
> In almost all cases, the random number generator in modern
> languages/libraries is going to be fine. Assuming, perhaps foolishly,
> that we're talking about IF languages, TADS and Inform and Hugo and so
> on all have totally adequate RNGs in all the modern interpreters.
>
> If for some reason this won't do, and for some reason you don't trust
> the built-in RNG in whatever language you're looking in, and you don't
> feel up to translating from a description of some algorithm, and you
> don't feel up to finding a book in whatever language that has an
> implementation, I suggest using a search engine to look for, eg,
> "mersenne twister", which should eventually lead you to somewhere like
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/eversions.html
Good advice, Dan, but doesn't quite solve my problem (which
probably isn't the same as Ashiq's). I'm looking for an adequate
16-bit Random Number Generator which can be implemented in
Inform. Why? To override the built-in generator, which is provided
by the Z-machine (and Glulx) interpreters. For test suite purposes,
I'd like to be able to generate the same sequence of pseudo-random
numbers, irrespective of the platform and interpreter being used to
run the tests. I'm afraid I'm much too lightweight a mathematician
to be able to translate the MT implementations (which are possibly
overkill anyway), but I'm sure somebody here can point to a suitable
algorithm.
Cheers, Roger
--
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
You'll find all my IF pages at http://www.firthworks.com/roger
WARNING: aggressive spam deletion -- use a meaningful Subject!
Samwyse
> Good advice, Dan, but doesn't quite solve my problem (which
> probably isn't the same as Ashiq's). I'm looking for an adequate
> 16-bit Random Number Generator which can be implemented in
> Inform. Why? To override the built-in generator, which is provided
> by the Z-machine (and Glulx) interpreters. For test suite purposes,
> I'd like to be able to generate the same sequence of pseudo-random
> numbers, irrespective of the platform and interpreter being used to
> run the tests. I'm afraid I'm much too lightweight a mathematician
> to be able to translate the MT implementations (which are possibly
> overkill anyway), but I'm sure somebody here can point to a suitable
> algorithm.
I'd go with the one mentioned earlier:
Ben Rudiak-Gould wrote:
> Max wrote:
>
>> To generate n random numbers (r[1]..r[n])
>>
>> r[0] = seed
>> for i = 1 to n:
>> r[i] = (a*r[i-1] + b) mod m
>
> This is exactly the sort of generator that causes problems with
> interactive fiction games! If m is even then r[i] will alternate between
> even and odd, so games which make a binary choice based on random()%2
> will be completely predictable. A lot of C libraries use a power of two
> for m. You can fix this problem by using a prime m (slow) or by
> discarding the low bits of each generated number (faster).
There's nothing in this that restricts you to 32-bit integers. Also, if
you can live with a slightly restricted set of outputs, you can get fair
speed by using a Mersenne prime as the value for m. Since (like all
Mersenne primes) these are one less than a power of two, you can replace
the modulo operator with a logical AND.
Global rng_seed;
Constant m $1FFF ! Mersenne prime M13
Constant a $1555 ! alternating ones and zeros, (a % 8 == 5)
Constant b 1;
[ base_rng ;
rng_seed = (a * rng_seed + b) & m;
return rng_seed;
];
Replace random;
[ random n r1 r2;
if (n<m) return base_rng() % n + 1;
! need more that 13 bits, so get two values, shift one of the
! over two places, and XOR them together to preserve randomness.
r1 = base_rng();
r2 = 4 * base_rng();
! XOR is one or the other, but not both
return ((r1 | r2) & ~(r1 & r2)) % n + 1;
];
As always, this is untested code.
David Thornley
Paul E Collins <find_my_re...@CL4.org> wrote:
>"Ashiq Alibhai" <shiny...@gmail.com> wrote:
>
>> This topic comes up from time to time--how do you
>> make sure you've got a balanced randomizer? I
>> presume you can code one yourself.
>
>It clearly needs to be based on some kind of unpredictable external
>(combined with whatever other variable flags and settings are
>available), which is good enough for most purposes.
Although not for internet-based games with significant money
involved, which we really aren't concerned about here.
To do much better
>than that, I think you'd need a piece of hardware that samples the
>real world in some way (e.g. measuring radioactive decay) - probably
>not necessary for an adventure game!
>
Almost certainly not necessary (although that can be useful for
cryptographic purposes). Besides, for debugging purposes it's
nice to be able to have a repeatable RNG so you can run the game
to a certain point from a script, and have problems be reproducible.
--
David H. Thornley | If you want my opinion, ask.
da...@thornley.net | If you don't, flee.
http://www.thornley.net/~thornley/david/ | O-
John W. Kennedy
A standards-conforming Z-machine has this already, does it not? Or is it
only a recommendation?
--
John W. Kennedy
"But now is a new thing which is very old--
that the rich make themselves richer and not poorer,
which is the true Gospel, for the poor's sake."
-- Charles Williams. "Judgement at Chelmsford"
Neil Cerutti
> Roger Firth wrote:
>> Good advice, Dan, but doesn't quite solve my problem (which
>> probably isn't the same as Ashiq's). I'm looking for an
>> adequate 16-bit Random Number Generator which can be
>> implemented in Inform. Why? To override the built-in
>> generator, which is provided by the Z-machine (and Glulx)
>> interpreters. For test suite purposes, I'd like to be able to
>> generate the same sequence of pseudo-random numbers,
>> irrespective of the platform and interpreter being used to run
>> the tests. I'm afraid I'm much too lightweight a mathematician
>> to be able to translate the MT implementations (which are
>> possibly overkill anyway), but I'm sure somebody here can
>> point to a suitable algorithm.
>
> A standards-conforming Z-machine has this already, does it not?
> Or is it only a recommendation?
Yes, there's an Inform statement that orders up a consistent
stream of psuedo-random numbers. But Roger, as I understand it,
wants the stream to be consistent between interpreters, so it's
not sufficient to be consistent for just one interpreter.
--
Neil Cerutti
Richard Bos
> Good advice, Dan, but doesn't quite solve my problem (which
> probably isn't the same as Ashiq's). I'm looking for an adequate
> 16-bit Random Number Generator which can be implemented in
> Inform. Why? To override the built-in generator, which is provided
> by the Z-machine (and Glulx) interpreters. For test suite purposes,
> I'd like to be able to generate the same sequence of pseudo-random
> numbers, irrespective of the platform and interpreter being used to
> run the tests.
Will an internally 32-bit RNG with a 16-bit output do? This one
implements (_if_ I've got the details right) the following RNG from
George Marsaglia, which is good enough for many purposes:
y^=y<<13; y^=y>>17; y^=y<<5;
where y is a member of [1..2**32-1]
(FTR, he posted this to comp.lang.c in
<WAEV7.5401$i8.9...@news1.rdc1.fl.home.com>.)
rand(n), n>0: random number from [1..n]
rand(), rand(0): random number from [1..2**15-1]
rand(n), n<0: seed RNG, proceed as for rand(-n)
If asked for a random number without being seeded, gets a random seed
from the ZMachine RNG.
---------------------------------------------------------
Global seedle; ! Largest 15 bits
Global seedme; ! Middle 2 bits
Global seedse; ! Smallest 15 bits
! There is nothing magical about the above division, except that it
! makes both the middle right-shift and the return statement simpler.
! This is a bit of serendipity, because the right-shift is by 17 bits,
! which just happens to be the 32-bit complement of the 15 bits needed
! for an Inform integer.
[ rand value helple helpme helpse;
if (value<0) { value=-value; seedle=value; seedme=0; seedse=value; }
if (seedle==0 && seedme==0 && seedse==0) {
seedle=random(32767); seedme=random(3); seedse=random(32767);
}
helple=(seedle&$$11)*8192 + seedme*2048 +
(seedse&$$111111111110000)/16;
helpme=(seedse&$$1100)/4;
helpse=(seedse&$$11)*8192;
seedle=(seedle|helple) & (~(seedle&helple));
seedme=(seedme|helpme) & (~(seedme&helpme));
seedse=(seedse|helpse) & (~(seedse&helpse));
helpse=seedle;
seedse=(seedse|helpse) & (~(seedse&helpse));
helple=(seedle&$$1111111111)*32 + seedme*8 +
(seedse&$$111000000000000)/4096;
helpme=(seedse&$$110000000000)/1024;
helpse=(seedse&$$1111111111)*32;
seedle=(seedle|helple) & (~(seedle&helple));
seedme=(seedme|helpme) & (~(seedme&helpme));
seedse=(seedse|helpse) & (~(seedse&helpse));
if (value==0)
return seedse + (seedse==0);
else
return (seedse%value)+1;
];
---------------------------------------------------------
Richard
Richard Bos
> "Roger Firth" <ro...@firthworks.com> wrote:
>
> > Good advice, Dan, but doesn't quite solve my problem (which
> > probably isn't the same as Ashiq's). I'm looking for an adequate
> > 16-bit Random Number Generator which can be implemented in
> > Inform. Why? To override the built-in generator, which is provided
> > by the Z-machine (and Glulx) interpreters. For test suite purposes,
> > I'd like to be able to generate the same sequence of pseudo-random
> > numbers, irrespective of the platform and interpreter being used to
> > run the tests.
>
> Will an internally 32-bit RNG with a 16-bit output do?
^^
*cough* 15-bits output, to avoid problems with Inform's signed-only
integers.
Richard
Samwyse
> "Roger Firth" <ro...@firthworks.com> wrote:
>
>
>>Good advice, Dan, but doesn't quite solve my problem (which
>>probably isn't the same as Ashiq's). I'm looking for an adequate
>>16-bit Random Number Generator which can be implemented in
>>Inform. Why? To override the built-in generator, which is provided
>>by the Z-machine (and Glulx) interpreters. For test suite purposes,
>>I'd like to be able to generate the same sequence of pseudo-random
>>numbers, irrespective of the platform and interpreter being used to
>>run the tests.
>
>
> Will an internally 32-bit RNG with a 16-bit output do? This one
> implements (_if_ I've got the details right) the following RNG from
> George Marsaglia, which is good enough for many purposes:
That looks good, especially since I suddenly suspect that my version
depends on 32-bit math during the multiplications.
Roger Firth
news:yVXxf.8652$dW3....@newssvr21.news.prodigy.com...
> Richard Bos wrote:
>>
>> Will an internally 32-bit RNG with a 16-bit output do? This one
>> implements (_if_ I've got the details right) the following RNG from
>> George Marsaglia, which is good enough for many purposes:
>
> That looks good, especially since I suddenly suspect that my version
> depends on 32-bit math during the multiplications.
Thanks to Neil for his clarification, and to Sam and Richard for
their algorithms, which I hope to check out tomorrow.
Samwyse
> "Samwyse" <sam...@gmail.com> wrote in message
> news:yVXxf.8652$dW3....@newssvr21.news.prodigy.com...
>
>>Richard Bos wrote:
>>
>>>Will an internally 32-bit RNG with a 16-bit output do? This one
>>>implements (_if_ I've got the details right) the following RNG from
>>>George Marsaglia, which is good enough for many purposes:
>>
>>That looks good, especially since I suddenly suspect that my version
>>depends on 32-bit math during the multiplications.
>
>
> Thanks to Neil for his clarification, and to Sam and Richard for
> their algorithms, which I hope to check out tomorrow.
I thought about it some more and decided that my version is 16-bit safe
after all. Multiplying two 14-bit numbers will overflow, but we're
discarding the high bits anyway. A bigger issue is whether you need to
handle all of the valid arguments for random().
! This portion is the same as before
Global rng_seed;
Constant m $1FFF ! Mersenne prime M13
Constant a $1555 ! alternating ones and zeros, (a % 8 == 5)
Constant b 1;
[ base_rng ;
rng_seed = (a * rng_seed + b) & m;
return rng_seed;
];
Replace random;
[ random n r1 r2;
if (n<0) {
rng_seed = - n;
return;
}
if (n==0) {
! We need more than 13 bits, so get two values, shift one of them
! over two places, and XOR them together to preserve randomness.
r1 = base_rng();
r2 = 4 * base_rng();
! XOR is one or the other, but not both
return (r1 | r2) & ~(r1 & r2);
}
if (n<=m) return base_rng() % n + 1;
return random() % n + 1;
];
rpresser
managed (I think) to compile a version of the TT800 random number
generator [2], which is a smaller cousin of the renowned Mersenne
Twister. It works with longs internally, which is why I needed vbccz,
but it now returns a random signed 16-bit integer. (Someone more
knowledgeable than I will have to decide if cutting the return value in
half causes any important bias in the RNG.) I am getting the same
results from the Z5 version and the gcc-compiled win32 version.
I'd like someone else to review my work before I upload it to the
archive. I feel a sense of accomplishment, and yet insecure. Email me
for a copy.
[1] http://www.cowlark.com/vbcc-z-compiler.html
[2] http://random.mat.sbg.ac.at/ftp/pub/data/tt800.c
bob_j...@burtleburtle.net
if (x >= 0x4000) {
x = x * 2;
x = x ^ 0xd37b;
}
else {
x = x*2;
}
? x = (0xd37b | x) & ~(0xd37b & x) is the same as ^ if there's no ^.
That lists every number in 1..0x7fff once, in a randomish order, then
repeats. Except 0, which it maps to 0.