From: orz on
I've cut & pasted your code in to my RNG experimentation code and set
it for testing using both TestU01 SmallCrush/Crush/BigCrush/Rabbit and
my own test suite (which is not yet published but should be available
on sourceforge within a week or so). Test results are not coming very
quickly though, as they expect a fair number of random bits and this
is producing them 1 at a time very slowly. I have not been very
impressed with Diehard or the NIST stuff or RaBiGeTe or ENT. I have
not tried Dieharder yet. The parameterization of MDWP that I'm
testing is the one used by default in your sample code:
mdwpobj<random_fracobj,vector5t,point5t>
Preliminary results say that MDWP output is significantly higher
quality than random_fracobj output, but that's not saying much as
random_fracobj is horrible. It passes SmallCrush; it passes Rabbit up
to 1 megabit so far; it passes my tests up to 1 GB so far (the last
may sound like a lot, but my tests are intended to be called on
multiple terrabytes for good RNGs - on faster RNGs I test 1 GB every
20 seconds or so, while on this it took 20 minutes).
If you have a different parameterization you want testing focused on
let me know, but my CPU resources are very limited so not much total
testing will get done.

Since MDWP requires an internal RNG I'd compare it to an RNG
transforming wrapper like a Bays-Durham shuffle rather than to an
RNG. In terms of practical usage I don't really see a point to this
due to its extremely low speed, but it's possible this could be of
interest from a theoretical perspective. Conceivably this could be
optimized quite a bit, but there are RNGs that pass all bias tests
that are 700+ times faster than this, and cryptographically secure
RNGs that are 400+ times faster than this, so even with optimization I
doubt it will be truly competitive in speed.

I'd suggest taking a glance at RC4 btw. It's an RNG that's at heart
about an arrangement of a fixed set of things, with their positions
within that arrangement interacting over time. So in that way it's
vaguely analogous to this, though it bears no real resemblance any
physical system.
From: Lev Dymchenko on
On Aug 11, 3:07 pm, orz <cdh...(a)gmail.com> wrote:
> I've cut & pasted your code in to my RNG experimentation code and set
> it for testing using both TestU01 SmallCrush/Crush/BigCrush/Rabbit and
> my own test suite (which is not yet published but should be available
> on sourceforge within a week or so).  Test results are not coming very
> quickly though, as they expect a fair number of random bits and this
> is producing them 1 at a time very slowly.  I have not been very
> impressed with Diehard or the NIST stuff or RaBiGeTe or ENT.  I have
> not tried Dieharder yet.  The parameterization of MDWP that I'm
> testing is the one used by default in your sample code:
> mdwpobj<random_fracobj,vector5t,point5t>
> Preliminary results say that MDWP output is significantly higher
> quality than random_fracobj output, but that's not saying much as
> random_fracobj is horrible.  It passes SmallCrush; it passes Rabbit up
> to 1 megabit so far; it passes my tests up to 1 GB so far (the last
> may sound like a lot, but my tests are intended to be called on
> multiple terrabytes for good RNGs - on faster RNGs I test 1 GB every
> 20 seconds or so, while on this it took 20 minutes).
> If you have a different parameterization you want testing focused on
> let me know, but my CPU resources are very limited so not much total
> testing will get done.
>
> Since MDWP requires an internal RNG I'd compare it to an RNG
> transforming wrapper like a Bays-Durham shuffle rather than to an
> RNG.  In terms of practical usage I don't really see a point to this
> due to its extremely low speed, but it's possible this could be of
> interest from a theoretical perspective.  Conceivably this could be
> optimized quite a bit, but there are RNGs that pass all bias tests
> that are 700+ times faster than this, and cryptographically secure
> RNGs that are 400+ times faster than this, so even with optimization I
> doubt it will be truly competitive in speed.
>
> I'd suggest taking a glance at RC4 btw.  It's an RNG that's at heart
> about an arrangement of a fixed set of things, with their positions
> within that arrangement interacting over time.  So in that way it's
> vaguely analogous to this, though it bears no real resemblance any
> physical system.

Thanks. Lets see results. Yes, it is a bit slow, however, MDWP rng can
have very big rand seed or encryption key with same performance. Even
megabytes. Do you know other RNG with such big rand seed? Performance
of the reference code is also dependent of compiler. I hope compiler
could deal with templates effectively. It uses about 200-500 clocks on
one bit on my system.
From: Mok-Kong Shen on
Lev Dymchenko wrote:

> I believe Joseph talks about analysis of sub sequences of bits, each
> sub sequence is formed by one particle.

I am interested to learn some details of the theory and practice of that
analysis technique when applied to attack PRNGs in general.

M. K. Shen


From: Cristiano on
Lev Dymchenko wrote:
> What sequence size do you suggest?

I usually do: 1, 8, 16, 32, ... MBits up to 128 MBits for the last answer.
I use 50 sequences.

I wrote a multi-threaded version (still in beta) of RaBiGeTe for Windows
which include the GUI (written with wxWidgets). If you are interested in
that version, let me know.

Cristiano


From: Mok-Kong Shen on

BTW, in case you are interested to compare your design with others,
there is a PRNG by G. Marsaglia named Super KISS, which is claimed to
have very large period and good statistical qualities. (You could
Google to find it. I personally have unfortunately no knowldege of it.)

M. K. Shen