mt19937

package module
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 13, 2020 License: GPL-3.0 Imports: 0 Imported by: 45

README

The Mersenne Twister in Go
==========================

An implementation of Takuji Nishimura's and Makoto Matsumoto's
`Mersenne Twister`_ pseudo random number generator in Go.

Copyright (C) 2013  Jochen Voss

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Please send any comments or bug reports to the program's author,
Jochen Voss <voss@seehuhn.de>.

.. _Mersenne Twister: http://en.wikipedia.org/wiki/Mersenne_twister

Overview
--------

The Mersenne Twister is a pseudo random number generator (PRNG),
developed by Takuji Nishimura and Makoto Matsumoto.  The Mersenne
Twister is, for example, commonly used in Monte Carlo simulations and
is the default random number generator for many programming languages,
e.g. Python_ and R_.  This package implements the `64bit version`_ of the
algorithm.

.. _Python: http://www.python.org/
.. _R: http://www.r-project.org/
.. _64bit version: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html


Installation
------------

This package can be installed using the ``go get`` command::

    go get github.com/seehuhn/mt19937


Usage
-----

Detailed usage instructions are available via the package's online
help, either on pkg.go.dev_ or on the command line::

    go doc github.com/seehuhn/mt19937

.. _pkg.go.dev: https://pkg.go.dev/github.com/seehuhn/mt19937

The class ``MT19937`` represents instances of the Mersenne Twister.
New instances can be allocated using the ``mt19937.New()`` function.
A seed can be set using the .Seed() or .SeedFromSlice() methods.
``MT19937`` implements the ``rand.Source`` interface from the
``math/rand`` package.  Typically the PRNG is wrapped in a rand.Rand
object as in the following example::

    rng := rand.New(mt19937.New())
    rng.Seed(time.Now().UnixNano())

Note that MT19937 is not safe for concurrent accesss by different
goroutines.  If more than one goroutine accesses the PRNG, the callers
must synchronise access using sync.Mutex or similar.


Comparison to the Go Default PRNG
---------------------------------

Go has a built-in PRNG provided by the math/rand package.  I did not
find any information about this built-in PRNG except for a comment in
the source code which says "algorithm by DP Mitchell and JA Reeds".
In contrast, the MT19737 generator provided in this package is a
well-understood random number generator.  Relevant references include
[Ni2000]_ and [MatNi1998]_.

.. [Ni2000] T. Nishimura, *Tables of 64-bit Mersenne Twisters*, ACM
     Transactions on Modeling and Computer Simulation 10, 2000, pages
     348-357.
.. [MatNi1998] M. Matsumoto and T. Nishimura, *Mersenne Twister: a
     623-dimensionally equidistributed uniform pseudorandom number
     generator*, ACM Transactions on Modeling and Computer Simulation
     8, 1998, pages 3--30.

The unit tests for the mt19937 package verify that the output of the
Go implementation coincides with the output of the reference
implementation.

The mt19937 generator is slightly slower than the Go default PRNG.
A speed comparison can be performed using the following command::

    go test -bench=. github.com/seehuhn/mt19937

On my laptop, using go version 1.15.5, I get the following results:

    +----------------+---------------+----------------+
    | method         | time per call |      thoughput |
    +================+===============+================+
    | MT19937.Uint64 |  5.63 ns/op   |   1422.14 MB/s |
    +----------------+---------------+----------------+
    | MT19937.Int63  |  5.69 ns/op   |   1405.04 MB/s |
    +----------------+---------------+----------------+
    | builtin Uint64 |  4.05 ns/op   |   1973.47 MB/s |
    +----------------+---------------+----------------+
    | builtin Int63  |  4.15 ns/op   |   1929.62 MB/s |
    +----------------+---------------+----------------+

This shows that, on my system, a call to the ``Int63()`` method of the
built-in PRNG takes about 73% of the time that MT19937.Int63() takes.

Documentation

Overview

Package mt19937 is a pure-go implementation of the 64bit Mersenne Twister pseudo random number generator (PRNG). The Mersenne Twister, developed by Takuji Nishimura and Makoto Matsumoto, is, for example, commonly used in Monte Carlo simulations. The implementation in the mt19937 package closely follows the reference implementation from

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html

and, for identical seeds, gives identical output to the reference implementation.

The PRNG from the mt19937 package implements the rand.Source interface from the math/rand package. Typically the PRNG is wrapped in a rand.Rand object as in the following example:

rng := rand.New(mt19937.New())
rng.Seed(time.Now().UnixNano())

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type MT19937

type MT19937 struct {
	// contains filtered or unexported fields
}

MT19937 is the structure to hold the state of one instance of the Mersenne Twister PRNG. New instances can be allocated using the mt19937.New() function. MT19937 implements the rand.Source interface and rand.New() from the math/rand package can be used to generate different distributions from a MT19937 PRNG.

This class is not safe for concurrent accesss by different goroutines. If more than one goroutine accesses the PRNG, the callers must synchronise access using sync.Mutex or similar.

func New

func New() *MT19937

New allocates a new instance of the 64bit Mersenne Twister. A seed can be set using the .Seed() or .SeedFromSlice() methods. If no seed is set explicitly, a default seed is used instead.

func (*MT19937) Int63

func (mt *MT19937) Int63() int64

Int63 generates a (pseudo-)random 63bit value. The output can be used as a replacement for a sequence of independent, uniformly distributed samples in the range 0, 1, ..., 2^63-1. This method is part of the rand.Source interface.

func (*MT19937) Read

func (mt *MT19937) Read(p []byte) (n int, err error)

Read fills `p` with (pseudo-)random bytes. This method implements the io.Reader interface. The returned length `n` always equals `len(p)` and `err` is always nil.

func (*MT19937) Seed

func (mt *MT19937) Seed(seed int64)

Seed uses the given 64bit value to initialise the generator state. This method is part of the rand.Source interface.

func (*MT19937) SeedFromSlice

func (mt *MT19937) SeedFromSlice(key []uint64)

SeedFromSlice uses the given slice of 64bit values to set the generator state.

func (*MT19937) Uint64

func (mt *MT19937) Uint64() uint64

Uint64 generates a (pseudo-)random 64bit value. The output can be used as a replacement for a sequence of independent, uniformly distributed samples in the range 0, 1, ..., 2^64-1. This method is part of the rand.Source64 interface.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL