From f5c4671bfbad96bf346bd7e9a21fc4317b4959df Mon Sep 17 00:00:00 2001 From: Indrajith K L Date: Sat, 3 Dec 2022 17:00:20 +0530 Subject: Adds most of the tools --- v_windows/v/vlib/rand/README.md | 87 +++++ v_windows/v/vlib/rand/config/config.v | 13 + v_windows/v/vlib/rand/constants/constants.v | 12 + v_windows/v/vlib/rand/dist/README.md | 10 + v_windows/v/vlib/rand/dist/dist.v | 85 +++++ v_windows/v/vlib/rand/dist/dist_test.v | 134 ++++++++ v_windows/v/vlib/rand/mt19937/mt19937.v | 325 +++++++++++++++++++ v_windows/v/vlib/rand/mt19937/mt19937_test.v | 341 ++++++++++++++++++++ v_windows/v/vlib/rand/musl/musl_rng.v | 241 ++++++++++++++ v_windows/v/vlib/rand/musl/musl_rng_test.v | 331 +++++++++++++++++++ v_windows/v/vlib/rand/pcg32/pcg32.v | 226 +++++++++++++ v_windows/v/vlib/rand/pcg32/pcg32_test.v | 337 ++++++++++++++++++++ v_windows/v/vlib/rand/rand.c.v | 127 ++++++++ v_windows/v/vlib/rand/rand.v | 183 +++++++++++ v_windows/v/vlib/rand/random_identifiers_test.v | 70 ++++ v_windows/v/vlib/rand/random_numbers_test.v | 319 +++++++++++++++++++ v_windows/v/vlib/rand/seed/seed.v | 40 +++ v_windows/v/vlib/rand/splitmix64/splitmix64.v | 225 +++++++++++++ v_windows/v/vlib/rand/splitmix64/splitmix64_test.v | 331 +++++++++++++++++++ v_windows/v/vlib/rand/sys/system_rng.c.v | 275 ++++++++++++++++ v_windows/v/vlib/rand/sys/system_rng.js.v | 15 + v_windows/v/vlib/rand/sys/system_rng_test.v | 354 +++++++++++++++++++++ v_windows/v/vlib/rand/util/util.v | 52 +++ v_windows/v/vlib/rand/util/util_test.v | 57 ++++ v_windows/v/vlib/rand/wyrand/wyrand.v | 252 +++++++++++++++ v_windows/v/vlib/rand/wyrand/wyrand_test.v | 331 +++++++++++++++++++ 26 files changed, 4773 insertions(+) create mode 100644 v_windows/v/vlib/rand/README.md create mode 100644 v_windows/v/vlib/rand/config/config.v create mode 100644 v_windows/v/vlib/rand/constants/constants.v create mode 100644 v_windows/v/vlib/rand/dist/README.md create mode 100644 v_windows/v/vlib/rand/dist/dist.v create mode 100644 v_windows/v/vlib/rand/dist/dist_test.v create mode 100644 v_windows/v/vlib/rand/mt19937/mt19937.v create mode 100644 v_windows/v/vlib/rand/mt19937/mt19937_test.v create mode 100644 v_windows/v/vlib/rand/musl/musl_rng.v create mode 100644 v_windows/v/vlib/rand/musl/musl_rng_test.v create mode 100644 v_windows/v/vlib/rand/pcg32/pcg32.v create mode 100644 v_windows/v/vlib/rand/pcg32/pcg32_test.v create mode 100644 v_windows/v/vlib/rand/rand.c.v create mode 100644 v_windows/v/vlib/rand/rand.v create mode 100644 v_windows/v/vlib/rand/random_identifiers_test.v create mode 100644 v_windows/v/vlib/rand/random_numbers_test.v create mode 100644 v_windows/v/vlib/rand/seed/seed.v create mode 100644 v_windows/v/vlib/rand/splitmix64/splitmix64.v create mode 100644 v_windows/v/vlib/rand/splitmix64/splitmix64_test.v create mode 100644 v_windows/v/vlib/rand/sys/system_rng.c.v create mode 100644 v_windows/v/vlib/rand/sys/system_rng.js.v create mode 100644 v_windows/v/vlib/rand/sys/system_rng_test.v create mode 100644 v_windows/v/vlib/rand/util/util.v create mode 100644 v_windows/v/vlib/rand/util/util_test.v create mode 100644 v_windows/v/vlib/rand/wyrand/wyrand.v create mode 100644 v_windows/v/vlib/rand/wyrand/wyrand_test.v (limited to 'v_windows/v/vlib/rand') diff --git a/v_windows/v/vlib/rand/README.md b/v_windows/v/vlib/rand/README.md new file mode 100644 index 0000000..b5b917f --- /dev/null +++ b/v_windows/v/vlib/rand/README.md @@ -0,0 +1,87 @@ +# Quickstart + +The V `rand` module provides two main ways in which users can generate pseudorandom numbers: + +1. Through top-level functions in the `rand` module. + - `import rand` - Import the `rand` module. + - `rand.seed(seed_data)` to seed (optional). + - Use `rand.int()`, `rand.u32n(max)`, etc. +2. Through a generator of choice. The PRNGs are included in their respective submodules. + - `import rand.pcg32` - Import the module of the PRNG required. + - `mut rng := pcg32.PCG32RNG{}` - Initialize the struct. Note that the **`mut`** is important. + - `rng.seed(seed_data)` - optionally seed it with an array of `u32` values. + - Use `rng.int()`, `rng.u32n(max)`, etc. + +You can change the default generator to a different one. The only requirement is that +the generator must implement the `PRNG` interface. See `get_current_rng()` and `set_rng()`. + +For non-uniform distributions, refer to the `rand.dist` module which defined functions for +sampling from non-uniform distributions. These functions make use of the global RNG. + +**Note:** The global PRNG is not thread safe. It is recommended to use separate generators for +separate threads in multi-threaded applications. If you need to use non-uniform sampling functions, +it is recommended to generate them before use in a multi-threaded context. + +For sampling functions and generating random strings, see `string_from_set()` and other related +functions defined in this top-level module. + +For arrays, see `rand.util`. + +# General Background + +A PRNG is a Pseudo Random Number Generator. +Computers cannot generate truly random numbers without an external source of noise or entropy. +We can use algorithms to generate sequences of seemingly random numbers, +but their outputs will always be deterministic. +This is often useful for simulations that need the same starting seed. + +If you need truly random numbers that are going to be used for cryptography, +use the `crypto.rand` module. + +# Guaranteed functions + +The following 21 functions are guaranteed to be supported by `rand` +as well as the individual PRNGs. + +- `seed(seed_data)` where `seed_data` is an array of `u32` values. + Different generators require different number of bits as the initial seed. + The smallest is 32-bits, required by `sys.SysRNG`. + Most others require 64-bits or 2 `u32` values. +- `u32()`, `u64()`, `int()`, `i64()`, `f32()`, `f64()` +- `u32n(max)`, `u64n(max)`, `intn(max)`, `i64n(max)`, `f32n(max)`, `f64n(max)` +- `u32_in_range(min, max)`, `u64_in_range(min, max)`, `int_in_range(min, max)`, + `i64_in_range(min, max)`, `f32_in_range(min, max)`, `f64_in_range(min, max)` +- `int31()`, `int63()` + +There are several additional functions defined in the top-level module that rely +on the global RNG. If you want to make use of those functions with a different +PRNG, you can can change the global RNG to do so. + +# Seeding Functions + +All the generators are time-seeded. +The helper functions publicly available in `rand.seed` module are: + +1. `time_seed_array()` - returns a `[]u32` that can be directly plugged into the `seed()` functions. +2. `time_seed_32()` and `time_seed_64()` - 32-bit and 64-bit values respectively + that are generated from the current time. + +# Caveats + +Note that the `sys.SysRNG` struct (in the C backend) uses `C.srand()` which sets the seed globally. +Consequently, all instances of the RNG will be affected. +This problem does not arise for the other RNGs. +A workaround (if you _must_ use the libc RNG) is to: + +1. Seed the first instance. +2. Generate all values required. +3. Seed the second instance. +4. Generate all values required. +5. And so on... + +# Notes + +Please note that [math interval](https://en.wikipedia.org/wiki/Interval_(mathematics)#Including_or_excluding_endpoints) notation is used throughout +the function documentation to denote what numbers ranges include. +An example of `[0, max)` thus denotes a range with all posible values +between `0` and `max` **including** 0 but **excluding** `max`. diff --git a/v_windows/v/vlib/rand/config/config.v b/v_windows/v/vlib/rand/config/config.v new file mode 100644 index 0000000..b11e77c --- /dev/null +++ b/v_windows/v/vlib/rand/config/config.v @@ -0,0 +1,13 @@ +module config + +import rand.seed + +// PRNGConfigStruct is a configuration struct for creating a new instance of the default RNG. +// Note that the RNGs may have a different number of u32s required for seeding. The default +// generator WyRand used 64 bits, ie. 2 u32s so that is the default. In case your desired generator +// uses a different number of u32s, use the `seed.time_seed_array()` method with the correct +// number of u32s. +pub struct PRNGConfigStruct { +pub: + seed_ []u32 = seed.time_seed_array(2) +} diff --git a/v_windows/v/vlib/rand/constants/constants.v b/v_windows/v/vlib/rand/constants/constants.v new file mode 100644 index 0000000..76fe211 --- /dev/null +++ b/v_windows/v/vlib/rand/constants/constants.v @@ -0,0 +1,12 @@ +module constants + +// Commonly used constants across RNGs - some taken from "Numerical Recipes". +pub const ( + lower_mask = u64(0x00000000FFFFFFFF) + max_u32 = 0xFFFFFFFF + max_u64 = 0xFFFFFFFFFFFFFFFF + max_u32_as_f32 = f32(max_u32) + 1 + max_u64_as_f64 = f64(max_u64) + 1 + u31_mask = u32(0x7FFFFFFF) + u63_mask = u64(0x7FFFFFFFFFFFFFFF) +) diff --git a/v_windows/v/vlib/rand/dist/README.md b/v_windows/v/vlib/rand/dist/README.md new file mode 100644 index 0000000..85b7177 --- /dev/null +++ b/v_windows/v/vlib/rand/dist/README.md @@ -0,0 +1,10 @@ +# Non-Uniform Distribution Functions + +This module contains functions for sampling from non-uniform distributions. + +All implementations of the `rand.PRNG` interface generate numbers from uniform +distributions. This library exists to allow the generation of pseudorandom numbers +sampled from non-uniform distributions. Additionally, it allows the user to use any +PRNG of their choice. This is because the default RNG can be reassigned to a different +generator. It can either be one of the pre-existing one (which are well-tested and +recommended) or a custom user-defined one. See `rand.set_rng()`. \ No newline at end of file diff --git a/v_windows/v/vlib/rand/dist/dist.v b/v_windows/v/vlib/rand/dist/dist.v new file mode 100644 index 0000000..b2d9055 --- /dev/null +++ b/v_windows/v/vlib/rand/dist/dist.v @@ -0,0 +1,85 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module dist + +import math +import rand + +fn check_probability_range(p f64) { + if p < 0 || p > 1 { + panic('$p is not a valid probability value.') + } +} + +// bernoulli returns true with a probability p. Note that 0 <= p <= 1. +pub fn bernoulli(p f64) bool { + check_probability_range(p) + return rand.f64() <= p +} + +// binomial returns the number of successful trials out of n when the +// probability of success for each trial is p. +pub fn binomial(n int, p f64) int { + check_probability_range(p) + mut count := 0 + for _ in 0 .. n { + if bernoulli(p) { + count++ + } + } + return count +} + +// Configuration struct for the `normal_pair` function. The default value for +// `mu` is 0 and the default value for `sigma` is 1. +pub struct NormalConfigStruct { + mu f64 = 0.0 + sigma f64 = 1.0 +} + +// normal_pair returns a pair of normally distributed random numbers with the mean mu +// and standard deviation sigma. If not specified, mu is 0 and sigma is 1. Intended usage is +// `x, y := normal_pair(mu: mean, sigma: stdev)`, or `x, y := normal_pair()`. +pub fn normal_pair(config NormalConfigStruct) (f64, f64) { + if config.sigma <= 0 { + panic('The standard deviation has to be positive.') + } + // This is an implementation of the Marsaglia polar method + // See: https://doi.org/10.1137%2F1006063 + // Also: https://en.wikipedia.org/wiki/Marsaglia_polar_method + for { + u := rand.f64_in_range(-1, 1) + v := rand.f64_in_range(-1, 1) + + s := u * u + v * v + if s >= 1 || s == 0 { + continue + } + t := math.sqrt(-2 * math.log(s) / s) + x := config.mu + config.sigma * t * u + y := config.mu + config.sigma * t * v + return x, y + } + return config.mu, config.mu +} + +// normal returns a normally distributed random number with the mean mu and standard deviation +// sigma. If not specified, mu is 0 and sigma is 1. Intended usage is +// `x := normal(mu: mean, sigma: etdev)` or `x := normal()`. +// **NOTE:** If you are generating a lot of normal variates, use `the normal_pair` function +// instead. This function discards one of the two variates generated by the `normal_pair` function. +pub fn normal(config NormalConfigStruct) f64 { + x, _ := normal_pair(config) + return x +} + +// exponential returns an exponentially distributed random number with the rate paremeter +// lambda. It is expected that lambda is positive. +pub fn exponential(lambda f64) f64 { + if lambda <= 0 { + panic('The rate (lambda) must be positive.') + } + // Use the inverse transform sampling method + return -math.log(rand.f64()) / lambda +} diff --git a/v_windows/v/vlib/rand/dist/dist_test.v b/v_windows/v/vlib/rand/dist/dist_test.v new file mode 100644 index 0000000..a7c565e --- /dev/null +++ b/v_windows/v/vlib/rand/dist/dist_test.v @@ -0,0 +1,134 @@ +import math +import rand +import rand.dist + +const ( + // The sample size to be used + count = 2000 + // Accepted error is within 5% of the actual values. + error = 0.05 + // The seeds used (for reproducible testing) + seeds = [[u32(0xffff24), 0xabcd], [u32(0x141024), 0x42851], + [u32(0x1452), 0x90cd], + ] +) + +fn test_bernoulli() { + ps := [0.0, 0.1, 1.0 / 3.0, 0.5, 0.8, 17.0 / 18.0, 1.0] + + for seed in seeds { + rand.seed(seed) + for p in ps { + mut successes := 0 + for _ in 0 .. count { + if dist.bernoulli(p) { + successes++ + } + } + assert math.abs(f64(successes) / count - p) < error + } + } +} + +fn test_binomial() { + ns := [100, 200, 1000] + ps := [0.0, 0.5, 0.95, 1.0] + + for seed in seeds { + rand.seed(seed) + for n in ns { + for p in ps { + np := n * p + npq := np * (1 - p) + + mut sum := 0 + mut var := 0.0 + for _ in 0 .. count { + x := dist.binomial(n, p) + sum += x + dist := (x - np) + var += dist * dist + } + + assert math.abs(f64(sum / count) - np) / n < error + assert math.abs(f64(var / count) - npq) / n < error + } + } + } +} + +fn test_normal_pair() { + mus := [0, 10, 100, -40] + sigmas := [1, 2, 40, 5] + total := 2 * count + + for seed in seeds { + rand.seed(seed) + for mu in mus { + for sigma in sigmas { + mut sum := 0.0 + mut var := 0.0 + for _ in 0 .. count { + x, y := dist.normal_pair(mu: mu, sigma: sigma) + sum += x + y + dist_x := x - mu + dist_y := y - mu + var += dist_x * dist_x + var += dist_y * dist_y + } + + variance := sigma * sigma + assert math.abs(f64(sum / total) - mu) / sigma < 1 + assert math.abs(f64(var / total) - variance) / variance < 2 * error + } + } + } +} + +fn test_normal() { + mus := [0, 10, 100, -40, 20] + sigmas := [1, 2, 5] + + for seed in seeds { + rand.seed(seed) + for mu in mus { + for sigma in sigmas { + mut sum := 0.0 + mut var := 0.0 + for _ in 0 .. count { + x := dist.normal(mu: mu, sigma: sigma) + sum += x + dist := x - mu + var += dist * dist + } + + variance := sigma * sigma + assert math.abs(f64(sum / count) - mu) / sigma < 1 + assert math.abs(f64(var / count) - variance) / variance < 2 * error + } + } + } +} + +fn test_exponential() { + lambdas := [1.0, 10, 1 / 20.0, 1 / 10000.0, 1 / 524.0, 200] + + for seed in seeds { + rand.seed(seed) + for lambda in lambdas { + mu := 1 / lambda + variance := mu * mu + mut sum := 0.0 + mut var := 0.0 + for _ in 0 .. count { + x := dist.exponential(lambda) + sum += x + dist := x - mu + var += dist * dist + } + + assert math.abs((f64(sum / count) - mu) / mu) < error + assert math.abs((f64(var / count) - variance) / variance) < 2 * error + } + } +} diff --git a/v_windows/v/vlib/rand/mt19937/mt19937.v b/v_windows/v/vlib/rand/mt19937/mt19937.v new file mode 100644 index 0000000..256fc06 --- /dev/null +++ b/v_windows/v/vlib/rand/mt19937/mt19937.v @@ -0,0 +1,325 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module mt19937 + +import math.bits + +/* +C++ functions for MT19937, with initialization improved 2002/2/10. + Coded by Takuji Nishimura and Makoto Matsumoto. + This is a faster version by taking Shawn Cokus's optimization, + Matthe Bellew's simplification, Isaku Wada's real version. + + Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + 3. The names of its contributors may not be used to endorse or promote + products derived from this software without specific prior written + permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + + Any feedback is very welcome. + http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html + email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space) +*/ +const ( + nn = 312 + mm = 156 + matrix_a = 0xB5026F5AA96619E9 + um = 0xFFFFFFFF80000000 + lm = 0x7FFFFFFF + inv_f64_limit = 1.0 / 9007199254740992.0 +) + +// MT19937RNG is generator that uses the Mersenne Twister algorithm with period 2^19937. +// **NOTE**: The RNG is not seeded when instantiated so remember to seed it before use. +pub struct MT19937RNG { +mut: + state []u64 = []u64{len: mt19937.nn} + mti int = mt19937.nn + next_rnd u32 + has_next bool +} + +// calculate_state returns a random state array calculated from the `seed_data`. +fn calculate_state(seed_data []u32, mut state []u64) []u64 { + lo := u64(seed_data[0]) + hi := u64(seed_data[1]) + state[0] = u64((hi << 32) | lo) + for j := 1; j < mt19937.nn; j++ { + state[j] = u64(6364136223846793005) * (state[j - 1] ^ (state[j - 1] >> 62)) + u64(j) + } + return *state +} + +// seed sets the current random state based on `seed_data`. +// seed expects `seed_data` to be only two `u32`s in little-endian format as [lower, higher]. +pub fn (mut rng MT19937RNG) seed(seed_data []u32) { + if seed_data.len != 2 { + eprintln('mt19937 needs only two 32bit integers as seed: [lower, higher]') + exit(1) + } + // calculate 2 times because MT19937RNG init didn't call calculate_state. + rng.state = calculate_state(seed_data, mut rng.state) + rng.state = calculate_state(seed_data, mut rng.state) + rng.mti = mt19937.nn + rng.next_rnd = 0 + rng.has_next = false +} + +// u32 returns a pseudorandom 32bit int in range `[0, 2³²)`. +[inline] +pub fn (mut rng MT19937RNG) u32() u32 { + if rng.has_next { + rng.has_next = false + return rng.next_rnd + } + ans := rng.u64() + rng.next_rnd = u32(ans >> 32) + rng.has_next = true + return u32(ans & 0xffffffff) +} + +// u64 returns a pseudorandom 64bit int in range `[0, 2⁶⁴)`. +[inline] +pub fn (mut rng MT19937RNG) u64() u64 { + mag01 := [u64(0), u64(mt19937.matrix_a)] + mut x := u64(0) + mut i := int(0) + if rng.mti >= mt19937.nn { + for i = 0; i < mt19937.nn - mt19937.mm; i++ { + x = (rng.state[i] & mt19937.um) | (rng.state[i + 1] & mt19937.lm) + rng.state[i] = rng.state[i + mt19937.mm] ^ (x >> 1) ^ mag01[int(x & 1)] + } + for i < mt19937.nn - 1 { + x = (rng.state[i] & mt19937.um) | (rng.state[i + 1] & mt19937.lm) + rng.state[i] = rng.state[i + (mt19937.mm - mt19937.nn)] ^ (x >> 1) ^ mag01[int(x & 1)] + i++ + } + x = (rng.state[mt19937.nn - 1] & mt19937.um) | (rng.state[0] & mt19937.lm) + rng.state[mt19937.nn - 1] = rng.state[mt19937.mm - 1] ^ (x >> 1) ^ mag01[int(x & 1)] + rng.mti = 0 + } + x = rng.state[rng.mti] + rng.mti++ + x ^= (x >> 29) & 0x5555555555555555 + x ^= (x << 17) & 0x71D67FFFEDA60000 + x ^= (x << 37) & 0xFFF7EEE000000000 + x ^= (x >> 43) + return x +} + +// int returns a 32-bit signed (possibly negative) `int`. +[inline] +pub fn (mut rng MT19937RNG) int() int { + return int(rng.u32()) +} + +// i64 returns a 64-bit signed (possibly negative) `i64`. +[inline] +pub fn (mut rng MT19937RNG) i64() i64 { + return i64(rng.u64()) +} + +// int31 returns a 31bit positive pseudorandom `int`. +[inline] +pub fn (mut rng MT19937RNG) int31() int { + return int(rng.u32() >> 1) +} + +// int63 returns a 63bit positive pseudorandom `i64`. +[inline] +pub fn (mut rng MT19937RNG) int63() i64 { + return i64(rng.u64() >> 1) +} + +// u32n returns a 32bit `u32` in range `[0, max)`. +[inline] +pub fn (mut rng MT19937RNG) u32n(max u32) u32 { + if max == 0 { + eprintln('max must be positive integer.') + exit(1) + } + // Check SysRNG in system_rng.c.v for explanation + bit_len := bits.len_32(max) + if bit_len == 32 { + for { + value := rng.u32() + if value < max { + return value + } + } + } else { + mask := (u32(1) << (bit_len + 1)) - 1 + for { + value := rng.u32() & mask + if value < max { + return value + } + } + } + return u32(0) +} + +// u64n returns a 64bit `u64` in range `[0, max)`. +[inline] +pub fn (mut rng MT19937RNG) u64n(max u64) u64 { + if max == 0 { + eprintln('max must be positive integer.') + exit(1) + } + bit_len := bits.len_64(max) + if bit_len == 64 { + for { + value := rng.u64() + if value < max { + return value + } + } + } else { + mask := (u64(1) << (bit_len + 1)) - 1 + for { + value := rng.u64() & mask + if value < max { + return value + } + } + } + return u64(0) +} + +// u32n returns a pseudorandom `u32` value that is guaranteed to be in range `[min, max)`. +[inline] +pub fn (mut rng MT19937RNG) u32_in_range(min u32, max u32) u32 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.u32n(max - min) +} + +// u64n returns a pseudorandom `u64` value that is guaranteed to be in range `[min, max)`. +[inline] +pub fn (mut rng MT19937RNG) u64_in_range(min u64, max u64) u64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.u64n(max - min) +} + +// intn returns a 32bit positive `int` in range `[0, max)`. +[inline] +pub fn (mut rng MT19937RNG) intn(max int) int { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return int(rng.u32n(u32(max))) +} + +// i64n returns a 64bit positive `i64` in range `[0, max)`. +[inline] +pub fn (mut rng MT19937RNG) i64n(max i64) i64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return i64(rng.u64n(u64(max))) +} + +// int_in_range returns a 32bit positive `int` in range `[min, max)`. +[inline] +pub fn (mut rng MT19937RNG) int_in_range(min int, max int) int { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.intn(max - min) +} + +// i64_in_range returns a 64bit positive `i64` in range `[min, max)`. +[inline] +pub fn (mut rng MT19937RNG) i64_in_range(min i64, max i64) i64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.i64n(max - min) +} + +// f32 returns a 32bit real (`f32`) in range `[0, 1)`. +[inline] +pub fn (mut rng MT19937RNG) f32() f32 { + return f32(rng.f64()) +} + +// f64 returns 64bit real (`f64`) in range `[0, 1)`. +[inline] +pub fn (mut rng MT19937RNG) f64() f64 { + return f64(rng.u64() >> 11) * mt19937.inv_f64_limit +} + +// f32n returns a 32bit real (`f32`) in range [0, max)`. +[inline] +pub fn (mut rng MT19937RNG) f32n(max f32) f32 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f32() * max +} + +// f64n returns a 64bit real (`f64`) in range `[0, max)`. +[inline] +pub fn (mut rng MT19937RNG) f64n(max f64) f64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f64() * max +} + +// f32_in_range returns a pseudorandom `f32` that lies in range `[min, max)`. +[inline] +pub fn (mut rng MT19937RNG) f32_in_range(min f32, max f32) f32 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.f32n(max - min) +} + +// i64_in_range returns a pseudorandom `i64` that lies in range `[min, max)`. +[inline] +pub fn (mut rng MT19937RNG) f64_in_range(min f64, max f64) f64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.f64n(max - min) +} diff --git a/v_windows/v/vlib/rand/mt19937/mt19937_test.v b/v_windows/v/vlib/rand/mt19937/mt19937_test.v new file mode 100644 index 0000000..f2a41de --- /dev/null +++ b/v_windows/v/vlib/rand/mt19937/mt19937_test.v @@ -0,0 +1,341 @@ +import math +import rand.mt19937 +import rand.seed + +const ( + range_limit = 40 + value_count = 1000 + seeds = [[u32(0xcafebabe), u32(0xdeadbeef)], [u32(0xc0de), u32(0xfeed)]] +) + +const ( + sample_size = 1000 + stats_epsilon = 0.05 + inv_sqrt_12 = 1.0 / math.sqrt(12) +) + +fn mt19937_basic_test() { + mut rng := mt19937.MT19937RNG{} + rng.seed([u32(0xdeadbeef)]) + target := [u32(956529277), 3842322136, 3319553134, 1843186657, 2704993644, 595827513, 938518626, + 1676224337, 3221315650, 1819026461] + for i := 0; i < 10; i++ { + assert target[i] == rng.u32() + } +} + +fn gen_randoms(seed_data []u32, bound int) []u64 { + bound_u64 := u64(bound) + mut randoms := []u64{len: (20)} + mut rnd := mt19937.MT19937RNG{} + rnd.seed(seed_data) + for i in 0 .. 20 { + randoms[i] = rnd.u64n(bound_u64) + } + return randoms +} + +fn test_mt19937_reproducibility() { + seed_data := seed.time_seed_array(2) + randoms1 := gen_randoms(seed_data, 1000) + randoms2 := gen_randoms(seed_data, 1000) + assert randoms1.len == randoms2.len + len := randoms1.len + for i in 0 .. len { + assert randoms1[i] == randoms2[i] + } +} + +// TODO: use the `in` syntax and remove this function +// after generics has been completely implemented +fn found(value u64, arr []u64) bool { + for item in arr { + if value == item { + return true + } + } + return false +} + +fn test_mt19937_variability() { + // If this test fails and if it is certainly not the implementation + // at fault, try changing the seed values. Repeated values are + // improbable but not impossible. + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + mut values := []u64{cap: value_count} + for i in 0 .. value_count { + value := rng.u64() + assert !found(value, values) + assert values.len == i + values << value + } + } +} + +fn check_uniformity_u64(mut rng mt19937.MT19937RNG, range u64) { + range_f64 := f64(range) + expected_mean := range_f64 / 2.0 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := f64(rng.u64n(range)) - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := range_f64 * inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_mt19937_uniformity_u64() { + ranges := [14019545, 80240, 130] + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for range in ranges { + check_uniformity_u64(mut rng, u64(range)) + } + } +} + +fn check_uniformity_f64(mut rng mt19937.MT19937RNG) { + expected_mean := 0.5 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := rng.f64() - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_mt19937_uniformity_f64() { + // The f64 version + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + check_uniformity_f64(mut rng) + } +} + +fn test_mt19937_u32n() { + max := u32(16384) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_mt19937_u64n() { + max := u64(379091181005) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_mt19937_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_mt19937_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_mt19937_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } + } +} + +fn test_mt19937_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } + } +} + +fn test_mt19937_intn() { + max := 2525642 + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.intn(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_mt19937_i64n() { + max := i64(3246727724653636) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_mt19937_int_in_range() { + min := -4252 + max := 1034 + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_mt19937_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_mt19937_f32() { + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_mt19937_f64() { + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_mt19937_f32n() { + max := f32(357.0) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_mt19937_f64n() { + max := 1.52e6 + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_mt19937_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_mt19937_f64_in_range() { + min := -548.7 + max := 5015.2 + for seed in seeds { + mut rng := mt19937.MT19937RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64_in_range(min, max) + assert value >= min + assert value < max + } + } +} diff --git a/v_windows/v/vlib/rand/musl/musl_rng.v b/v_windows/v/vlib/rand/musl/musl_rng.v new file mode 100644 index 0000000..fdfb733 --- /dev/null +++ b/v_windows/v/vlib/rand/musl/musl_rng.v @@ -0,0 +1,241 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module musl + +import math.bits +import rand.seed +import rand.constants + +// MuslRNG ported from https://git.musl-libc.org/cgit/musl/tree/src/prng/rand_r.c +pub struct MuslRNG { +mut: + state u32 = seed.time_seed_32() +} + +// seed sets the current random state based on `seed_data`. +// seed expects `seed_data` to be only one `u32`. +pub fn (mut rng MuslRNG) seed(seed_data []u32) { + if seed_data.len != 1 { + eprintln('MuslRNG needs only one unsigned 32-bit integer as a seed.') + exit(1) + } + rng.state = seed_data[0] +} + +// temper returns a tempered value based on `prev` value. +[inline] +fn temper(prev u32) u32 { + mut x := prev + x ^= x >> 11 + x ^= (x << 7) & 0x9D2C5680 + x ^= (x << 15) & 0xEFC60000 + x ^= (x >> 18) + return x +} + +// u32 returns a pseudorandom 32-bit unsigned integer (`u32`). +[inline] +pub fn (mut rng MuslRNG) u32() u32 { + rng.state = rng.state * 1103515245 + 12345 + // We are not dividing by 2 (or shifting right by 1) + // because we want all 32-bits of random data + return temper(rng.state) +} + +// u64 returns a pseudorandom 64-bit unsigned integer (`u64`). +[inline] +pub fn (mut rng MuslRNG) u64() u64 { + return u64(rng.u32()) | (u64(rng.u32()) << 32) +} + +// u32n returns a pseudorandom 32-bit unsigned integer `u32` in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) u32n(max u32) u32 { + if max == 0 { + eprintln('max must be positive integer.') + exit(1) + } + // Check SysRNG in system_rng.c.v for explanation + bit_len := bits.len_32(max) + if bit_len == 32 { + for { + value := rng.u32() + if value < max { + return value + } + } + } else { + mask := (u32(1) << (bit_len + 1)) - 1 + for { + value := rng.u32() & mask + if value < max { + return value + } + } + } + return u32(0) +} + +// u64n returns a pseudorandom 64-bit unsigned integer (`u64`) in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) u64n(max u64) u64 { + if max == 0 { + eprintln('max must be positive integer.') + exit(1) + } + bit_len := bits.len_64(max) + if bit_len == 64 { + for { + value := rng.u64() + if value < max { + return value + } + } + } else { + mask := (u64(1) << (bit_len + 1)) - 1 + for { + value := rng.u64() & mask + if value < max { + return value + } + } + } + return u64(0) +} + +// u32_in_range returns a pseudorandom 32-bit unsigned integer (`u32`) in range `[min, max)`. +[inline] +pub fn (mut rng MuslRNG) u32_in_range(min u32, max u32) u32 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.u32n(u32(max - min)) +} + +// u64_in_range returns a pseudorandom 64-bit unsigned integer (`u64`) in range `[min, max)`. +[inline] +pub fn (mut rng MuslRNG) u64_in_range(min u64, max u64) u64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.u64n(max - min) +} + +// int returns a 32-bit signed (possibly negative) integer (`int`). +[inline] +pub fn (mut rng MuslRNG) int() int { + return int(rng.u32()) +} + +// i64 returns a 64-bit signed (possibly negative) integer (`i64`). +[inline] +pub fn (mut rng MuslRNG) i64() i64 { + return i64(rng.u64()) +} + +// int31 returns a 31-bit positive pseudorandom integer (`int`). +[inline] +pub fn (mut rng MuslRNG) int31() int { + return int(rng.u32() >> 1) +} + +// int63 returns a 63-bit positive pseudorandom integer (`i64`). +[inline] +pub fn (mut rng MuslRNG) int63() i64 { + return i64(rng.u64() >> 1) +} + +// intn returns a 32-bit positive int in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) intn(max int) int { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return int(rng.u32n(u32(max))) +} + +// i64n returns a 64-bit positive integer `i64` in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) i64n(max i64) i64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return i64(rng.u64n(u64(max))) +} + +// int_in_range returns a 32-bit positive integer `int` in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) int_in_range(min int, max int) int { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.intn(max - min) +} + +// i64_in_range returns a 64-bit positive integer `i64` in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) i64_in_range(min i64, max i64) i64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.i64n(max - min) +} + +// f32 returns a pseudorandom `f32` value in range `[0, 1)`. +[inline] +pub fn (mut rng MuslRNG) f32() f32 { + return f32(rng.u32()) / constants.max_u32_as_f32 +} + +// f64 returns a pseudorandom `f64` value in range `[0, 1)`. +[inline] +pub fn (mut rng MuslRNG) f64() f64 { + return f64(rng.u64()) / constants.max_u64_as_f64 +} + +// f32n returns a pseudorandom `f32` value in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) f32n(max f32) f32 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f32() * max +} + +// f64n returns a pseudorandom `f64` value in range `[0, max)`. +[inline] +pub fn (mut rng MuslRNG) f64n(max f64) f64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f64() * max +} + +// f32_in_range returns a pseudorandom `f32` in range `[min, max)`. +[inline] +pub fn (mut rng MuslRNG) f32_in_range(min f32, max f32) f32 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.f32n(max - min) +} + +// i64_in_range returns a pseudorandom `i64` in range `[min, max)`. +[inline] +pub fn (mut rng MuslRNG) f64_in_range(min f64, max f64) f64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.f64n(max - min) +} diff --git a/v_windows/v/vlib/rand/musl/musl_rng_test.v b/v_windows/v/vlib/rand/musl/musl_rng_test.v new file mode 100644 index 0000000..e6406f9 --- /dev/null +++ b/v_windows/v/vlib/rand/musl/musl_rng_test.v @@ -0,0 +1,331 @@ +import math +import rand.musl +import rand.seed + +const ( + range_limit = 40 + value_count = 1000 + seeds = [[u32(42)], [u32(256)]] +) + +const ( + sample_size = 1000 + stats_epsilon = 0.05 + inv_sqrt_12 = 1.0 / math.sqrt(12) +) + +fn gen_randoms(seed_data []u32, bound int) []u64 { + bound_u64 := u64(bound) + mut randoms := []u64{len: (20)} + mut rnd := musl.MuslRNG{} + rnd.seed(seed_data) + for i in 0 .. 20 { + randoms[i] = rnd.u64n(bound_u64) + } + return randoms +} + +fn test_musl_reproducibility() { + seed_data := seed.time_seed_array(1) + randoms1 := gen_randoms(seed_data, 1000) + randoms2 := gen_randoms(seed_data, 1000) + assert randoms1.len == randoms2.len + len := randoms1.len + for i in 0 .. len { + assert randoms1[i] == randoms2[i] + } +} + +// TODO: use the `in` syntax and remove this function +// after generics has been completely implemented +fn found(value u64, arr []u64) bool { + for item in arr { + if value == item { + return true + } + } + return false +} + +fn test_musl_variability() { + // If this test fails and if it is certainly not the implementation + // at fault, try changing the seed values. Repeated values are + // improbable but not impossible. + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + mut values := []u64{cap: value_count} + for i in 0 .. value_count { + value := rng.u64() + assert !found(value, values) + assert values.len == i + values << value + } + } +} + +fn check_uniformity_u64(mut rng musl.MuslRNG, range u64) { + range_f64 := f64(range) + expected_mean := range_f64 / 2.0 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := f64(rng.u64n(range)) - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := range_f64 * inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_musl_uniformity_u64() { + ranges := [14019545, 80240, 130] + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for range in ranges { + check_uniformity_u64(mut rng, u64(range)) + } + } +} + +fn check_uniformity_f64(mut rng musl.MuslRNG) { + expected_mean := 0.5 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := rng.f64() - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_musl_uniformity_f64() { + // The f64 version + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + check_uniformity_f64(mut rng) + } +} + +fn test_musl_u32n() { + max := u32(16384) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_musl_u64n() { + max := u64(379091181005) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_musl_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_musl_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_musl_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } + } +} + +fn test_musl_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } + } +} + +fn test_musl_intn() { + max := 2525642 + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.intn(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_musl_i64n() { + max := i64(3246727724653636) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_musl_int_in_range() { + min := -4252 + max := 1034 + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_musl_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_musl_f32() { + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_musl_f64() { + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_musl_f32n() { + max := f32(357.0) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_musl_f64n() { + max := 1.52e6 + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_musl_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_musl_f64_in_range() { + min := -548.7 + max := 5015.2 + for seed in seeds { + mut rng := musl.MuslRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64_in_range(min, max) + assert value >= min + assert value < max + } + } +} diff --git a/v_windows/v/vlib/rand/pcg32/pcg32.v b/v_windows/v/vlib/rand/pcg32/pcg32.v new file mode 100644 index 0000000..25a83f7 --- /dev/null +++ b/v_windows/v/vlib/rand/pcg32/pcg32.v @@ -0,0 +1,226 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module pcg32 + +import rand.seed +import rand.constants + +// PCG32RNG ported from http://www.pcg-random.org/download.html, +// https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c, and +// https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.h +pub struct PCG32RNG { +mut: + state u64 = u64(0x853c49e6748fea9b) ^ seed.time_seed_64() + inc u64 = u64(0xda3e39cb94b95bdb) ^ seed.time_seed_64() +} + +// seed seeds the PCG32RNG with 4 `u32` values. +// The first 2 represent the 64-bit initial state as `[lower 32 bits, higher 32 bits]` +// The last 2 represent the 64-bit stream/step of the PRNG. +pub fn (mut rng PCG32RNG) seed(seed_data []u32) { + if seed_data.len != 4 { + eprintln('PCG32RNG needs 4 u32s to be seeded. First two the initial state and the last two the stream/step. Both in little endian format: [lower, higher].') + exit(1) + } + init_state := u64(seed_data[0]) | (u64(seed_data[1]) << 32) + init_seq := u64(seed_data[2]) | (u64(seed_data[3]) << 32) + rng.state = u64(0) + rng.inc = (init_seq << u64(1)) | u64(1) + rng.u32() + rng.state += init_state + rng.u32() +} + +// u32 returns a pseudorandom unsigned `u32`. +[inline] +pub fn (mut rng PCG32RNG) u32() u32 { + oldstate := rng.state + rng.state = oldstate * (6364136223846793005) + rng.inc + xorshifted := u32(((oldstate >> u64(18)) ^ oldstate) >> u64(27)) + rot := u32(oldstate >> u64(59)) + return ((xorshifted >> rot) | (xorshifted << ((-rot) & u32(31)))) +} + +// u64 returns a pseudorandom 64-bit unsigned `u64`. +[inline] +pub fn (mut rng PCG32RNG) u64() u64 { + return u64(rng.u32()) | (u64(rng.u32()) << 32) +} + +// u32n returns a pseudorandom 32-bit unsigned `u32` in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) u32n(max u32) u32 { + if max == 0 { + eprintln('max must be positive') + exit(1) + } + // To avoid bias, we need to make the range of the RNG a multiple of + // max, which we do by dropping output less than a threshold. + threshold := (-max % max) + // Uniformity guarantees that loop below will terminate. In practice, it + // should usually terminate quickly; on average (assuming all max's are + // equally likely), 82.25% of the time, we can expect it to require just + // one iteration. In practice, max's are typically small and only a + // tiny amount of the range is eliminated. + for { + r := rng.u32() + if r >= threshold { + return (r % max) + } + } + return u32(0) +} + +// u64n returns a pseudorandom 64-bit unsigned `u64` in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) u64n(max u64) u64 { + if max == 0 { + eprintln('max must be positive') + exit(1) + } + threshold := (-max % max) + for { + r := rng.u64() + if r >= threshold { + return (r % max) + } + } + return u64(0) +} + +// u32_in_range returns a pseudorandom 32-bit unsigned `u32` in range `[min, max)`. +[inline] +pub fn (mut rng PCG32RNG) u32_in_range(min u32, max u32) u32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.u32n(u32(max - min)) +} + +// u64_in_range returns a pseudorandom 64-bit unsigned `u64` in range `[min, max)`. +[inline] +pub fn (mut rng PCG32RNG) u64_in_range(min u64, max u64) u64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.u64n(max - min) +} + +// int returns a 32-bit signed (possibly negative) `int`. +[inline] +pub fn (mut rng PCG32RNG) int() int { + return int(rng.u32()) +} + +// i64 returns a 64-bit signed (possibly negative) `i64`. +[inline] +pub fn (mut rng PCG32RNG) i64() i64 { + return i64(rng.u64()) +} + +// int31 returns a 31-bit positive pseudorandom `int`. +[inline] +pub fn (mut rng PCG32RNG) int31() int { + return int(rng.u32() >> 1) +} + +// int63 returns a 63-bit positive pseudorandom `i64`. +[inline] +pub fn (mut rng PCG32RNG) int63() i64 { + return i64(rng.u64() >> 1) +} + +// intn returns a 32-bit positive `int` in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) intn(max int) int { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return int(rng.u32n(u32(max))) +} + +// i64n returns a 64-bit positive `i64` in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) i64n(max i64) i64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return i64(rng.u64n(u64(max))) +} + +// int_in_range returns a 32-bit positive `int` in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) int_in_range(min int, max int) int { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.intn(max - min) +} + +// i64_in_range returns a 64-bit positive `i64` in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) i64_in_range(min i64, max i64) i64 { + if max <= min { + eprintln('max must be greater than min.') + exit(1) + } + return min + rng.i64n(max - min) +} + +// f32 returns a pseudorandom `f32` value in range `[0, 1)`. +[inline] +pub fn (mut rng PCG32RNG) f32() f32 { + return f32(rng.u32()) / constants.max_u32_as_f32 +} + +// f64 returns a pseudorandom `f64` value in range `[0, 1)`. +[inline] +pub fn (mut rng PCG32RNG) f64() f64 { + return f64(rng.u64()) / constants.max_u64_as_f64 +} + +// f32n returns a pseudorandom `f32` value in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) f32n(max f32) f32 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f32() * max +} + +// f64n returns a pseudorandom `f64` value in range `[0, max)`. +[inline] +pub fn (mut rng PCG32RNG) f64n(max f64) f64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f64() * max +} + +// f32_in_range returns a pseudorandom `f32` in range `[min, max)`. +[inline] +pub fn (mut rng PCG32RNG) f32_in_range(min f32, max f32) f32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.f32n(max - min) +} + +// i64_in_range returns a pseudorandom `i64` in range `[min, max)`. +[inline] +pub fn (mut rng PCG32RNG) f64_in_range(min f64, max f64) f64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.f64n(max - min) +} diff --git a/v_windows/v/vlib/rand/pcg32/pcg32_test.v b/v_windows/v/vlib/rand/pcg32/pcg32_test.v new file mode 100644 index 0000000..17048a0 --- /dev/null +++ b/v_windows/v/vlib/rand/pcg32/pcg32_test.v @@ -0,0 +1,337 @@ +import math +import rand +import rand.pcg32 +import rand.seed + +const ( + range_limit = 40 + value_count = 1000 + seeds = [[u32(42), 242, 267, 14195], [u32(256), 340, 1451, 1505]] +) + +const ( + sample_size = 1000 + stats_epsilon = 0.05 + inv_sqrt_12 = 1.0 / math.sqrt(12) +) + +fn gen_randoms(seed_data []u32, bound int) []u32 { + mut randoms := []u32{len: 20} + mut rng := pcg32.PCG32RNG{} + rng.seed(seed_data) + for i in 0 .. 20 { + randoms[i] = rng.u32n(u32(bound)) + } + return randoms +} + +fn test_pcg32_reproducibility() { + seed_data := seed.time_seed_array(4) + randoms1 := gen_randoms(seed_data, 1000) + randoms2 := gen_randoms(seed_data, 1000) + assert randoms1.len == randoms2.len + len := randoms1.len + for i in 0 .. len { + r1 := randoms1[i] + r2 := randoms2[i] + assert r1 == r2 + } +} + +// TODO: use the `in` syntax and remove this function +// after generics has been completely implemented +fn found(value u64, arr []u64) bool { + for item in arr { + if value == item { + return true + } + } + return false +} + +fn test_pcg32_variability() { + // If this test fails and if it is certainly not the implementation + // at fault, try changing the seed values. Repeated values are + // improbable but not impossible. + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + mut values := []u64{cap: value_count} + for i in 0 .. value_count { + value := rng.u64() + assert !found(value, values) + assert values.len == i + values << value + } + } +} + +fn check_uniformity_u64(mut rng pcg32.PCG32RNG, range u64) { + range_f64 := f64(range) + expected_mean := range_f64 / 2.0 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := f64(rng.u64n(range)) - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := range_f64 * inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_pcg32_uniformity_u64() { + ranges := [14019545, 80240, 130] + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for range in ranges { + check_uniformity_u64(mut rng, u64(range)) + } + } +} + +fn check_uniformity_f64(mut rng pcg32.PCG32RNG) { + expected_mean := 0.5 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := rng.f64() - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_pcg32_uniformity_f64() { + // The f64 version + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + check_uniformity_f64(mut rng) + } +} + +fn test_pcg32_u32n() { + max := u32(16384) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_pcg32_u64n() { + max := u64(379091181005) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_pcg32_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32_in_range(u32(min), u32(max)) + assert value >= min + assert value < max + } + } +} + +fn test_pcg32_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_pcg32_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } + } +} + +fn test_pcg32_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } + } +} + +fn test_pcg32_intn() { + max := 2525642 + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.intn(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_pcg32_i64n() { + max := i64(3246727724653636) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_pcg32_int_in_range() { + min := -4252 + max := 1034 + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_pcg32_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_pcg32_f32() { + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_pcg32_f64() { + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_pcg32_f32n() { + max := f32(357.0) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_pcg32_f64n() { + max := 1.52e6 + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_pcg32_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_pcg32_f64_in_range() { + min := -548.7 + max := 5015.2 + for seed in seeds { + mut rng := pcg32.PCG32RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_change_default_random_generator() { + rand.set_rng(pcg32.PCG32RNG{}) +} diff --git a/v_windows/v/vlib/rand/rand.c.v b/v_windows/v/vlib/rand/rand.c.v new file mode 100644 index 0000000..066d8eb --- /dev/null +++ b/v_windows/v/vlib/rand/rand.c.v @@ -0,0 +1,127 @@ +module rand + +import time +// uuid_v4 generates a random (v4) UUID +// See https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random) + +pub fn uuid_v4() string { + buflen := 36 + mut buf := unsafe { malloc_noscan(37) } + mut i_buf := 0 + mut x := u64(0) + mut d := byte(0) + for i_buf < buflen { + mut c := 0 + x = default_rng.u64() + // do most of the bit manipulation at once: + x &= 0x0F0F0F0F0F0F0F0F + x += 0x3030303030303030 + // write the ASCII codes to the buffer: + for c < 8 && i_buf < buflen { + d = byte(x) + unsafe { + buf[i_buf] = if d > 0x39 { d + 0x27 } else { d } + } + i_buf++ + c++ + x = x >> 8 + } + } + // there are still some random bits in x: + x = x >> 8 + d = byte(x) + unsafe { + buf[19] = if d > 0x39 { d + 0x27 } else { d } + buf[8] = `-` + buf[13] = `-` + buf[18] = `-` + buf[23] = `-` + buf[14] = `4` + buf[buflen] = 0 + return buf.vstring_with_len(buflen) + } +} + +const ( + ulid_encoding = '0123456789ABCDEFGHJKMNPQRSTVWXYZ' +) + +// ulid generates an Unique Lexicographically sortable IDentifier. +// See https://github.com/ulid/spec . +// NB: ULIDs can leak timing information, if you make them public, because +// you can infer the rate at which some resource is being created, like +// users or business transactions. +// (https://news.ycombinator.com/item?id=14526173) +pub fn ulid() string { + return ulid_at_millisecond(u64(time.utc().unix_time_milli())) +} + +// ulid_at_millisecond does the same as `ulid` but takes a custom Unix millisecond timestamp via `unix_time_milli`. +pub fn ulid_at_millisecond(unix_time_milli u64) string { + buflen := 26 + mut buf := unsafe { malloc_noscan(27) } + mut t := unix_time_milli + mut i := 9 + for i >= 0 { + unsafe { + buf[i] = rand.ulid_encoding[t & 0x1F] + } + t = t >> 5 + i-- + } + // first rand set + mut x := default_rng.u64() + i = 10 + for i < 19 { + unsafe { + buf[i] = rand.ulid_encoding[x & 0x1F] + } + x = x >> 5 + i++ + } + // second rand set + x = default_rng.u64() + for i < 26 { + unsafe { + buf[i] = rand.ulid_encoding[x & 0x1F] + } + x = x >> 5 + i++ + } + unsafe { + buf[26] = 0 + return buf.vstring_with_len(buflen) + } +} + +// string_from_set returns a string of length `len` containing random characters sampled from the given `charset` +pub fn string_from_set(charset string, len int) string { + if len == 0 { + return '' + } + mut buf := unsafe { malloc_noscan(len + 1) } + for i in 0 .. len { + unsafe { + buf[i] = charset[intn(charset.len)] + } + } + unsafe { + buf[len] = 0 + } + return unsafe { buf.vstring_with_len(len) } +} + +// string returns a string of length `len` containing random characters in range `[a-zA-Z]`. +pub fn string(len int) string { + return string_from_set(english_letters, len) +} + +// hex returns a hexadecimal number of length `len` containing random characters in range `[a-f0-9]`. +pub fn hex(len int) string { + return string_from_set(hex_chars, len) +} + +// ascii returns a random string of the printable ASCII characters with length `len`. +pub fn ascii(len int) string { + return string_from_set(ascii_chars, len) +} diff --git a/v_windows/v/vlib/rand/rand.v b/v_windows/v/vlib/rand/rand.v new file mode 100644 index 0000000..d790dd5 --- /dev/null +++ b/v_windows/v/vlib/rand/rand.v @@ -0,0 +1,183 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module rand + +import rand.config +import rand.wyrand + +// PRNG is a common interface for all PRNGs that can be used seamlessly with the rand +// modules's API. It defines all the methods that a PRNG (in the vlib or custom made) must +// implement in order to ensure that _all_ functions can be used with the generator. +pub interface PRNG { + seed(seed_data []u32) + u32() u32 + u64() u64 + u32n(max u32) u32 + u64n(max u64) u64 + u32_in_range(min u32, max u32) u32 + u64_in_range(min u64, max u64) u64 + int() int + i64() i64 + int31() int + int63() i64 + intn(max int) int + i64n(max i64) i64 + int_in_range(min int, max int) int + i64_in_range(min i64, max i64) i64 + f32() f32 + f64() f64 + f32n(max f32) f32 + f64n(max f64) f64 + f32_in_range(min f32, max f32) f32 + f64_in_range(min f64, max f64) f64 +} + +__global ( + default_rng &PRNG +) + +// init initializes the default RNG. +fn init() { + default_rng = new_default() +} + +// new_default returns a new instance of the default RNG. If the seed is not provided, the current time will be used to seed the instance. +pub fn new_default(config config.PRNGConfigStruct) &PRNG { + mut rng := &wyrand.WyRandRNG{} + rng.seed(config.seed_) + return rng +} + +// get_current_rng returns the PRNG instance currently in use. If it is not changed, it will be an instance of wyrand.WyRandRNG. +pub fn get_current_rng() &PRNG { + return default_rng +} + +// set_rng changes the default RNG from wyrand.WyRandRNG (or whatever the last RNG was) to the one +// provided by the user. Note that this new RNG must be seeded manually with a constant seed or the +// `seed.time_seed_array()` method. Also, it is recommended to store the old RNG in a variable and +// should be restored if work with the custom RNG is complete. It is not necessary to restore if the +// program terminates soon afterwards. +pub fn set_rng(rng &PRNG) { + default_rng = unsafe { rng } +} + +// seed sets the given array of `u32` values as the seed for the `default_rng`. The default_rng is +// an instance of WyRandRNG which takes 2 u32 values. When using a custom RNG, make sure to use +// the correct number of u32s. +pub fn seed(seed []u32) { + default_rng.seed(seed) +} + +// u32 returns a uniformly distributed `u32` in range `[0, 2³²)`. +pub fn u32() u32 { + return default_rng.u32() +} + +// u64 returns a uniformly distributed `u64` in range `[0, 2⁶⁴)`. +pub fn u64() u64 { + return default_rng.u64() +} + +// u32n returns a uniformly distributed pseudorandom 32-bit signed positive `u32` in range `[0, max)`. +pub fn u32n(max u32) u32 { + return default_rng.u32n(max) +} + +// u64n returns a uniformly distributed pseudorandom 64-bit signed positive `u64` in range `[0, max)`. +pub fn u64n(max u64) u64 { + return default_rng.u64n(max) +} + +// u32_in_range returns a uniformly distributed pseudorandom 32-bit unsigned `u32` in range `[min, max)`. +pub fn u32_in_range(min u32, max u32) u32 { + return default_rng.u32_in_range(min, max) +} + +// u64_in_range returns a uniformly distributed pseudorandom 64-bit unsigned `u64` in range `[min, max)`. +pub fn u64_in_range(min u64, max u64) u64 { + return default_rng.u64_in_range(min, max) +} + +// int returns a uniformly distributed pseudorandom 32-bit signed (possibly negative) `int`. +pub fn int() int { + return default_rng.int() +} + +// intn returns a uniformly distributed pseudorandom 32-bit signed positive `int` in range `[0, max)`. +pub fn intn(max int) int { + return default_rng.intn(max) +} + +// byte returns a uniformly distributed pseudorandom 8-bit unsigned positive `byte`. +pub fn byte() byte { + return byte(default_rng.u32() & 0xff) +} + +// int_in_range returns a uniformly distributed pseudorandom 32-bit signed int in range `[min, max)`. +// Both `min` and `max` can be negative, but we must have `min < max`. +pub fn int_in_range(min int, max int) int { + return default_rng.int_in_range(min, max) +} + +// int31 returns a uniformly distributed pseudorandom 31-bit signed positive `int`. +pub fn int31() int { + return default_rng.int31() +} + +// i64 returns a uniformly distributed pseudorandom 64-bit signed (possibly negative) `i64`. +pub fn i64() i64 { + return default_rng.i64() +} + +// i64n returns a uniformly distributed pseudorandom 64-bit signed positive `i64` in range `[0, max)`. +pub fn i64n(max i64) i64 { + return default_rng.i64n(max) +} + +// i64_in_range returns a uniformly distributed pseudorandom 64-bit signed `i64` in range `[min, max)`. +pub fn i64_in_range(min i64, max i64) i64 { + return default_rng.i64_in_range(min, max) +} + +// int63 returns a uniformly distributed pseudorandom 63-bit signed positive `i64`. +pub fn int63() i64 { + return default_rng.int63() +} + +// f32 returns a uniformly distributed 32-bit floating point in range `[0, 1)`. +pub fn f32() f32 { + return default_rng.f32() +} + +// f64 returns a uniformly distributed 64-bit floating point in range `[0, 1)`. +pub fn f64() f64 { + return default_rng.f64() +} + +// f32n returns a uniformly distributed 32-bit floating point in range `[0, max)`. +pub fn f32n(max f32) f32 { + return default_rng.f32n(max) +} + +// f64n returns a uniformly distributed 64-bit floating point in range `[0, max)`. +pub fn f64n(max f64) f64 { + return default_rng.f64n(max) +} + +// f32_in_range returns a uniformly distributed 32-bit floating point in range `[min, max)`. +pub fn f32_in_range(min f32, max f32) f32 { + return default_rng.f32_in_range(min, max) +} + +// f64_in_range returns a uniformly distributed 64-bit floating point in range `[min, max)`. +pub fn f64_in_range(min f64, max f64) f64 { + return default_rng.f64_in_range(min, max) +} + +const ( + english_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' + hex_chars = 'abcdef0123456789' + ascii_chars = '!"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ\\^_`abcdefghijklmnopqrstuvwxyz{|}~' +) diff --git a/v_windows/v/vlib/rand/random_identifiers_test.v b/v_windows/v/vlib/rand/random_identifiers_test.v new file mode 100644 index 0000000..d54fa84 --- /dev/null +++ b/v_windows/v/vlib/rand/random_identifiers_test.v @@ -0,0 +1,70 @@ +import time +import rand + +// uuid_v4: +fn test_rand_uuid_v4() { + uuid1 := rand.uuid_v4() + uuid2 := rand.uuid_v4() + uuid3 := rand.uuid_v4() + assert uuid1 != uuid2 + assert uuid1 != uuid3 + assert uuid2 != uuid3 + assert uuid1.len == 36 + assert uuid2.len == 36 + assert uuid3.len == 36 + assert uuid1[14] == `4` + assert uuid2[14] == `4` + assert uuid3[14] == `4` +} + +// ulids: +fn test_ulids_are_unique() { + ulid1 := rand.ulid() + ulid2 := rand.ulid() + ulid3 := rand.ulid() + assert ulid1.len == 26 + assert ulid2.len == 26 + assert ulid3.len == 26 + assert ulid1 != ulid2 + assert ulid1 != ulid3 + assert ulid2 != ulid3 +} + +fn test_ulids_max_start_character_is_ok() { + ulid1 := rand.ulid() + // the largest valid ULID encoded in Base32 is 7ZZZZZZZZZZZZZZZZZZZZZZZZZ + assert (int(ulid1[0]) - 48) <= 7 +} + +fn test_ulids_generated_in_the_same_millisecond_have_the_same_prefix() { + t := u64(time.utc().unix_time_milli()) + mut ulid1 := '' + mut ulid2 := '' + mut ulid3 := '' + ulid1 = rand.ulid_at_millisecond(t) + ulid2 = rand.ulid_at_millisecond(t) + ulid3 = rand.ulid_at_millisecond(t) + ulid1_prefix := ulid1[0..10] + ulid2_prefix := ulid2[0..10] + ulid3_prefix := ulid3[0..10] + assert ulid1_prefix == ulid2_prefix + assert ulid1_prefix == ulid3_prefix +} + +fn test_ulids_should_be_lexicographically_ordered_when_not_in_same_millisecond() { + ulid1 := rand.ulid() + time.sleep(1 * time.millisecond) + ulid2 := rand.ulid() + time.sleep(1 * time.millisecond) + ulid3 := rand.ulid() + mut all := [ulid3, ulid2, ulid1] + // eprintln('all before: $all') + all.sort() + // eprintln('all after: $all') + s1 := all[0] + s2 := all[1] + s3 := all[2] + assert s1 == ulid1 + assert s2 == ulid2 + assert s3 == ulid3 +} diff --git a/v_windows/v/vlib/rand/random_numbers_test.v b/v_windows/v/vlib/rand/random_numbers_test.v new file mode 100644 index 0000000..f09fa3c --- /dev/null +++ b/v_windows/v/vlib/rand/random_numbers_test.v @@ -0,0 +1,319 @@ +import rand +import rand.splitmix64 +import rand.musl +import rand.mt19937 + +const ( + rnd_count = 40 + seeds = [[u32(42), 0], [u32(256), 0]] +) + +fn get_n_random_ints(seed_data []u32, n int) []int { + mut values := []int{cap: n} + rand.seed(seed_data) + for _ in 0 .. n { + values << rand.intn(n) + } + return values +} + +fn test_rand_reproducibility() { + for seed in seeds { + array1 := get_n_random_ints(seed, 1000) + array2 := get_n_random_ints(seed, 1000) + assert array1.len == array2.len + assert array1 == array2 + } +} + +fn test_rand_u32n() { + max := u32(16384) + for _ in 0 .. rnd_count { + value := rand.u32n(max) + assert value >= 0 + assert value < max + } +} + +fn test_rand_u64n() { + max := u64(379091181005) + for _ in 0 .. rnd_count { + value := rand.u64n(max) + assert value >= 0 + assert value < max + } +} + +fn test_rand_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for _ in 0 .. rnd_count { + value := rand.u32_in_range(min, max) + assert value >= min + assert value < max + } +} + +fn test_rand_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for _ in 0 .. rnd_count { + value := rand.u64_in_range(min, max) + assert value >= min + assert value < max + } +} + +fn test_rand_intn() { + max := 2525642 + for _ in 0 .. rnd_count { + value := rand.intn(max) + assert value >= 0 + assert value < max + } +} + +fn test_rand_i64n() { + max := i64(3246727724653636) + for _ in 0 .. rnd_count { + value := rand.i64n(max) + assert value >= 0 + assert value < max + } +} + +fn test_rand_int_in_range() { + min := -4252 + max := 23054962 + for _ in 0 .. rnd_count { + value := rand.int_in_range(min, max) + assert value >= min + assert value < max + } +} + +fn test_rand_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for _ in 0 .. rnd_count { + value := rand.i64_in_range(min, max) + assert value >= min + assert value < max + } +} + +fn test_rand_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for _ in 0 .. rnd_count { + value := rand.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } +} + +fn test_rand_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for _ in 0 .. rnd_count { + value := rand.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } +} + +fn test_rand_f32() { + for _ in 0 .. rnd_count { + value := rand.f32() + assert value >= 0.0 + assert value < 1.0 + } +} + +fn test_rand_f64() { + for _ in 0 .. rnd_count { + value := rand.f64() + assert value >= 0.0 + assert value < 1.0 + } +} + +fn test_rand_f32n() { + max := f32(357.0) + for _ in 0 .. rnd_count { + value := rand.f32n(max) + assert value >= 0.0 + assert value < max + } +} + +fn test_rand_f64n() { + max := f64(1.52e6) + for _ in 0 .. rnd_count { + value := rand.f64n(max) + assert value >= 0.0 + assert value < max + } +} + +fn test_rand_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for _ in 0 .. rnd_count { + value := rand.f32_in_range(min, max) + assert value >= min + assert value < max + } +} + +fn test_rand_f64_in_range() { + min := f64(-548.7) + max := f64(5015.2) + for _ in 0 .. rnd_count { + value := rand.f64_in_range(min, max) + assert value >= min + assert value < max + } +} + +fn test_rand_byte() { + mut all := []byte{} + for _ in 0 .. 256 { + x := rand.byte() + assert x >= 0 + assert x <= 255 + all << x + } + all.sort(a < b) + assert all[0] != all[255] + assert all[0] != all[128] +} + +const ( + string_count = 25 +) + +fn test_rand_string_from_set() { + sets := [ + '0123456789', + 'qwertyuiop', + 'abcdefghijklmnopqrstuvwxyz', + ] + for charset in sets { + for _ in 0 .. string_count { + len := rand.intn(rnd_count) + str := rand.string_from_set(charset, len) + assert str.len == len + for character in str { + position := charset.index(character.ascii_str()) or { -1 } + assert position > -1 + } + } + } +} + +fn test_rand_string() { + rand.seed([u32(0), 1]) + outputs := [ + 'rzJfVBJgvAyCNpEdXIteDQezg', + 'AJOeswgoelDOCfcrSUWzVPjeL', + 'NQfKauQqsXYXSUMFPGnXXPJIn', + 'vfBGUKbpLoBMQVYXfkvRplWih', + 'aYHLjMJqvUJmJJHGxEnrEmQGl', + 'rBJXkQZcembAteaRFoxXmECJo', + 'HYVLfHmDOCTlSbiSzHrsAIaBH', + 'zgOiwyISjLSdLGhLzJsSKHVBi', + 'UiAtobWXGcHsEtgzuNatxfkoI', + 'NisnYlffJgFEcIdcgzWcGjnHy', + ] + for output in outputs { + assert rand.string(25) == output + } +} + +fn test_rand_hex() { + rand.seed([u32(0), 1]) + outputs := [ + 'fc30e495deee09e008e15ffc3', + '4320efa837788397fb59b28f4', + '4995210abf33b6765c240ce62', + 'f3d20dbe0a8aa6b9c88cd1f6f', + '8d7d58b256ab00213dd519cf7', + 'fa2251284bc20a21eff48127c', + '5fef90cdc0c37143117599092', + '2a6170531c76dfb50c54126bc', + 'a686dfd536042d1c1a9afdaf4', + '7f12013f6e1177e2d63726de3', + ] + for output in outputs { + assert rand.hex(25) == output + } +} + +fn test_rand_ascii() { + rand.seed([u32(0), 1]) + outputs := [ + "2Z:&PeD'V;9=mn\$C>yKg'DIr%", + 'Ub7ix,}>I=QJki{%FHKv&K', + '1WStRylMO|p.R~qqRtr&AOEsd', + 'yka> 32 ^ (ctime & 0x0000_0000_FFFF_FFFF)) + mut seed_data := []u32{cap: count} + for _ in 0 .. count { + seed = nr_next(seed) + seed_data << nr_next(seed) + } + return seed_data +} + +// time_seed_32 returns a 32-bit seed generated from system time. +[inline] +pub fn time_seed_32() u32 { + return time_seed_array(1)[0] +} + +// time_seed_64 returns a 64-bit seed generated from system time. +[inline] +pub fn time_seed_64() u64 { + seed_data := time_seed_array(2) + lower := u64(seed_data[0]) + upper := u64(seed_data[1]) + return lower | (upper << 32) +} diff --git a/v_windows/v/vlib/rand/splitmix64/splitmix64.v b/v_windows/v/vlib/rand/splitmix64/splitmix64.v new file mode 100644 index 0000000..d3cb9d1 --- /dev/null +++ b/v_windows/v/vlib/rand/splitmix64/splitmix64.v @@ -0,0 +1,225 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module splitmix64 + +import rand.seed +import rand.constants + +// SplitMix64RNG ported from http://xoshiro.di.unimi.it/splitmix64.c +pub struct SplitMix64RNG { +mut: + state u64 = seed.time_seed_64() + has_extra bool + extra u32 +} + +// seed sets the seed of the accepting SplitMix64RNG to the given data +// in little-endian format (i.e. lower 32 bits are in [0] and higher 32 bits in [1]). +pub fn (mut rng SplitMix64RNG) seed(seed_data []u32) { + if seed_data.len != 2 { + eprintln('SplitMix64RNG needs 2 32-bit unsigned integers as the seed.') + exit(1) + } + rng.state = seed_data[0] | (u64(seed_data[1]) << 32) + rng.has_extra = false +} + +// u32 updates the PRNG state and returns the next pseudorandom `u32`. +[inline] +pub fn (mut rng SplitMix64RNG) u32() u32 { + if rng.has_extra { + rng.has_extra = false + return rng.extra + } + full_value := rng.u64() + lower := u32(full_value & constants.lower_mask) + upper := u32(full_value >> 32) + rng.extra = upper + rng.has_extra = true + return lower +} + +// u64 updates the PRNG state and returns the next pseudorandom `u64`. +[inline] +pub fn (mut rng SplitMix64RNG) u64() u64 { + rng.state += (0x9e3779b97f4a7c15) + mut z := rng.state + z = (z ^ ((z >> u64(30)))) * (0xbf58476d1ce4e5b9) + z = (z ^ ((z >> u64(27)))) * (0x94d049bb133111eb) + return z ^ (z >> (31)) +} + +// u32n returns a pseudorandom `u32` less than `bound`. +[inline] +pub fn (mut rng SplitMix64RNG) u32n(bound u32) u32 { + // This function is kept similar to the u64 version + if bound == 0 { + eprintln('max must be non-zero') + exit(1) + } + threshold := -bound % bound + for { + r := rng.u32() + if r >= threshold { + return r % bound + } + } + return u32(0) +} + +// u64n returns a pseudorandom `u64` less than `bound`. +[inline] +pub fn (mut rng SplitMix64RNG) u64n(bound u64) u64 { + // See pcg32.v for explanation of comment. This algorithm + // existed before the refactoring. + if bound == 0 { + eprintln('max must be non-zero') + exit(1) + } + threshold := -bound % bound + for { + r := rng.u64() + if r >= threshold { + return r % bound + } + } + return u64(0) +} + +// u32n returns a pseudorandom `u32` value that is guaranteed to be in range `[min, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) u32_in_range(min u32, max u32) u32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.u32n(max - min) +} + +// u64n returns a pseudorandom `u64` value that is guaranteed to be in range `[min, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) u64_in_range(min u64, max u64) u64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.u64n(max - min) +} + +// int returns a pseudorandom 32-bit (possibly negative) `int`. +[inline] +pub fn (mut rng SplitMix64RNG) int() int { + return int(rng.u32()) +} + +// i64 returns a pseudorandom 64-bit (possibly negative) `i64`. +[inline] +pub fn (mut rng SplitMix64RNG) i64() i64 { + return i64(rng.u64()) +} + +// int31 returns a positive pseudorandom 31-bit `int`. +[inline] +pub fn (mut rng SplitMix64RNG) int31() int { + return int(rng.u32() & constants.u31_mask) // Set the 32nd bit to 0. +} + +// int63 returns a positive pseudorandom 63-bit `i64`. +[inline] +pub fn (mut rng SplitMix64RNG) int63() i64 { + return i64(rng.u64() & constants.u63_mask) // Set the 64th bit to 0. +} + +// intn returns a pseudorandom `int` in range `[0, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) intn(max int) int { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return int(rng.u32n(u32(max))) +} + +// i64n returns a pseudorandom `i64` in range `[0, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) i64n(max i64) i64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return i64(rng.u64n(u64(max))) +} + +// int_in_range returns a pseudorandom `int` in range `[min, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) int_in_range(min int, max int) int { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + // This supports negative ranges like [-10, -5) because the difference is positive + return min + rng.intn(max - min) +} + +// i64_in_range returns a pseudorandom `i64` in range `[min, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) i64_in_range(min i64, max i64) i64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.i64n(max - min) +} + +// f32 returns a pseudorandom `f32` value in range `[0, 1)`. +[inline] +pub fn (mut rng SplitMix64RNG) f32() f32 { + return f32(rng.u32()) / constants.max_u32_as_f32 +} + +// f64 returns a pseudorandom `f64` value in range `[0, 1)`. +[inline] +pub fn (mut rng SplitMix64RNG) f64() f64 { + return f64(rng.u64()) / constants.max_u64_as_f64 +} + +// f32n returns a pseudorandom `f32` value in range `[0, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) f32n(max f32) f32 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f32() * max +} + +// f64n returns a pseudorandom `f64` value in range `[0, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) f64n(max f64) f64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f64() * max +} + +// f32_in_range returns a pseudorandom `f32` in range `[min, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) f32_in_range(min f32, max f32) f32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.f32n(max - min) +} + +// i64_in_range returns a pseudorandom `i64` in range `[min, max)`. +[inline] +pub fn (mut rng SplitMix64RNG) f64_in_range(min f64, max f64) f64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.f64n(max - min) +} diff --git a/v_windows/v/vlib/rand/splitmix64/splitmix64_test.v b/v_windows/v/vlib/rand/splitmix64/splitmix64_test.v new file mode 100644 index 0000000..669da3c --- /dev/null +++ b/v_windows/v/vlib/rand/splitmix64/splitmix64_test.v @@ -0,0 +1,331 @@ +import math +import rand.splitmix64 +import rand.seed + +const ( + range_limit = 40 + value_count = 1000 + seeds = [[u32(42), 0], [u32(256), 0]] +) + +const ( + sample_size = 1000 + stats_epsilon = 0.05 + inv_sqrt_12 = 1.0 / math.sqrt(12) +) + +fn gen_randoms(seed_data []u32, bound int) []u64 { + bound_u64 := u64(bound) + mut randoms := []u64{len: (20)} + mut rnd := splitmix64.SplitMix64RNG{} + rnd.seed(seed_data) + for i in 0 .. 20 { + randoms[i] = rnd.u64n(bound_u64) + } + return randoms +} + +fn test_splitmix64_reproducibility() { + seed_data := seed.time_seed_array(2) + randoms1 := gen_randoms(seed_data, 1000) + randoms2 := gen_randoms(seed_data, 1000) + assert randoms1.len == randoms2.len + len := randoms1.len + for i in 0 .. len { + assert randoms1[i] == randoms2[i] + } +} + +// TODO: use the `in` syntax and remove this function +// after generics has been completely implemented +fn found(value u64, arr []u64) bool { + for item in arr { + if value == item { + return true + } + } + return false +} + +fn test_splitmix64_variability() { + // If this test fails and if it is certainly not the implementation + // at fault, try changing the seed values. Repeated values are + // improbable but not impossible. + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + mut values := []u64{cap: value_count} + for i in 0 .. value_count { + value := rng.u64() + assert !found(value, values) + assert values.len == i + values << value + } + } +} + +fn check_uniformity_u64(mut rng splitmix64.SplitMix64RNG, range u64) { + range_f64 := f64(range) + expected_mean := range_f64 / 2.0 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := f64(rng.u64n(range)) - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := range_f64 * inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_splitmix64_uniformity_u64() { + ranges := [14019545, 80240, 130] + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for range in ranges { + check_uniformity_u64(mut rng, u64(range)) + } + } +} + +fn check_uniformity_f64(mut rng splitmix64.SplitMix64RNG) { + expected_mean := 0.5 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := rng.f64() - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_splitmix64_uniformity_f64() { + // The f64 version + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + check_uniformity_f64(mut rng) + } +} + +fn test_splitmix64_u32n() { + max := u32(16384) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_splitmix64_u64n() { + max := u64(379091181005) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_splitmix64_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_splitmix64_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_splitmix64_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } + } +} + +fn test_splitmix64_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } + } +} + +fn test_splitmix64_intn() { + max := 2525642 + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.intn(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_splitmix64_i64n() { + max := i64(3246727724653636) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_splitmix64_int_in_range() { + min := -4252 + max := 230549862 + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_splitmix64_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_splitmix64_f32() { + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_splitmix64_f64() { + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_splitmix64_f32n() { + max := f32(357.0) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_splitmix64_f64n() { + max := 1.52e6 + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_splitmix64_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_splitmix64_f64_in_range() { + min := -548.7 + max := 5015.2 + for seed in seeds { + mut rng := splitmix64.SplitMix64RNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64_in_range(min, max) + assert value >= min + assert value < max + } + } +} diff --git a/v_windows/v/vlib/rand/sys/system_rng.c.v b/v_windows/v/vlib/rand/sys/system_rng.c.v new file mode 100644 index 0000000..f1c701d --- /dev/null +++ b/v_windows/v/vlib/rand/sys/system_rng.c.v @@ -0,0 +1,275 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module sys + +import math.bits +import rand.seed +import rand.constants + +// Implementation note: +// ==================== +// C.rand returns a pseudorandom integer from 0 (inclusive) to C.RAND_MAX (exclusive) +// C.rand() is okay to use within its defined range. +// (See: https://web.archive.org/web/20180801210127/http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx) +// The problem is, this value varies with the libc implementation. On windows, +// for example, RAND_MAX is usually a measly 32767, whereas on (newer) linux it's generally +// 2147483647. The repetition period also varies wildly. In order to provide more entropy +// without altering the underlying algorithm too much, this implementation simply +// requests for more random bits until the necessary width for the integers is achieved. +const ( + rand_limit = u64(C.RAND_MAX) + rand_bitsize = bits.len_64(rand_limit) + u32_iter_count = calculate_iterations_for(32) + u64_iter_count = calculate_iterations_for(64) +) + +fn calculate_iterations_for(bits int) int { + base := bits / sys.rand_bitsize + extra := if bits % sys.rand_bitsize == 0 { 0 } else { 1 } + return base + extra +} + +// SysRNG is the PRNG provided by default in the libc implementiation that V uses. +pub struct SysRNG { +mut: + seed u32 = seed.time_seed_32() +} + +// r.seed() sets the seed of the accepting SysRNG to the given data. +pub fn (mut r SysRNG) seed(seed_data []u32) { + if seed_data.len != 1 { + eprintln('SysRNG needs one 32-bit unsigned integer as the seed.') + exit(1) + } + r.seed = seed_data[0] + C.srand(r.seed) +} + +// r.default_rand() exposes the default behavior of the system's RNG +// (equivalent to calling C.rand()). Recommended for testing/comparison +// b/w V and other languages using libc and not for regular use. +// This is also a one-off feature of SysRNG, similar to the global seed +// situation. Other generators will not have this. +[inline] +pub fn (r SysRNG) default_rand() int { + return C.rand() +} + +// r.u32() returns a pseudorandom u32 value less than 2^32 +[inline] +pub fn (r SysRNG) u32() u32 { + mut result := u32(C.rand()) + for i in 1 .. sys.u32_iter_count { + result = result ^ (u32(C.rand()) << (sys.rand_bitsize * i)) + } + return result +} + +// r.u64() returns a pseudorandom u64 value less than 2^64 +[inline] +pub fn (r SysRNG) u64() u64 { + mut result := u64(C.rand()) + for i in 1 .. sys.u64_iter_count { + result = result ^ (u64(C.rand()) << (sys.rand_bitsize * i)) + } + return result +} + +// r.u32n(max) returns a pseudorandom u32 value that is guaranteed to be less than max +[inline] +pub fn (r SysRNG) u32n(max u32) u32 { + if max == 0 { + eprintln('max must be positive integer') + exit(1) + } + // Owing to the pigeon-hole principle, we can't simply do + // val := rng.u32() % max. + // It'll wreck the properties of the distribution unless + // max evenly divides 2^32. So we divide evenly to + // the closest power of two. Then we loop until we find + // an int in the required range + bit_len := bits.len_32(max) + if bit_len == 32 { + for { + value := r.u32() + if value < max { + return value + } + } + } else { + mask := (u32(1) << (bit_len + 1)) - 1 + for { + value := r.u32() & mask + if value < max { + return value + } + } + } + return u32(0) +} + +// r.u64n(max) returns a pseudorandom u64 value that is guaranteed to be less than max +[inline] +pub fn (r SysRNG) u64n(max u64) u64 { + if max == 0 { + eprintln('max must be positive integer') + exit(1) + } + // Similar procedure for u64s + bit_len := bits.len_64(max) + if bit_len == 64 { + for { + value := r.u64() + if value < max { + return value + } + } + } else { + mask := (u64(1) << (bit_len + 1)) - 1 + for { + value := r.u64() & mask + if value < max { + return value + } + } + } + return u64(0) +} + +// r.u32n(min, max) returns a pseudorandom u32 value that is guaranteed to be in [min, max) +[inline] +pub fn (r SysRNG) u32_in_range(min u32, max u32) u32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + r.u32n(max - min) +} + +// r.u64n(min, max) returns a pseudorandom u64 value that is guaranteed to be in [min, max) +[inline] +pub fn (r SysRNG) u64_in_range(min u64, max u64) u64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + r.u64n(max - min) +} + +// r.int() returns a pseudorandom 32-bit int (which may be negative) +[inline] +pub fn (r SysRNG) int() int { + return int(r.u32()) +} + +// r.i64() returns a pseudorandom 64-bit i64 (which may be negative) +[inline] +pub fn (r SysRNG) i64() i64 { + return i64(r.u64()) +} + +// r.int31() returns a pseudorandom 31-bit int which is non-negative +[inline] +pub fn (r SysRNG) int31() int { + return int(r.u32() & constants.u31_mask) // Set the 32nd bit to 0. +} + +// r.int63() returns a pseudorandom 63-bit int which is non-negative +[inline] +pub fn (r SysRNG) int63() i64 { + return i64(r.u64() & constants.u63_mask) // Set the 64th bit to 0. +} + +// r.intn(max) returns a pseudorandom int that lies in [0, max) +[inline] +pub fn (r SysRNG) intn(max int) int { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return int(r.u32n(u32(max))) +} + +// r.i64n(max) returns a pseudorandom i64 that lies in [0, max) +[inline] +pub fn (r SysRNG) i64n(max i64) i64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return i64(r.u64n(u64(max))) +} + +// r.int_in_range(min, max) returns a pseudorandom int that lies in [min, max) +[inline] +pub fn (r SysRNG) int_in_range(min int, max int) int { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + // This supports negative ranges like [-10, -5) because the difference is positive + return min + r.intn(max - min) +} + +// r.i64_in_range(min, max) returns a pseudorandom i64 that lies in [min, max) +[inline] +pub fn (r SysRNG) i64_in_range(min i64, max i64) i64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + r.i64n(max - min) +} + +// r.f32() returns a pseudorandom f32 value between 0.0 (inclusive) and 1.0 (exclusive) i.e [0, 1) +[inline] +pub fn (r SysRNG) f32() f32 { + return f32(r.u32()) / constants.max_u32_as_f32 +} + +// r.f64() returns a pseudorandom f64 value between 0.0 (inclusive) and 1.0 (exclusive) i.e [0, 1) +[inline] +pub fn (r SysRNG) f64() f64 { + return f64(r.u64()) / constants.max_u64_as_f64 +} + +// r.f32n() returns a pseudorandom f32 value in [0, max) +[inline] +pub fn (r SysRNG) f32n(max f32) f32 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return r.f32() * max +} + +// r.f64n() returns a pseudorandom f64 value in [0, max) +[inline] +pub fn (r SysRNG) f64n(max f64) f64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return r.f64() * max +} + +// r.f32_in_range(min, max) returns a pseudorandom f32 that lies in [min, max) +[inline] +pub fn (r SysRNG) f32_in_range(min f32, max f32) f32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + r.f32n(max - min) +} + +// r.i64_in_range(min, max) returns a pseudorandom i64 that lies in [min, max) +[inline] +pub fn (r SysRNG) f64_in_range(min f64, max f64) f64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + r.f64n(max - min) +} diff --git a/v_windows/v/vlib/rand/sys/system_rng.js.v b/v_windows/v/vlib/rand/sys/system_rng.js.v new file mode 100644 index 0000000..496794d --- /dev/null +++ b/v_windows/v/vlib/rand/sys/system_rng.js.v @@ -0,0 +1,15 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module sys + +// Until there's a portable, JS has a seeded way to produce random numbers +// and not just Math.random(), use any of the existing implementations +// as the System's RNG +type SysRNG = WyRandRNG + +// In the JS version, we simply return the same int as is normally generated. +[inline] +pub fn (r SysRNG) default_rand() int { + return r.int() +} diff --git a/v_windows/v/vlib/rand/sys/system_rng_test.v b/v_windows/v/vlib/rand/sys/system_rng_test.v new file mode 100644 index 0000000..638ed10 --- /dev/null +++ b/v_windows/v/vlib/rand/sys/system_rng_test.v @@ -0,0 +1,354 @@ +import math +import rand.sys + +const ( + range_limit = 40 + value_count = 1000 + seeds = [u32(42), 256] +) + +const ( + sample_size = 1000 + stats_epsilon = 0.05 + inv_sqrt_12 = 1.0 / math.sqrt(12) +) + +fn get_n_randoms(n int, r sys.SysRNG) []int { + mut ints := []int{cap: n} + for _ in 0 .. n { + ints << r.int() + } + return ints +} + +fn test_sys_rng_reproducibility() { + // Note that C.srand() sets the seed globally. + // So the order of seeding matters. It is recommended + // to obtain all necessary data first, then set the + // seed for another batch of data. + for seed in seeds { + seed_data := [seed] + mut r1 := sys.SysRNG{} + mut r2 := sys.SysRNG{} + r1.seed(seed_data) + ints1 := get_n_randoms(value_count, r1) + r2.seed(seed_data) + ints2 := get_n_randoms(value_count, r2) + assert ints1 == ints2 + } +} + +// TODO: use the `in` syntax and remove this function +// after generics has been completely implemented +fn found(value u64, arr []u64) bool { + for item in arr { + if value == item { + return true + } + } + return false +} + +fn test_sys_rng_variability() { + // If this test fails and if it is certainly not the implementation + // at fault, try changing the seed values. Repeated values are + // improbable but not impossible. + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + mut values := []u64{cap: value_count} + for i in 0 .. value_count { + value := rng.u64() + assert !found(value, values) + assert values.len == i + values << value + } + } +} + +fn check_uniformity_u64(rng sys.SysRNG, range u64) { + range_f64 := f64(range) + expected_mean := range_f64 / 2.0 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := f64(rng.u64n(range)) - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := range_f64 * inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_sys_rng_uniformity_u64() { + // This assumes that C.rand() produces uniform results to begin with. + // If the failure persists, report an issue on GitHub + ranges := [14019545, 80240, 130] + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for range in ranges { + check_uniformity_u64(rng, u64(range)) + } + } +} + +fn check_uniformity_f64(rng sys.SysRNG) { + expected_mean := 0.5 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := rng.f64() - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_sys_rng_uniformity_f64() { + // The f64 version + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + check_uniformity_f64(rng) + } +} + +fn test_sys_rng_u32n() { + max := u32(16384) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.u32n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_sys_rng_u64n() { + max := u64(379091181005) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.u64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_sys_rng_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.u32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_sys_rng_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.u64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_sys_rng_intn() { + max := 2525642 + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.intn(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_sys_rng_i64n() { + max := i64(3246727724653636) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.i64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_sys_rng_int_in_range() { + min := -4252 + max := 23054962 + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.int_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_sys_rng_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.i64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_sys_rng_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } + } +} + +fn test_sys_rng_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } + } +} + +fn test_sys_rng_f32() { + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.f32() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_sys_rng_f64() { + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.f64() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_sys_rng_f32n() { + max := f32(357.0) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.f32n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_sys_rng_f64n() { + max := 1.52e6 + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.f64n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_sys_rng_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.f32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_sys_rng_f64_in_range() { + min := -548.7 + max := 5015.2 + for seed in seeds { + seed_data := [seed] + mut rng := sys.SysRNG{} + rng.seed(seed_data) + for _ in 0 .. range_limit { + value := rng.f64_in_range(min, max) + assert value >= min + assert value < max + } + } +} diff --git a/v_windows/v/vlib/rand/util/util.v b/v_windows/v/vlib/rand/util/util.v new file mode 100644 index 0000000..e1c30ca --- /dev/null +++ b/v_windows/v/vlib/rand/util/util.v @@ -0,0 +1,52 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module util + +import rand + +// sample_nr returns a sample of the array without replacement. This means the indices cannot repeat and it restricts the sample size to be less than or equal to the size of the given array. Note that if the array has repeating elements, then the sample may have repeats as well. +pub fn sample_nr(array []T, k int) []T { + n := array.len + if k > n { + panic('Cannot sample $k elements without replacement from a $n-element array.') + } + mut results := []T{len: k} + mut indices := []int{len: n} + // Initialize with all indices + // temporary workaround for issue #10343 + for i in 0 .. indices.len { + indices[i] = i + } + shuffle(mut indices, k) + for i in 0 .. k { + results[i] = array[indices[i]] + } + return results +} + +// sample_r returns a sample of the array with replacement. This means the elements can repeat and the size of the sample may exceed the size of the array +pub fn sample_r(array []T, k int) []T { + n := array.len + mut results := []T{len: k} + for i in 0 .. k { + results[i] = array[rand.intn(n)] + } + return results +} + +// shuffle randomizes the first `n` items of an array in place (all if `n` is 0) +[direct_array_access] +pub fn shuffle(mut a []T, n int) { + if n < 0 || n > a.len { + panic("argument 'n' must be in range [0, a.len]") + } + cnt := if n == 0 { a.len - 1 } else { n } + for i in 0 .. cnt { + x := rand.int_in_range(i, a.len) + // swap + a_i := a[i] + a[i] = a[x] + a[x] = a_i + } +} diff --git a/v_windows/v/vlib/rand/util/util_test.v b/v_windows/v/vlib/rand/util/util_test.v new file mode 100644 index 0000000..f92e70b --- /dev/null +++ b/v_windows/v/vlib/rand/util/util_test.v @@ -0,0 +1,57 @@ +import rand +import rand.util + +fn test_sample_nr() { + lengths := [1, 3, 4, 5, 6, 7] + a := ['one', 'two', 'three', 'four', 'five', 'six', 'seven'] + for length in lengths { + b := util.sample_nr(a, length) + assert b.len == length + for element in b { + assert element in a + // make sure every element occurs once + mut count := 0 + for e in b { + if e == element { + count++ + } + } + assert count == 1 + } + } +} + +fn test_sample_r() { + k := 20 + a := ['heads', 'tails'] + b := util.sample_r(a, k) + assert b.len == k + for element in b { + assert element in a + } +} + +fn test_shuffle() { + rand.seed([u32(1), 2]) // set seed to produce same results in order + a := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] + mut b := a.clone() + mut c := a.clone() + util.shuffle(mut b, 0) + util.shuffle(mut c, 0) + assert b == [6, 4, 5, 1, 9, 2, 10, 3, 8, 7] + assert c == [1, 6, 5, 8, 7, 2, 10, 9, 3, 4] + // test shuffling a slice + mut d := a.clone() + util.shuffle(mut d[..5], 0) + assert d == [5, 2, 1, 3, 4, 6, 7, 8, 9, 10] + assert d[5..] == a[5..] + // test shuffling n items + mut e := a.clone() + util.shuffle(mut e, 5) + assert e[..5] == [10, 3, 1, 8, 4] + assert e[5..] == [6, 7, 5, 9, 2] + // test shuffling empty array + mut f := a[..0] + util.shuffle(mut f, 0) + assert f == []int{} +} diff --git a/v_windows/v/vlib/rand/wyrand/wyrand.v b/v_windows/v/vlib/rand/wyrand/wyrand.v new file mode 100644 index 0000000..22b71af --- /dev/null +++ b/v_windows/v/vlib/rand/wyrand/wyrand.v @@ -0,0 +1,252 @@ +// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved. +// Use of this source code is governed by an MIT license +// that can be found in the LICENSE file. +module wyrand + +import math.bits +import rand.seed +import rand.constants +import hash + +// Redefinition of some constants that we will need for pseudorandom number generation. +const ( + wyp0 = u64(0xa0761d6478bd642f) + wyp1 = u64(0xe7037ed1a0b428db) +) + +// WyRandRNG is a RNG based on the WyHash hashing algorithm. +pub struct WyRandRNG { +mut: + state u64 = seed.time_seed_64() + has_extra bool + extra u32 +} + +// seed sets the seed, needs only two `u32`s in little-endian format as [lower, higher]. +pub fn (mut rng WyRandRNG) seed(seed_data []u32) { + if seed_data.len != 2 { + eprintln('WyRandRNG needs 2 32-bit unsigned integers as the seed.') + exit(1) + } + rng.state = seed_data[0] | (u64(seed_data[1]) << 32) + rng.has_extra = false +} + +// u32 updates the PRNG state and returns the next pseudorandom `u32`. +[inline] +pub fn (mut rng WyRandRNG) u32() u32 { + if rng.has_extra { + rng.has_extra = false + return rng.extra + } + full_value := rng.u64() + lower := u32(full_value & constants.lower_mask) + upper := u32(full_value >> 32) + rng.extra = upper + rng.has_extra = true + return lower +} + +// u64 updates the PRNG state and returns the next pseudorandom `u64`. +[inline] +pub fn (mut rng WyRandRNG) u64() u64 { + unsafe { + mut seed1 := rng.state + seed1 += wyrand.wyp0 + rng.state = seed1 + return hash.wymum(seed1 ^ wyrand.wyp1, seed1) + } + return 0 +} + +// u32n returns a pseudorandom `u32` less than `max`. +[inline] +pub fn (mut rng WyRandRNG) u32n(max u32) u32 { + if max == 0 { + eprintln('max must be positive integer') + exit(1) + } + // Check SysRNG in system_rng.c.v for explanation + bit_len := bits.len_32(max) + if bit_len == 32 { + for { + value := rng.u32() + if value < max { + return value + } + } + } else { + mask := (u32(1) << (bit_len + 1)) - 1 + for { + value := rng.u32() & mask + if value < max { + return value + } + } + } + return u32(0) +} + +// u64n returns a pseudorandom `u64` less than `max`. +[inline] +pub fn (mut rng WyRandRNG) u64n(max u64) u64 { + if max == 0 { + eprintln('max must be positive integer') + exit(1) + } + bit_len := bits.len_64(max) + if bit_len == 64 { + for { + value := rng.u64() + if value < max { + return value + } + } + } else { + mask := (u64(1) << (bit_len + 1)) - 1 + for { + value := rng.u64() & mask + if value < max { + return value + } + } + } + return u64(0) +} + +// u32n returns a pseudorandom `u32` value that is guaranteed to be in range `[min, max)`. +[inline] +pub fn (mut rng WyRandRNG) u32_in_range(min u32, max u32) u32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.u32n(max - min) +} + +// u64n returns a pseudorandom `u64` value that is guaranteed to be in range `[min, max)`. +[inline] +pub fn (mut rng WyRandRNG) u64_in_range(min u64, max u64) u64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.u64n(max - min) +} + +// int returns a (possibly negative) pseudorandom 32-bit `int`. +[inline] +pub fn (mut rng WyRandRNG) int() int { + return int(rng.u32()) +} + +// i64 returns a (possibly negative) pseudorandom 64-bit `i64`. +[inline] +pub fn (mut rng WyRandRNG) i64() i64 { + return i64(rng.u64()) +} + +// int31 returns a positive pseudorandom 31-bit `int`. +[inline] +pub fn (mut rng WyRandRNG) int31() int { + return int(rng.u32() & constants.u31_mask) // Set the 32nd bit to 0. +} + +// int63 returns a positive pseudorandom 63-bit `i64`. +[inline] +pub fn (mut rng WyRandRNG) int63() i64 { + return i64(rng.u64() & constants.u63_mask) // Set the 64th bit to 0. +} + +// intn returns a pseudorandom `int` in range `[0, max)`. +[inline] +pub fn (mut rng WyRandRNG) intn(max int) int { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return int(rng.u32n(u32(max))) +} + +// i64n returns a pseudorandom int that lies in `[0, max)`. +[inline] +pub fn (mut rng WyRandRNG) i64n(max i64) i64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return i64(rng.u64n(u64(max))) +} + +// int_in_range returns a pseudorandom `int` in range `[min, max)`. +[inline] +pub fn (mut rng WyRandRNG) int_in_range(min int, max int) int { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + // This supports negative ranges like [-10, -5) because the difference is positive + return min + rng.intn(max - min) +} + +// i64_in_range returns a pseudorandom `i64` in range `[min, max)`. +[inline] +pub fn (mut rng WyRandRNG) i64_in_range(min i64, max i64) i64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.i64n(max - min) +} + +// f32 returns a pseudorandom `f32` value in range `[0, 1)`. +[inline] +pub fn (mut rng WyRandRNG) f32() f32 { + return f32(rng.u32()) / constants.max_u32_as_f32 +} + +// f64 returns a pseudorandom `f64` value in range `[0, 1)`. +[inline] +pub fn (mut rng WyRandRNG) f64() f64 { + return f64(rng.u64()) / constants.max_u64_as_f64 +} + +// f32n returns a pseudorandom `f32` value in range `[0, max)`. +[inline] +pub fn (mut rng WyRandRNG) f32n(max f32) f32 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f32() * max +} + +// f64n returns a pseudorandom `f64` value in range `[0, max)`. +[inline] +pub fn (mut rng WyRandRNG) f64n(max f64) f64 { + if max <= 0 { + eprintln('max has to be positive.') + exit(1) + } + return rng.f64() * max +} + +// f32_in_range returns a pseudorandom `f32` in range `[min, max)`. +[inline] +pub fn (mut rng WyRandRNG) f32_in_range(min f32, max f32) f32 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.f32n(max - min) +} + +// i64_in_range returns a pseudorandom `i64` in range `[min, max)`. +[inline] +pub fn (mut rng WyRandRNG) f64_in_range(min f64, max f64) f64 { + if max <= min { + eprintln('max must be greater than min') + exit(1) + } + return min + rng.f64n(max - min) +} diff --git a/v_windows/v/vlib/rand/wyrand/wyrand_test.v b/v_windows/v/vlib/rand/wyrand/wyrand_test.v new file mode 100644 index 0000000..4cdfdb6 --- /dev/null +++ b/v_windows/v/vlib/rand/wyrand/wyrand_test.v @@ -0,0 +1,331 @@ +import math +import rand.seed +import rand.wyrand + +const ( + range_limit = 40 + value_count = 1000 + seeds = [[u32(42), 0], [u32(256), 0]] +) + +const ( + sample_size = 1000 + stats_epsilon = 0.05 + inv_sqrt_12 = 1.0 / math.sqrt(12) +) + +fn gen_randoms(seed_data []u32, bound int) []u64 { + bound_u64 := u64(bound) + mut randoms := []u64{len: (20)} + mut rnd := wyrand.WyRandRNG{} + rnd.seed(seed_data) + for i in 0 .. 20 { + randoms[i] = rnd.u64n(bound_u64) + } + return randoms +} + +fn test_wyrand_reproducibility() { + seed_data := seed.time_seed_array(2) + randoms1 := gen_randoms(seed_data, 1000) + randoms2 := gen_randoms(seed_data, 1000) + assert randoms1.len == randoms2.len + len := randoms1.len + for i in 0 .. len { + assert randoms1[i] == randoms2[i] + } +} + +// TODO: use the `in` syntax and remove this function +// after generics has been completely implemented +fn found(value u64, arr []u64) bool { + for item in arr { + if value == item { + return true + } + } + return false +} + +fn test_wyrand_variability() { + // If this test fails and if it is certainly not the implementation + // at fault, try changing the seed values. Repeated values are + // improbable but not impossible. + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + mut values := []u64{cap: value_count} + for i in 0 .. value_count { + value := rng.u64() + assert !found(value, values) + assert values.len == i + values << value + } + } +} + +fn check_uniformity_u64(mut rng wyrand.WyRandRNG, range u64) { + range_f64 := f64(range) + expected_mean := range_f64 / 2.0 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := f64(rng.u64n(range)) - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := range_f64 * inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_wyrand_uniformity_u64() { + ranges := [14019545, 80240, 130] + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for range in ranges { + check_uniformity_u64(mut rng, u64(range)) + } + } +} + +fn check_uniformity_f64(mut rng wyrand.WyRandRNG) { + expected_mean := 0.5 + mut variance := 0.0 + for _ in 0 .. sample_size { + diff := rng.f64() - expected_mean + variance += diff * diff + } + variance /= sample_size - 1 + sigma := math.sqrt(variance) + expected_sigma := inv_sqrt_12 + error := (sigma - expected_sigma) / expected_sigma + assert math.abs(error) < stats_epsilon +} + +fn test_wyrand_uniformity_f64() { + // The f64 version + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + check_uniformity_f64(mut rng) + } +} + +fn test_wyrand_u32n() { + max := u32(16384) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_wyrand_u64n() { + max := u64(379091181005) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_wyrand_u32_in_range() { + max := u32(484468466) + min := u32(316846) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_wyrand_u64_in_range() { + max := u64(216468454685163) + min := u64(6848646868) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.u64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_wyrand_int31() { + max_u31 := int(0x7FFFFFFF) + sign_mask := int(0x80000000) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int31() + assert value >= 0 + assert value <= max_u31 + // This statement ensures that the sign bit is zero + assert (value & sign_mask) == 0 + } + } +} + +fn test_wyrand_int63() { + max_u63 := i64(0x7FFFFFFFFFFFFFFF) + sign_mask := i64(0x8000000000000000) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int63() + assert value >= 0 + assert value <= max_u63 + assert (value & sign_mask) == 0 + } + } +} + +fn test_wyrand_intn() { + max := 2525642 + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.intn(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_wyrand_i64n() { + max := i64(3246727724653636) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64n(max) + assert value >= 0 + assert value < max + } + } +} + +fn test_wyrand_int_in_range() { + min := -4252 + max := 1034 + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.int_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_wyrand_i64_in_range() { + min := i64(-24095) + max := i64(324058) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.i64_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_wyrand_f32() { + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_wyrand_f64() { + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64() + assert value >= 0.0 + assert value < 1.0 + } + } +} + +fn test_wyrand_f32n() { + max := f32(357.0) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_wyrand_f64n() { + max := 1.52e6 + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64n(max) + assert value >= 0.0 + assert value < max + } + } +} + +fn test_wyrand_f32_in_range() { + min := f32(-24.0) + max := f32(125.0) + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f32_in_range(min, max) + assert value >= min + assert value < max + } + } +} + +fn test_wyrand_f64_in_range() { + min := -548.7 + max := 5015.2 + for seed in seeds { + mut rng := wyrand.WyRandRNG{} + rng.seed(seed) + for _ in 0 .. range_limit { + value := rng.f64_in_range(min, max) + assert value >= min + assert value < max + } + } +} -- cgit v1.2.3