Are Maple's pseudo random number generators good generators?

Ask a Question

Create a Post

All Posts : MaplePrimes Commons General Technical Discussions

Are Maple's pseudo random number generators good generators?

Posted: mmcdara 6563

December 04 2019

I'm particularly interested in data analysis and more specifically in statistical analysis of computer code outputs.

One of the main activity of this very broad field is named Uncertainty Propagation. In a few words it consists in perturbing the inputs of a computational code in order to understand (and quantify) how these perturbations propagates through the outputs of this code.

At the core of uncertainty propagation is the ability to generate large numbers of "random" variations of the inputs. Knowing that these entries can be counted in tens, one sees that the first problem consists in generating "random" points in a space of potentially very large dimension.

Even among my mathematician colleagues an impressive number of them is completely ignorant of the way "random" numbers are generated. I guess that a lot of Mapleprimes' users are too. My purpose is not to give a course on this topic and the affording litterature is vast enough for everyone interested might find informations of any level of complexity.
Among those who have some knowledge about Pseudo Random Numbers Generators (PRNG), only a few of them know that a PRNG has to pass severe tests ("tests of randomness") before the streams of number it generates might be qualified as "reasonably random" and therefore this PRNG might be released.

One of most famous example of a bad PRNG is given by "randu" (IBM 1966, and probably used in Fortran libraries during more than 30 years), this same PRNG that Knuth qualified himself as the "infamous generator".

These tests of randomness are generally gathered in dedicated libraries and Diehard is probably tone of the most known of them.
Diehard has originally been developed by George Marsaglia more than twenty years ago and it's still widely ued today.

I recently decided, not because I have doubts about the quality of the work done by Maplesoft, to test the Maple's PRNG named "Mersenne Twister". First, because it can do no harm to publish quantitative information that allows everyone to know that it is using a proven PRNG; second, because the (very simple) approach used here can fill the gaps I have mentioned above.

Mersenne Twister (often dubbed mt19937) is considered as a very good PRNG; it is used in a lot of applications (including finance where it is not so rare to sample input spaces of dimensions larger than 1000... ok I know, mt19937 is often considered as a poor candidate for cryptography applications, but it's not my concern here).

I have thus decided to spend some time to run the Diehard suite of tests on a sequence of integers numbers generated by RandomTools[MersenneTwister].

restart:

DIEHARD tests suite for Pseudo Random Numbers Generators (PRNG)

Reference: http://webhome.phy.duke.edu/~rgb/General/dieharder.php

The installation procedure (Mac OSX) can be found here
    https://gist.github.com/blixt/9abfafdd0ada0f4f6f26
or here
    http://macappstore.org/dieharder/

For other operating systems, please search on the web pages.

dieharder [-h]   # for inline help
dieharder -l      # to get the lists all the avaliable tests

A description of the many tests can be found here:
    https://en.wikipedia.org/wiki/Diehard_tests
    https://sites.google.com/site/astudyofentropy/background-information/the-tests/dieharder-test-descriptions
    https://www.stata.com/support/cert/diehard/randnumb_mt64.out

General theory about PRNG testing can be found here (a reference among many):
    http://liu.diva-portal.org/smash/get/diva2:740158/FULLTEXT01.pdf

or here (more oriented to the NIST test suite)
    https://www.random.org/analysis/Analysis2005.pdf
    https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf

In a terminal window execute the following commands for an exhaustive testing ("-a" option).
The "-g 202" option means that the generator is replaced by a text format input file
(use dieharder -h for more details).

cd //..../Desktop/DIEHARD

dieharder -g 202 -f SomeAsciiFile -a > //..../Desktop/DIEHARD/TheResultFile.txt

Be carefull, the complete testing takes several hours (about 5 on my computer)

__________________________________________________________________________________

Maple's Mersenne Twister Generator

Maple help page : RandomTools[MersenneTwister][GenerateInteger]
(see rincluded references to the Mersenne Twister PRNG).

Note: in the sequel this generator will be dubbed mt19937

The Mersenne Twister is implemented in many softwares.
It is higly likely that this PRNG (and the others these softwares propose) have been intensively
tested with one of the existing PRNG testing libraries.
Unfortunately only a few editors have made public the results of these tests (probably because
the implementation in itself is rarely questioned... but a code typo is always a possibility).

One exception is ths software STATA.
A summary of the results can be found here
https://www.stata.com/support/cert/diehard/.
A complete description of the results of the tests passed is given here
https://www.stata.com/support/cert/diehard/randnumb_mt64.out

The classical pattern of the performances of mt19937 can be found here

http://www2.ic.uff.br/~celso/artigos/pjo6.ps.

and the table below comes from it (P means "Passed", F means "Failed"):

____________________________________________________________________________

In the Maple code below, a sequence of N UnsignedInt32 numbers is generated from the
Maple's Mersenne Twister and the result is exported in an ASCII file.
The Seed is set to 1 (SetState(state=1)) to compare, with a small value of N (let's say N=10)
the sequence produced by Maple's mt19937 with the the sequence of the same length generated
by Diehard's mt19937.
To generate this later sequence and save it in file Diehard_mt19937, just run in a terminan window
the command (-S 1 means "seed = 1", -t 10 means "a sequence of length 10"):
dieharder -S 1 -B -o -t 10 > Diehard_mt19937

About the value of N:

In http://webhome.phy.duke.edu/~rgb/General/dieharder.php it's recommend that N be at least
equal to 2.5 million; STATA used N=3 million.
Other web sources say this value is too small.
For N=10 million the Maple's mt19937 doesn't pass the tests successfully.
I used here N=50 million (the resulting ASCII file has size 537 Mo).

Name of the input file.

The file generated by Maple is named Maple_mt19937_N=5e7.txt

One important thing is the preamble of a licit input file.

This preamble must have 6 lines (the value 10 right to count must be set to the value of N).
A licit preamble is of the form.

#==================================================================

# some text indicating the generator used

#==================================================================

type: d

count: 10

numbit: 32

As Maple_mt19937_N=5e7.txt is generated from an ExportMatrix command, this preamble is added
by hand.

Running multiple Diehard tests

To run the same tests used to qualify STATA's Mersenne Twister, open a terminal window,
go to the directory that contains input file Maple_mt19937_N=5e7.txt and run this script:

for i in {0,1,2,3,4,8,9,10,11,12,13,14,15,16}; do

dieharder -g 202 -f Maple_mt19937_N=5e7.txt -d $i >> Diehard___Maple_mt19937_N=5e7

done ;

The results are then forked in the ASCII file Diehard___Maple_mt19937_N=5e7

>	with(RandomTools[MersenneTwister]):

>	dir := cat("/", currentdir(), "Desktop/DIEHARD/"): InputFile := cat(dir, "Maple_mt19937_N=5e7.txt"):

>	SetState(state=1); N := 5*10^7: st := time(): S := convert([seq(GenerateUnsignedInt32(), i=1..N)], Matrix)^+; time()-st;

$S := Vector(4, {(1) = ` 50000000 x 1 `*Matrix, (2) = `Data Type: `*anything, (3) = `Storage: `*rectangular, (4) = `Order: `*Fortran_order})$

(1)

>	st := time(): ExportMatrix(InputFile, S, format=rectangular, mode=ascii); time()-st;

(2)

Diehard's results

Full test suite (about 5 hours of computational time)

Command :
dieharder -g 202 -f Maple_mt19937_N=5e7.txt -a > Diehard___ALL___Maple_mt19937_N=5e7

The results are compared to those obtained for Diehard's mt19937.
Two ways are used :

  - 1 - In a first stage one generates a stream of PRN and store it in an ASCII file (just as we did with Maple).
         The whole suite of tests is then run on this file.
         Commands (-g 013 codes for mt19937):

         dieharder -S 1 -g 013 -o -t 50000000 > Diehard_mt19937_N=5e7.txt
         dieharder -g 202 -f Diehard_mt19937_N=5e7.txt -a > Diehard___ALL___Diehard_mt19937_N=5e7

  - 2 - The whole suite is run by invoking directectly mt19937 "online"
         Commands :
         dieharder -S 1 -g 013 -t 50000000 -a > Diehard___ALL___Online

A UNIX diff command has been used to verify that the two files Maple_mt19937_N=5e7.txt and
Diehard_mt19937_N=5e7.txt were identical (thet were).

Note that the Diehard doens't responds identically depending on the stream of random numbers comes from a file
or is generated online (this last [- 2 -] situation seems to give better results).-

Résumé (114 tests):
   - * - Maple's and Diehard's mt19937 respond exactly the same way when the stream of random
          numbers is read from an ASCII file (8 tests failed (******) and 6 weak (**)).
   - * - Diehard's mt19937 fails 0 test and is weak on 4 tests when the stream is generated online

restart:

dir := currentdir():
FromMapleFile     := cat(dir, "Diehard___ALL___Maple_mt19937_N=5e7"):
FromDiehardFile   := cat(dir, "Diehard___ALL___diehard_mt19937_N=5e7"):
FromDiehardNoFile := cat(dir, "Diehard___ALL___Online"):

printf("                           ======================|======================|======================|\n"):
printf("                          |   From Maple's file | From Diehard's File | Diehard online test |\n"):
printf("==========================|======================|======================|======================|\n"):
printf("          test       ntup | p.value   Assessment | p.value   Assessment | p.value   Assessment |\n"):
printf("==========================|======================|======================|======================|\n"):

for k from 1 to 9 do
  LMF := readline(FromMapleFile):
  LDF := readline(FromDiehardFile):
  LDNF := readline(FromDiehardNoFile):
end do:

while LMF <> 0 do
  if StringTools:-Search("|", LMF) > 0 then
    res := StringTools:-StringSplit(LMF, "|")[[1, 2, 5, 6]];
    printf("%-20s %3d | %1.7f ", res[1], parse(res[2]), parse(res[3]));
      if StringTools:-Search("WEAK" , res[4]) > 0 then printf("    **     |")
    elif StringTools:-Search("FAILED", res[4]) > 0 then printf(" ******   |")
    else printf(" PASSED   |")
    end if:
  end if:
  LMF := readline(FromMapleFile):

  if StringTools:-Search("|", LDF) > 0 then
    res := StringTools:-StringSplit(LDF, "|")[[5, 6]];
    printf(" %1.7f ", parse(res[1]));
      if StringTools:-Search(" WEAK" , res[2]) > 0 then printf("     **    |")
    elif StringTools:-Search(" FAILED", res[2]) > 0 then printf("   ****** |")
    else printf("   PASSED |")
    end if:
  end if:
  LDF := readline(FromDiehardFile):

  if StringTools:-Search("|", LDNF) > 0 then
    res := StringTools:-StringSplit(LDNF, "|")[[5, 6]];
    printf(" %1.7f ", parse(res[1]));
      if StringTools:-Search("WEAK" , res[2]) > 0 then printf("     **    |")
    elif StringTools:-Search("FAILED", res[2]) > 0 then printf("   ******    |")
    else printf("   PASSED |")
    end if:
    printf("\n"):
  end if:
  LDNF := readline(FromDiehardNoFile):

end do:

Download DIEHARD_test_of_MAPLE_MersenneTwister.mw

A lot of supplementary details are given in the attached file.
I let the readers discover by themselves if Maple's implementation of the Mersenne Twister PRNG is correct or not.
Beyond this exercise, I hope this work will be useful to people who could be tempted to test their own generator.

316 views
More...

Contact Author

Subscribe

Generate PDF

Comment

Share

Branch

Create a new Post in reply

Ask a related Question

Flag

Add a Comment

Share via:

E-Mail Address:
Password:
Remember Me:	Automatically sign in on future visits

E-Mail Address:
Password:
Remember Me:	Automatically sign in on future visits

Ask a Question

Create a Post

Are Maple's pseudo random number generators good generators?

316 views
More...

Contact Author

Subscribe

Generate PDF

Comment

Share

Branch

Create a new Post in reply

Ask a related Question

Flag

Preview

Preview

Save this setting as your default sorting preference?

Ask a Question

Create a Post

Generating PDF…

Save this setting as your default sorting preference?
Note: You can change your preference any time in your account settings
Don't show this again

From:
To:

Custom Message (optional):

Ask a Question

Create a Post

Are Maple's pseudo random number generators good generators?

316 views More... Contact Author Subscribe Generate PDF Comment Share Branch Create a new Post in reply Ask a related Question Flag

Preview

Preview

Save this setting as your default sorting preference?

Ask a Question

Create a Post

Generating PDF…

316 views
More...

Contact Author

Subscribe

Generate PDF

Comment

Share

Branch

Create a new Post in reply

Ask a related Question

Flag