# Crate rand_sequence

source ·`rand-unique`

crate instead## Expand description

## rand-sequence (deprecated for rand-unique)

Please note, **this crate has been renamed** in favour of rand-unique, which better describes the functionality of this crate. If you would like to take ownership of the `rand-sequence`

crate name, please raise a GitHub issue.

Deterministically generate a sequence of unique random numbers. A non-repeating pseudo-random number generator, directly index-able for the nth number in the sequence.

Not cryptographically secure. Complexity: O(1) time and space complexity for all operations.

Properties:

- The sequence is deterministic and repeatable for the same seeds.
- The sequence will only include each number once (every index has a unique output).
- 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.
- Note that once a number has appeared in the sequence, it will not appear again. Each value in this sequence is unique.

- Computing the value for any random index in the sequence is an O(1) operation.
`RandomSequence::n(index)`

returns the output for a given position in the sequence.

- Support for
`u8`

,`u16`

,`u32`

,`u64`

, and`usize`

. Outputs can be cast to`i8`

,`i16`

,`i32`

,`i64`

, and`isize`

respectively.

### Features

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.

### Example

```
use rand::rngs::OsRng;
use rand_sequence::{RandomSequence, RandomSequenceBuilder};
// Initialise a sequence from a random seed.
let config = RandomSequenceBuilder::<u64>::rand(&mut OsRng);
let mut sequence = 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));
// Unique across the entire type, with support for u8, u16, u32, and u64.
let sequence = RandomSequence::<u16>::rand(&mut OsRng);
let nums: std::collections::HashSet<u16> = (0..=u16::MAX)
.into_iter()
.map(|i| sequence.n(i))
.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();
```

### Output Distribution

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.

### How It Works

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)
}
```

### Sources

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

- Article: http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/
- Source: https://github.com/preshing/RandomSequence/blob/master/randomsequence.h

## Structs

- RandomSequenceDeprecatedGenerate a deterministic pseudo-random sequence of unique numbers.
- RandomSequenceBuilderDeprecatedThe configuration for RandomSequence, a random unique sequence generator.