1. More on Random Number Generators in Euphoria
>
>Hmm... I don't know much about that. I've written multiple-dice-rolling
>functions using rand(), and they give a proper-looking bell curve, so that's
>always seemed random enough for me. How do you decide how random
>is random enough? (on a philosophical sidenote, if you know how random
>something is, does that make it less random?)
The old test (mid '80s in Turbo Pascal of Turbo C) was to plot dots on an
NxN square. if a pattern showed up it was obvious that it was not really
random but predictable pattern. I wrote one similar to this in Euphoria for
a 400 x 400 square and got what I think may be some anomalous results. I
have not had a chance to try coding another test I have seen which plots
the dots to the interior of a sphere and presents the results as in three
different windows (X,Y,Z Planes) which can be viewed to look for patterns.
How much randomness is good? In a board game if rolling a "die" is always
more likely to roll a 2 than a 6 you'd call the game unfair and the dice
loaded.
The tests for RNG (or more properly pseudo-random number generators) have
gotten more and more rigorous. Marsaglia issued a battery of tests (Called
the DieHard tests of course! 
) which the KISS code below passes (sorry
it's in C as Euphoria does not have completely equivalent code).
The first three defines are RNGs. MWC has a period of 2^60. SHR3 has a
period of 2^32-1. and the CONG a period of 2^32. The SWG has a period of
2^7578 but has some randomness shortcomings but by combining SWG with the
KISS generator which has a period of 2^123, you get a RNG that passes the
tests and has a period of greater than 2^7700 or as my windows calculator
reports 8.53034532588326944571607353968e+2317.
In statistics and games that's a nice generator.
#define MWC ((znew<<16)+wnew )
#define SHR3 (jsr^=(jsr<<17), jsr^=(jsr>>13), jsr^=(jsr<<5))
#define CONG (jcong=69069*jcong+1234567)
#define KISS ((MWC^CONG)+SHR3)
#define SWB (c++,bro=(x<y),t[c]=(x=t[UC(c+34)])-(y=t[UC(c+19)]+bro))
>> b) a magic bullet that makes Euphoria do 64 bit logical operations or
>an
>>include file that does so.
>
>Well, if you can assume that it'll be used on Pentium MMX-equipped PCs,
>maybe you could poke and call the machine code for PAND, POR, and
>PXOR... (the MMX 64-bit bitwise instructions). Don't know if that requires
>any special work, but I can try it. If it works it'd be quicker than
>sequencizing them.
I also hear that the Pentium III has a hardware RNG but as I and most folks
don't currently have a PIII, it is a moot point.
I'd be interested in the code for the MMX 64bit operators...
2. Re: More on Random Number Generators in Euphoria
Has anybody run the Euphoria RNG through the Diehard test? It is available
online from several sources and should give a really good indication of
the reliability of the Eu construct. Before proceeding any further, it would
seem to be proper to test what we have. Visible patterns are fine, if they
show up. This is a much tougher test.
Everett L.(Rett) Williams
rett at gvtc.com
3. Re: More on Random Number Generators in Euphoria
On Mon, 14 Feb 2000 13:22:01 -0500, Everett Williams wrote:
>Has anybody run the Euphoria RNG through the Diehard test?
I decided to go ahead and look into this. The Diehard test is looking for
32-bit random numbers... The problem with Euphoria's 'rand' function is
that it will only produce random numbers up to 0x3FFFFFF (instead of
0xFFFFFFFF). What would be an acceptable method to obtain the required
range? Is it acceptable to generate two 16-bit random numbers and
concatenate them? Does anybody have any other valid suggestions? I could
try all suggested methods and see what works best...
-- Brian
4. Re: More on Random Number Generators in Euphoria
On Mon, 14 Feb 2000, Brian Broker wrote:
> On Mon, 14 Feb 2000 13:22:01 -0500, Everett Williams wrote:
>
> >Has anybody run the Euphoria RNG through the Diehard test?
>
> I decided to go ahead and look into this. The Diehard test is looking for
> 32-bit random numbers... The problem with Euphoria's 'rand' function is
> that it will only produce random numbers up to 0x3FFFFFF (instead of
> 0xFFFFFFFF). What would be an acceptable method to obtain the required
> range? Is it acceptable to generate two 16-bit random numbers and
> concatenate them? Does anybody have any other valid suggestions? I could
> try all suggested methods and see what works best...
>
> -- Brian
>
It would be acceptable to concatenate two 16 bit integers provided
you apply the results of the test only to 'the concatenation of two 16 bit
integers as generated by rand()'. =)
5. Re: More on Random Number Generators in Euphoria
On Mon, 14 Feb 2000 14:25:13 -0500, Brian Broker <bkb at CNW.COM> wrote:
>On Mon, 14 Feb 2000 13:22:01 -0500, Everett Williams wrote:
>
>>Has anybody run the Euphoria RNG through the Diehard test?
>
>I decided to go ahead and look into this. The Diehard test is looking for
>32-bit random numbers... The problem with Euphoria's 'rand' function is
>that it will only produce random numbers up to 0x3FFFFFF (instead of
>0xFFFFFFFF). What would be an acceptable method to obtain the required
>range? Is it acceptable to generate two 16-bit random numbers and
>concatenate them? Does anybody have any other valid suggestions? I could
>try all suggested methods and see what works best...
>
>-- Brian
It is perfectly legitimate to concatenate items. The output of a RNG should
normally be treated as a bit-stream anyway, arbitrarily divided under the
needs of the moment. That is not quite the same as concatenation, as in
concatenation usually some bits are thrown away. That is to say, when
you concatenate, you should not throw away the remainder, but put it at the
head of the next number. Even when throwing away portions, I believe that
it would be okay, if the number were shifted left 5 bits and the created zeros
replaced by the low order bits of the next number in sequence.
It would still be interesting to create a set of 10 to 11 megabytes in size
consisting of the 0x3FFFFFFF ranged numbers available and run it through
the diehard tests. The results might be instructive if it will accept the set
at all.
Everett L.(Rett) Williams
rett at gvtc.com
6. Re: More on Random Number Generators in Euphoria
--=====================_14631672==_.ALT
from the DIEHARD Manual:
"Write a main program that sends the (hex) output of your random
number procedure to an ordinary ascii file. Then invoke the
file on this disk, ASC2BIN.EXE that will prompt for the names
of your input and output files and do the conversion.
Your random number generator should produce 32-bit integers.
(If 31 bits, left justify by shift-left-one, as some of the
tests in DIEHARD favor leading bits.) You should send them to
your ascii file in hex form, 8 hex 'digits' per integer,
10 integers per line, no intervening spaces. The ascii file
will be twice as big as the binary file it is reduced to.
You can see that DIEHARD requires large test files. But they
need only be created one at a time, then deleted."
The program analyses the "goodness" (randomness) of the *bits* so a 0x3FFFFFF
limit is not relevant. Think of it as an 80,000,000 iteration cointoss.
At 04:34 PM 02/14/2000 -0400, you wrote:
>On Mon, 14 Feb 2000, Brian Broker wrote:
>
>> On Mon, 14 Feb 2000 13:22:01 -0500, Everett Williams wrote:
>>
>> >Has anybody run the Euphoria RNG through the Diehard test?
>>
>> I decided to go ahead and look into this. The Diehard test is looking for
>> 32-bit random numbers... The problem with Euphoria's 'rand' function is
>> that it will only produce random numbers up to 0x3FFFFFF (instead of
>> 0xFFFFFFFF). What would be an acceptable method to obtain the required
>> range? Is it acceptable to generate two 16-bit random numbers and
>> concatenate them? Does anybody have any other valid suggestions? I could
>> try all suggested methods and see what works best...
>>
>> -- Brian
>>
>
> It would be acceptable to concatenate two 16 bit integers provided
>you apply the results of the test only to 'the concatenation of two 16 bit
>integers as generated by rand()'. =)
Joel H. Crook
Manager, Information Services
Certified Novell Administrator
Microsoft Certified Professional, OS Specialist
Kellogg & Andelson Accountancy Corp.
14724 Ventura Blvd. 2nd Floor
Sherman Oaks, CA 91403
(818) 971-5100
--=====================_14631672==_.ALT
<html><div>from the DIEHARD Manual:</div>
<br>
<div> "Write a main program that sends the (hex) output of your
random</div>
<div> number procedure to an ordinary ascii file. Then
invoke the</div>
<div> file on this disk, ASC2BIN.EXE that will prompt for the
names</div>
<div> of your input and output files and do the
conversion.</div>
<br>
<div> Your random number generator should produce 32-bit
integers.</div>
<div> (If 31 bits, left justify by shift-left-one, as some of
the</div>
<div> tests in DIEHARD favor leading bits.) You should
send them to</div>
<div> your ascii file in hex form, 8 hex 'digits' per
integer,</div>
<div> 10 integers per line, no intervening spaces. The
ascii file</div>
<div> will be twice as big as the binary file it is reduced
to.</div>
<br>
<div> You can see that DIEHARD requires large test
files. But they</div>
<div> need only be created one at a time, then
deleted."</div>
<br>
<div>The program analyses the "goodness" (randomness) of the
*bits* so a 0x3FFFFFF limit is not relevant. Think of it as
an 80,000,000 iteration cointoss. </div>
<br>
<br>
<div>At 04:34 PM 02/14/2000 -0400, you wrote:</div>
<div>>On Mon, 14 Feb 2000, Brian Broker wrote:</div>
<div>></div>
<div>>> On Mon, 14 Feb 2000 13:22:01 -0500, Everett Williams
wrote:</div>
<div>>></div>
<div>>> >Has anybody run the Euphoria RNG through the Diehard
test?</div>
<div>>></div>
<div>>> I decided to go ahead and look into this. The Diehard
test is looking for</div>
<div>>> 32-bit random numbers... The problem with Euphoria's
'rand' function is</div>
<div>>> that it will only produce random numbers up to 0x3FFFFFF
(instead of</div>
<div>>> 0xFFFFFFFF). What would be an acceptable method to
obtain the required</div>
<div>>> range? Is it acceptable to generate two 16-bit random
numbers and</div>
<div>>> concatenate them? Does anybody have any other valid
suggestions? I could</div>
<div>>> try all suggested methods and see what works
best...</div>
<div>>></div>
<div>>> -- Brian</div>
<div>>></div>
<div>></div>
<div>> It would be
acceptable to concatenate two 16 bit integers provided</div>
<div>>you apply the results of the test only to 'the concatenation of
two 16 bit</div>
<div>>integers as generated by rand()'. =)</div>
<br>
Joel H. Crook<br>
<br>
Manager, Information Services<br>
<font size=1>Certified Novell Administrator<br>
Microsoft Certified Professional, OS Specialist<br>
<br>
</font><b>Kellogg & Andelson Accountancy Corp.<br>
</b><font size=1>14724 Ventura Blvd. 2nd Floor<br>
Sherman Oaks, CA 91403<br>
(818) 971-5100<br>
</font></html>
--=====================_14631672==_.ALT--
7. Re: More on Random Number Generators in Euphoria
I believe that one of the standard tests for randomness is to treat the input
file as a bit stream and measure the distance between ones and then throw
that into various statistical distributions. The unshifted, unfilled version of
the numbers is likely to produce a major peak in this set of calculations, but
it still might be instructive to see just what it does generate.
Everett L.(Rett) Williams
rett at gvtc.com
