Randomness tests

Randomness tests

[Gautier write-only]

Does someone have some randomness checking sources in Ada ?
I am evaluating a fast random generator (published long time ago in
the Ada letters), alternative to GNAT's implementation.
Probably the most obvious test is to check that it is well uniformly
distributed.
_________________________________________________________
Gautier's Ada programming -- http://sf.net/users/gdemont/
NB: For a direct answer, e-mail address on the Web site!

Re: Randomness tests

[Jeffrey R. Carter]

Gautier write-only wrote:
> Does someone have some randomness checking sources in Ada ?
> I am evaluating a fast random generator (published long time ago in
> the Ada letters), alternative to GNAT's implementation.
> Probably the most obvious test is to check that it is well uniformly
> distributed.

An interesting test is the "parking-lot" test. Consecutive pairs of numbers from 
the generator are treated as (x, y) pairs of coordinates and plotted on a graph. 
Poor generators create line segments; good ones don't. (The test gets its name 
from the 1st generator it was applied to, which created short, parallel, 
diagonal line segments that reminded people of the lines in a parking lot.) 
Apparently even generators that do well on other tests can fail this one. The 
generator in Turbo Pascal did especially poorly on this test.

I know of one application in which consecutive triples of numbers were treated 
as (x, y, z) 3-D coordinates. A generator which did well on other tests, 
including the 2-D parking lot test, failed the 3-D version.

Also note that the PragmAda reusable components include the "universal" random 
number generator, which is supposed to be a very good generator, is portable, 
and gives identical results on all platforms.

-- 
Jeff Carter
"Sheriff murdered, crops burned, stores looted,
people stampeded, and cattle raped."
Blazing Saddles
35

Re: Randomness tests

[Gautier write-only]

Jeffrey R. Carter:

Thanks for the explanations about the "parking-lot" method.

> Also note that the PragmAda reusable components include the "universal" random
> number generator, which is supposed to be a very good generator, is portable,
> and gives identical results on all platforms.

I was precisely considering that algorithm (the famous u_rand).

Gautier

Re: Randomness tests

[AdaMagica]

Do you mean Marsaglias_Generator:

The algorithm was developed by George Marsaglia,
Supercomputer Computations Research Institute,
Florida State University
(ref. to Ada LETTERS, Volume VIII, Number2, March/April 1988).

I have an implementation of it. It produces the results required for a
correct implementation.

Re: Randomness tests

[Nicholas Paul Collin Gloucester]

On 2009-07-16, Gautier write-only <gautier_niouzes@hotmail.com> wrote:

|--------------------------------------------------------------------|
|"Does someone have some randomness checking sources in Ada ?        |
|I am evaluating a fast random generator (published long time ago in |
|the Ada letters), alternative to GNAT's implementation.             |
|Probably the most obvious test is to check that it is well uniformly|
|distributed."                                                       |
|--------------------------------------------------------------------|

Please let us know your conclusions.

With kind regards,
N. P. C.

Re: Randomness tests

[Peter Hermann]

Christoph, Gautier,

did you look at the open source
GNAT:ada.numerics.[float][discrete]_random ?

Re: Randomness tests

[AdaMagica]

On 17 Jul., 13:51, Peter Hermann <s...@spam.de> wrote:
> Christoph, Gautier,
>
> did you look at the open source
> GNAT:ada.numerics.[float][discrete]_random ?

Of course I know and use those. I just wanted to know which Ada
Letters random generator Gautier wanted to test.

Re: Randomness tests

[Gautier write-only]

Nicholas Paul Collin Gloucester:

> Please let us know your conclusions.

So - the mentioned package is indeed the "universal" random generator
from Dr. George Marsaglia, which seems to have appeared in the Ada
letters in 1988, which circulates under the name U_Rand.
According to the machine and compiler, I get a speedup from 5x to 6.8x
(net of overhead).
No more advanced tests yet...
There are a couple of others generators I've to try, e.g. the Mersenne
Twister:
http://adrianhoe.com/adrianhoe/projects/adamt19937/
or a very simple one from Peter:
http://groups.google.ch/group/comp.lang.ada/msg/cf300f84f8782702

I've just "repimped" U_Rand with generics, no more global variables
but a type Generator, and some Ada 95 A.N.Float_Random-style
"renames", which facilitates the switch between random packages, like
in this example:

  -- *** Choice of the floating-point type used for the whole
Portfolio Model:
  subtype Real is Long_Float;

  package Real_U_Rand is new U_Rand(Real);

  -- *** Choice of a random generator: A.N.F_R, or U_Rand (faster),
or...:
  package RRand renames
    -- Ada.Numerics.Float_Random;
    Real_U_Rand;

The funny thing is that RRand can be plugged in its turn into another
generic package

  package GRA is new Ada.Numerics.Generic_Real_Arrays(Real);

  package RCopulas is new Copulas(
    Real,
    RRand.Uniformly_Distributed, RRand.Generator, RRand.Random,
    GRA
  );

In case someone is interested, mail me.
Anytime soon I'll open a SourceForge project with various random
variable goodies.
_________________________________________________________
Gautier's Ada programming -- http://sf.net/users/gdemont/
NB: For a direct answer, e-mail address on the Web site!

Re: Randomness tests

[jonathan]

On Jul 16, 8:41 pm, Gautier write-only <gautier_niou...@hotmail.com>
wrote:
> Does someone have some randomness checking sources in Ada ?
> I am evaluating a fast random generator (published long time ago in
> the Ada letters), alternative to GNAT's implementation.
> Probably the most obvious test is to check that it is well uniformly
> distributed.
> _________________________________________________________
> Gautier's Ada programming --http://sf.net/users/gdemont/
> NB: For a direct answer, e-mail address on the Web site!

You can find several basic tests at

http://web.am.qub.ac.uk/users/j.parker/miscellany

 in the subdirectory: disorderly

see for example:

  gcd_4bytes_1.adb
  gcd_6bytes_1.adb
  rank_tst_2.adb
  bday_tst_1.adb
  gorilla_tst_demo_2.adb


(To use gcd_6bytes_1.adb, concatenate 2 of the
24 bit words generated by Marsaglia's Universal
generator.)

The greatest-common-divisor test, gcd_6bytes_1.adb
and gorilla tests are from the Marsaglia,
Tsang updated diehard suite. To find their paper
google for

"Some difficult-to-pass tests of
randomness", Marsaglia, Tsang.

The birthday test is a variant of
Marsaglia's birthday test. I include
the birthday test (bday_tst_1.adb) because the
present GNAT generator fails this. (It has to.
All short period generators fail this test.)

I include Marsaglia's rank test (rank_tst_2.adb)
because it easily breaks the Mersenne Twister.
(It has to. The Mersenne Twister is full-period
and linear; they all fail this test catastrophically.)
I would still prefer the Mersenne Twister over
the Marsaglia Universal generator though .. it
does quite a bit more bit-mixing between outputs
than the Marsaglia Universal generator.

The site given above contains my own version of
the way I think Random Number Generators ought
to be done:  disorderly.ads. Generator Disorderly
is really just a non-linear 61-bit version
of Marsaglia's KISS generator. KISS appeared
about a decade after his Universal generator.
The KISS generator is a combination generator
that uses linear component generators.
Disorderly includes a non-linear
component generator: X_{n+1} = X_n**2 mod M.
The X_{n+1} = X_n**2 mod M component in Disorderly
was inspired by GNAT's generator. The GNAT
generator is a combination generator made from
2 of these non-linear component generators.
(If you use just the least significant bit of
each word output by the GNAT generator, then
its called the Blum-Blum-Schub generator.)

A fast linear version of Disorderly is included;
seemed to be about 3 times faster than the GNAT
generator .. produces 61 bits per call.

Here is the start of the README:

1. directory Disorderly contains

  a package of new Random Number Generators (package
  Disorderly.Random) along with some test/demo
  routines.

  a package of Random Deviates (package
  Disorderly.Random.Deviates) with the following distributions:

    Uniform, Normal (Gaussian), Exponential, Lorentzian (Cauchy),
    Poissonian, Binomial, Negative Binomial, Weibull, Rayleigh,
    Student_t, Beta, Gamma, Chi_Squared, Log_Normal,
    Multivariate_Normal.

   procedure Deviates_Demo_1 tests
     and demonstrates usage of random deviates (variates).
     The procedure tests package Disorderly.Random.Deviates.

   procedure Basic_Deviates_Demo_1 tests
     and demonstrates usage of random deviates:
     Disorderly.Basic_Rand.Deviates.
     Uses Disorderly.Basic_Rand.
     and demonstrates usage of random deviates (variates).

Jonathan