News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Diehard Test Workaround?

Started by FORTRANS, January 24, 2013, 10:29:20 AM

Previous topic - Next topic

FORTRANS

Hi,

   I was looking at the Park Miller or Lehmer random number
generator and decided to modify it a bit.  It generates 31-bit
numbers which seem to poison some of the Diehard Tests.
I have a random bit routine (or use one bit from another
random number generator) that I could us to supply a zero
bit to a shifted 31-bit result to get a 32-bit value.  Do you
have an opinion on the best way to do this?

Thanks,

Steve N.

MichaelW

I can't back this up with logic ATM, but it seems to me that to avoid "polluting" the results with a bit from another generator, you should get the additional bit from a second instance of the generator being tested. 
Well Microsoft, here's another nice mess you've gotten us into.

dedndave

not sure i understand where Michael is coming from
one random bit should have little or no relation to another - that's part of being random   :biggrin:

you could OR the bit onto the dword
or, somehow use it to set/clear the carry flag, then use RCL/RCR
the BT instruction is one way to set the carry flag - another would SHL/SHR

FORTRANS

#3
Hi,

   After thinking about this this morning in the dark, I think
I will use the "leftovers" from the calculation of the random
number to supply the extra bit.  This would avoid both the
pollution that Michael spoke of, and obviates the need for a
separate generator.  A SHR EAX,1 (AL,1?) followed by a
RCL EDX,1 seems to fill the need.

   Michael, thanks for the comment, that was one of the
reasons (more or less) that I posted asking for ideas.
Dave, as shown, that was sort of the idea.  Just where
to best get a bit from was the problem.  Off to continue
the testing.

Regards,

Steve N.

Edit:

   Well, that did not help.  Neither SHR EAX, 1 or 2 workes.

SRN

dedndave

QuoteA SHR EAX,1 (AL,1?)

i think SHR EAX,1 is prefered over SHR AL,1
at least, it was in days of old
it codes as 2 bytes and is quite fast
well - the shift part is fast - dependancies on the carry flag that follow aren't as fast as they should be

MichaelW

Quote from: dedndave on January 24, 2013, 09:16:44 PM
not sure i understand where Michael is coming from
one random bit should have little or no relation to another - that's part of being random

One of the points of the statistical tests is to determine if there is a non-random relationship between the bits. I suggested getting the additional bit from a separate instance of the generator because for some generators when you skip through the generated sequence in a regular pattern, the apparent randomness of the resulting sequence can be less than that of the full sequence. But after having thought more about it, I think it would be better to just rig the generator to produce a sequence of bits, 31 per cycle, and let the tests access the bits in whatever size chunks they require.
Well Microsoft, here's another nice mess you've gotten us into.

dedndave

welllll....
i maintain that a set of tests like ENT that is written to test bytes is only valid for byte generators
some of the tests just can't be easily performed (correctly) on larger widths

if you generate 31-bit sequences, you have to test them as such
using a byte test on them is like comparing apples to oranges

FORTRANS

Hi,

   Ended up getting a bit from another random number
generator (LCG).  My random bit generator did badly
enough I might run its output through something to
see how bad it is.  The use of a leftover bit made it look
random, but Diehard flunked a few tests even when helped
by the bit generator.

   Oh well, my new generator is comperable to the munged
Park Miller.  Now I have a number of different full cycle length
generators to chose from.

Cheers,

Steve N.

jj2007

Steve,

You could submit your results to Acert. It's an interesting collection.

@Alex: There is also one that starts with MB_  :lol:

FORTRANS

Hi jj,

   Done.  Look for PMRand32.

Cheers,

Steve

jj2007

Quote from: FORTRANS on January 26, 2013, 01:47:31 AM
   Done.  Look for PMRand32.

Top quality :t

Compare to MS Excel 2007... :dazzled:

There are some great names in the "red zone" - Mersenne twister, gsl noise, php, ...

Mine has a little problem with the 6*8 Matrix but it's still grouped under "good" generators. And it seems to be the fastest among the 1000+ tested :biggrin:

FORTRANS

Hi,

   It is somewhat odd that they sort on entropy.  It would
be nice to do some kind of sort by quality.  I guess it is both
easy and understandable.  Also no code sizes.  Leaves us at
a disadvantage to not be able to crow a little.

Cheers,

Steve N.