# nim-random

Random number generation library for Nim inspired by Python's "random" module

## Contents

## Example

```
import algorithm, sequtils
import random, random.xorshift
var a = toSeq(1..10)
echo a[randomInt(a.len)]
# Possible output: 9
echo a.randomChoice()
# Possible output: 3
a.shuffle()
echo a
# Possible output: @[4, 8, 2, 10, 9, 3, 1, 5, 6, 7]
a.sort(cmp[int])
if randomBool():
echo "heads"
else:
echo "tails"
# Possible output: heads
var rng = initXorshift128Plus(1337)
echo rng.randomInt(13..37)
# Reproducible output: 27
echo toSeq(rng.randomSample(a, 3))
# Reproducible output: @[9, 10, 5]
var rng2 = initMersenneTwister(urandom(2500))
echo rng2.random()
# Possible output: 0.6097267717528587
```

## Manual

### Common Operations

The following procedures work for every random number generator (`import random.*`

). The first argument is skipped here; it is always `var RNG`

, so you would write, for example, `rng.shuffle(arr)`

.

You can also do `import random`

and get access to these exact procedures without the first argument. They use a global instance of Mersenne twister, which is seeded using an array of bytes provided by `urandom`

, or, in case of failure, the current time. Due to this silent fallback and the fact that any other code can use this global instance (and there is no thread safety), it is not recommended to do this if you have any concerns for security.

#### Random Integers

`proc randomInt(T: typedesc[SomeInteger]): T`

Returns a uniformly distributed random integer `T.low ≤ x ≤ T.high`

`proc randomInt(max: Positive): Natural`

Returns a uniformly distributed random integer `0 ≤ x < max`

`proc randomInt(min, max: int): int`

Returns a uniformly distributed random integer `min ≤ x < max`

`proc randomInt(interval: Slice[int]): int`

Returns a uniformly distributed random integer `interval.a ≤ x ≤ interval.b`

`proc randomBool(): bool`

Returns a random boolean

#### Random Reals

`proc random(): float64`

Returns a uniformly distributed random number `0 ≤ x < 1`

`proc random(max: float): float`

Returns a uniformly distributed random number `0 ≤ x < max`

`proc random(min, max: float): float`

Returns a uniformly distributed random number `min ≤ x < max`

`proc randomPrecise(): float64`

Returns a uniformly distributed random number `0 ≤ x ≤ 1`

,
with more resolution (doesn't skip values).

Based on http://mumble.net/~campbell/2014/04/28/uniform-random-float

#### Sequence Operations

`proc randomChoice(arr: RAContainer): auto`

Selects a random element (all of them have an equal chance) from a random access container and returns it

`proc shuffle(arr: var RAContainer)`

Randomly shuffles elements of a random access container.

`iterator randomSample(interval: Slice[int]; n: Natural): int`

Yields `n`

random integers `interval.a ≤ x ≤ interval.b`

in random order.
Each number has an equal chance to be picked and can be picked only once.

Raises `ValueError`

if there are less than `n`

items in `interval`

.

`iterator randomSample(arr: RAContainer; n: Natural): auto`

Yields `n`

items randomly picked from a random access container `arr`

,
in random order. Each item has an equal chance to be picked
and can be picked only once. Duplicate items are allowed in `arr`

,
and they will not be treated in any special way.

Raises `ValueError`

if there are less than `n`

items in `arr`

.

`proc randomSample[T](iter: iterator(): T; n: Natural): seq[T]`

Random sample using reservoir sampling algorithm.

Returns a sequence of `n`

items randomly picked from an iterator `iter`

,
in no particular order. Each item has an equal chance to be picked and can
be picked only once. Repeating items are allowed in `iter`

, and they will
not be treated in any special way.

Raises `ValueError`

if there are less than `n`

items in `iter`

.

### Type Glossary

`RNG`

Random number generator typeclass. See custom RNGs.

`typedesc[SomeInteger]`

Pass any integer type as an argument.

`Positive`

, `Natural`

`int > 0`

, `int ≥ 0`

`Slice[int]`

`a..b`

`RAContainer`

Random access container concept. Should support `len`

, `low`

, `high`

, `[]`

. Examples: `array`

, `seq`

.

### Random Number Generators

Pseudo random number generators are objects that have some state associated with them. You can create as many independent RNG objects as you like. If you use the same seed, you will always get the same sequence of numbers.

If you need to generate important things such as passwords, use *random.urandom* or `SystemRandom`

, but for typical usage it is much better to only use `urandom`

to seed a pseudo-random number generator, as shown at the bottom of the example.

None of the operations are thread-safe, so if you want to use random number generation in multiple threads, just make a different RNG object in each thread.

*random.urandom*

`proc urandom(size: Natural): seq[uint8]`

Returns a `seq`

of random integers `0 ≤ n < 256`

provided by
the operating system's cryptographic source

POSIX: Reads and returns `size`

bytes from the file `/dev/urandom`

.

Windows: Returns `size`

bytes obtained by calling `CryptGenRandom`

.
Initialization is done before the first call with
`CryptAcquireContext(..., PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)`

.

Raises `OSError`

on failure.

##### type SystemRandom

Random number generator based on bytes provided by
the operating system's cryptographic source (see `urandom`

)

- Period: none
- State: none (but bytes are obtained in 128-byte chunks)

`proc initSystemRandom(): SystemRandom`

Initializes and returns a new `SystemRandom`

*random.mersenne*

##### type MersenneTwister

Mersenne Twister (MT19937). Based on http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html

- Period: 2
^{19937}- 1 - State: 2496 bytes + int

`proc initMersenneTwister(seed: openArray[uint32]): MersenneTwister`

Seeds a new `MersenneTwister`

with an array of `uint32`

`proc initMersenneTwister(seed: openArray[uint8]): MersenneTwister`

Seeds a new `MersenneTwister`

with an array of bytes

`proc initMersenneTwister(seed: uint32): MersenneTwister`

Seeds a new `MersenneTwister`

with an `uint32`

*random.xorshift*

##### type Xorshift128Plus

xorshift128+. Based on http://xorshift.di.unimi.it/

- Period: 2
^{128}- 1 - State: 16 bytes

`proc initXorshift128Plus(seed: array[2, uint64]): Xorshift128Plus`

Seeds a new `Xorshift128Plus`

with 2 `uint64`

.

Raises `ValueError`

if the seed consists of only zeros.

`proc initXorshift128Plus(seed: array[16, uint8]): Xorshift128Plus`

Seeds a new `Xorshift128Plus`

with an array of 16 bytes.

Raises `ValueError`

if the seed consists of only zeros.

`proc initXorshift128Plus(seed: uint64): Xorshift128Plus`

Seeds a new `Xorshift128Plus`

with an `uint64`

.

Raises `ValueError`

if the seed consists of only zeros.

##### type Xorshift1024Star

xorshift1024*. Based on http://xorshift.di.unimi.it/

- Period: 2
^{1024}- 1 - State: 128 bytes + int

`proc initXorshift1024Star(seed: array[16, uint64]): Xorshift1024Star`

Seeds a new `Xorshift1024Star`

with 16 `uint64`

.

Raises `ValueError`

if the seed consists of only zeros.

`proc initXorshift1024Star(seed: array[128, uint8]): Xorshift1024Star`

Seeds a new `Xorshift1024Star`

with an array of 128 bytes.

Raises `ValueError`

if the seed consists of only zeros.

`proc initXorshift1024Star(seed: uint64): Xorshift1024Star`

Seeds a new `Xorshift1024Star`

using an `uint64`

.

Raises `ValueError`

if the seed consists of only zeros.

### Custom RNGs

The typeclass `RNG`

requires any of:

`rng.randomUint8() is uint8`

`rng.randomUint32() is uint32`

`rng.randomUint64() is uint64`

So all you need to make another random number generator compatible with this library is to implement one of these procs, for example:

`proc randomUint32*(self: var MersenneTwister): uint32 =`

This should return a uniformly distributed random number.

You may also override any of the common operations for your RNG; `random()`

would be the first candidate for this.

Other than this, you should make `init...`

procs to create and seed your RNG. It is important to be able to seed with an array of bytes, for convenience of use with `urandom`

. Look in the source code to see how *random/private/util*.`bytesToWords`

and `bytesToWordsN`

are used to quickly create byte-array seeding based on some other seeding proc.

Don't forget to import+export *random.common*.

## Generated Documentation

## Credits

This library was made by Oleh Prypin.

It was inspired by Python's random library and takes some ideas from it.

Thanks to:

- Varriount for helping wrap
`CryptGenRandom`

- flaviut for chi-square testing, CircleCI example, various comments and pointers
- Jehan for random sample testing, various comments and pointers
- Niklas B. for fast implementation of log2 (
`bitSize`

) - OderWat for reservoir sampling
- Araq, def-, and the rest of the Nim community for answering numerous questions
- Takuji Nishimura and Makoto Matsumoto for MT19937
- Sebastiano Vigna for Xorshift...
- Taylor R. Campbell for
`random_real`