Crates.io | rand-unique |

lib.rs | rand-unique |

version | 0.2.2 |

source | src |

created_at | 2023-11-02 22:07:41.218647 |

updated_at | 2023-11-03 16:45:29.400468 |

description | A no-std crate for generating random sequences of unique integers in O(1) time. |

homepage | |

repository | https://github.com/hoxxep/rand-unique |

max_upload_size | |

id | 1023620 |

size | 90,668 |

https://docs.rs/rand-unique

A no-std crate for generating sequences of unique random numbers in O(1) time and space. `RandomSequence`

is a non-repeating pseudo-random sequence generator, directly index-able for the nth number in the sequence.

Not cryptographically secure. No-std compatible.

Properties of each `RandomSequence`

:

**Unique:**The sequence will only include each number once; every index has a unique output.**Uniform:**The sequence is pseudo-uniformly distributed. Each number which has not yet appeared in the sequence has a roughly equal probability of being the next number in the sequence.**Fast:**Computing the value for any random index in the sequence is an O(1) operation in time and memory complexity.**Indexable:**`RandomSequence::n(index)`

returns the output for a given position in the sequence.**Integer Range:**Support for`u8`

,`u16`

,`u32`

,`u64`

, and`usize`

. Outputs can be cast to`i8`

,`i16`

,`i32`

,`i64`

, and`isize`

respectively.**Terminating and Wrapping:**Iterator usage of`RandomSequence::next()`

will terminate at the end of the sequence. Alternatively,`RandomSequence::wrapping_next()`

will wrap around to the start of the sequence when exhausted.**Deterministic:**The sequence is deterministic and repeatable for the same seeds.`RandomSequenceBuilder`

can be serialized with serde to store the sequence parameters. Must have the`serde`

feature enabled.`RandomSequenceBuilder::new(seed_base, seed_offset)`

can be used to instantiate with specific seeds.`RandomSequenceBuilder::rand(prng)`

can be used to instantiate with random seeds. Must have the`rand`

feature enabled.`RandomSequenceBuilder::into_iter()`

constructs a`RandomSequence`

with the parameters defined by the builder. Two builders configured the same will generate the same sequence, and so we can construct multiple iterators over the same sequence.

This crate is no-std compatible.

`default-features`

:`rand`

`rand`

: Enables the`rand(&mut RngCore)`

helper methods on`RandomSequenceBuilder`

and`RandomSequence`

to initialize with random seeds, which requires the`rand`

dependency. Can be omitted and instead manually provide seeds to the`RandomSequenceBuilder::seed()`

method to instantiate.`serde`

: Enables serde`Serlialize`

and`Deserialize`

support for`RandomSequenceBuilder`

, which requires the`serde`

dependency.

```
use std::collections::HashSet;
use rand::rngs::OsRng;
use rand_unique::{RandomSequence, RandomSequenceBuilder};
// Initialise a sequence from a random seed.
let config = RandomSequenceBuilder::<u16>::rand(&mut OsRng);
let mut sequence: RandomSequence<u16> = config.into_iter();
// Iterate over the sequence with next() and prev(), or index directly with n(i).
assert_eq!(sequence.next().unwrap(), sequence.n(0));
assert_eq!(sequence.next().unwrap(), sequence.n(1));
assert_eq!(sequence.next().unwrap(), sequence.n(2));
// Get the current index, if the sequence is not yet exhausted.
assert_eq!(sequence.index(), Some(3));
assert!(!sequence.exhausted());
// Initialise a new RandomSequence iterator over the same sequence.
let sequence_2 = config.into_iter();
assert_eq!(sequence_2.n(0), sequence.n(0));
assert_eq!(sequence_2.index(), Some(0));
// Consume the iterator, and show outputs are unique across the entire type.
// With support for u8, u16, u32, u64, and usize.
let nums: HashSet<u16> = sequence_2.collect();
assert_eq!(nums.len(), u16::MAX as usize + 1);
// Serialise the config to reproduce the same sequence later.
// Requires the "serde" feature to be enabled.
// let config = serde_json::to_string(&sequence.config).unwrap();
```

Future work could include a more rigorous analysis of the output distribution. For now, the following charts demonstrate the roughly uniform distribution for `RandomSequence<u16>`

.

Histogram visualisation of the `RandomSequence`

output distribution.

Visual scatter plot of the `RandomSequence`

output.

This non-repeating pseudo-random number generator works by creating a permutation function against the index in the sequence, herein referred to as `x`

. So for any position `x`

in the sequence, we want to deterministically compute a unique output number via function `n(x)`

, where comparing `n(x)`

and `n(x + 1)`

would appear randomly generated.

For any prime number $p$ which satisfies $p 3 \mod 4$, then for any input $x$, the operation $f(x) = x^2 \mod p$ will produce a unique number for each value of $x$ where $2x < p$.

Quadratic residue tends to cluster numbers together, and so we apply the quadratic residue permutation along with other permutation functions (*wrapping* addition and xor) to add further noise. Permutation functions are those with a direct 1-1 mapping for all inputs to outputs, where each input has a unique output.

In a simplified form, the permutation function is:

```
/// `p` is chosen to be the largest number satisfying:
/// - a prime number
/// - that satisfies p = 3 mod 4 (`p % 4 == 3`)
/// - that fits in the datatype chosen, in this example `u64`
const PRIME: u64 = 18446744073709551427;
/// Simplified example of the quadratic residue function, taking input `x` for prime `PRIME`.
fn permute_qpr(x: u64) -> u64 {
// we choose x to be the largest prime number of the type, and so there are a small handful
// of numbers in the datatype which are larger than p. We map them directly to themselves.
if x > PRIME {
return x;
}
// compute the residue, in the real method we're careful to avoid integer overflow, omitted here
// for clarity.
let residue = (x * x) % PRIME;
// the residue is unique for all x <= p/2; and so p-residue is also unique for x > p/2.
if x <= PRIME / 2 {
residue
} else {
PRIME - residue
}
}
/// Randomly selected variables to introduce further noise in the output generation.
const OFFSET_NOISE: u64 = 0x46790905682f0161;
const XOR_NOISE: u64 = 0x5bf0363546790905;
/// We can then use this permutation function [permute_qpr] to build our number generator `n(x)`.
fn n(x: u64) -> u64 {
// function sequence: permute_qpr, wrapping addition, xor, permute_qpr
// care is taken in the real implementation to use wrapping addition, omitted here for clarity.
permute_qpr((permute_qpr(x) + OFFSET_NOISE) ^ XOR_NOISE)
}
```

Based on the article by @preshing using quadratic prime residue: