# The quest for a perfect quasi-random sequence

We want a function that maps sequential values (entities concurrently living in a scene *usually* have ids that are sequential) into very different colors (the hue component of the color, to be specific)

What we are looking for is a so-called “low discrepancy” sequence. ie: a function `f`

such as for integers in a given range (eg: 101, 102, 103…), `f(i)`

returns a rational number in the [0..1] range, such as `|f(i) - f(i±1)| ≈ 0.5`

(maximum difference of images for neighboring preimages)

AHash is a good random hasher, but it has relatively high discrepancy, so we need something else. Known good low discrepancy sequences are:

#### The Van Der Corput sequence

```
fn van_der_corput(bits: u64) -> f32 {
let leading_zeros = if bits == 0 { 0 } else { bits.leading_zeros() };
let nominator = bits.reverse_bits() >> leading_zeros;
let denominator = bits.next_power_of_two();
nominator as f32 / denominator as f32
}
```

#### The Gold Kronecker sequence

Note that the implementation suggested in the linked post assumes floats, we have integers

```
fn gold_kronecker(bits: u64) -> f32 {
const U64_MAX_F: f32 = u64::MAX as f32;
// (u64::MAX / Φ) rounded down
const FRAC_U64MAX_GOLDEN_RATIO: u64 = 11400714819323198485;
bits.wrapping_mul(FRAC_U64MAX_GOLDEN_RATIO) as f32 / U64_MAX_F
}
```

### Comparison of the sequences

So they are both pretty good. Both only have a single (!) division and two `u64 as f32`

conversions.

- Both do not care much about the generation (consider that
`entity.to_bits()`

will usually be a value in the form ‘x·2³² + y’) - Kronecker is resilient to regular sequence (eg: 100, 102, 104, 106) while this kills Van Der Corput (consider that potentially one entity out of two spawned might be a mesh)

I made a small app to compare the two sequences, available at: https://gist.github.com/nicopap/5dd9bd6700c6a9a9cf90c9199941883e

At the top, we have Van Der Corput, at the bottom we have the Gold Kronecker. In the video, we spawn a vertical line at the position on screen where the x coordinate is the image of the sequence. The preimages are 1,2,3,4,… The ideal algorithm would always have the largest possible gap between each line (imagine the screen x coordinate as the color hue):

https://github.com/bevyengine/bevy/assets/26321040/349aa8f8-f669-43ba-9842-f9a46945e25c

Here, we repeat the experiment, but with with `entity.to_bits()`

instead of a sequence:

https://github.com/bevyengine/bevy/assets/26321040/516cea27-7135-4daa-a4e7-edfd1781d119

Notice how Van Der Corput tend to bunch the lines on a single side of the screen. This is because we always skip odd-numbered entities.

The kronecker sequence seems better, so I used it.