Skip to content

Random number generation library for Nim

License

Notifications You must be signed in to change notification settings

oprypin/nim-random

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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: 219937 - 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: 2128 - 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: 21024 - 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.



Credits

This library was made by Oleh Prypin.

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

Thanks to: