Differences in our Seed.split implementation

[ghost]

I took some time today to read through the splittable random paper, and I noticed some differences between our implementation and theirs. Mainly, our split function creates and returns two Seed values, while in the paper there is only a single SplittableRandom created and also they shuffle the gamma value while we don't (p. 465). Is this correct? Does Hedgehog need both generated this way to operate properly?

Just trying to get my head wrapped around this. I want to start writing more documentation for these modules to help newcomers (and myself, apparently) understand them.

/cc @moodmosaic

[ghost]

I've translated the entire java code from the paper to rust, using a mutable pattern. It might help our discussion (I'm not-so-secretly working on a rust port).

pub struct SplittableRandom {
  seed: u64,
  gamma: u64,
}

impl SplittableRandom {
  pub fn from_seed(seed: u64) {
    Self::new(seed, GOLDEN_GAMMA);
  }

  fn new(seed: u64, gamma: u64) -> Self {
    assert!((gamma & 1) == 1, "gamma should always be odd.");

    Self {
      seed,
      gamma,
    }
  }

  pub fn seed(&self) -> u64 {
    self.seed
  }

  fn next(&self) -> Self {
    Self::new(self.seed + self.gamma, self.gamma)
  }

  pub fn random() -> Self {
    let seed = std::time::UNIX_EPOCH.elapsed().unwrap().as_nanos() as u64;

    Self::new(
      mix_u64(seed),
      mix_gamma(seed + GOLDEN_GAMMA),
    )
  }

  pub fn next_u64(&self) -> (Self, u64) {
    let rand = self.next();
    let seed = rand.seed();
    (rand, mix_u64(seed))
  }

  pub fn next_u32(&self) -> (Self, u32) {
    let rand = self.next();
    let seed = mix_u32(rand.seed());
    (rand, seed)
  }

  pub fn next_f64(&self) -> (Self, f64) {
    let (rand, seed) = self.next_u64();
    let seed = ((seed >> 11) as f64) * DOUBLE_ULP;
    (rand, seed)
  }

  pub fn split(&self) -> Self {
    let rand0 = self;
    let rand1 = rand0.next();
    let rand2 = rand1.next();

    let seed = mix_u64(rand1.seed());
    let gamma = mix_gamma(rand2.seed());

    Self::new(seed, gamma)
  }
}

const DOUBLE_ULP: f64 = 1.0 / ((1u64 << 53) as f64);
const GOLDEN_GAMMA: u64 = 0x9e3779b97f4a7c15; // odd

fn mix_u64(mut z: u64) -> u64 {
  z = (z ^ (z >> 33)) * 0xff51afd7ed558ccd;
  z = (z ^ (z >> 33)) * 0xc4ceb9fe1a85ec53;
  return z ^ (z >> 33);
}

fn mix_u32(mut z: u64) -> u32 {
  z = (z ^ (z >> 33)) * 0xff51afd7ed558ccd;
  z = (z ^ (z >> 33)) * 0xc4ceb9fe1a85ec53;
  return (z >> 32) as u32;
}

fn mix_u64_variant_13(mut z: u64) -> u64 {
  z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
  z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
  return z ^ (z >> 31);
}

fn mix_gamma(z: u64) -> u64 {
  let z = mix_u64_variant_13(z) | 1;
  let n = (z ^ (z >> 1)).count_ones();
  if n >= 24 {
    z ^ 0xaaaaaaaaaaaaaaaa
  } else {
    z
  }
}

[moodmosaic]

I'll have to refresh my memory. Keep in mind, the original paper's implementation isn't perfect: hedgehogqa/haskell-hedgehog@39b15b9

[moodmosaic]

I've put more effort in Seed.hs (as you may tell from that long commit message also). I've been trying to keep both versions in sync though. I'm not sure if we need to rewrite Seed.fs however. Where do you see the issue exactly?

[moodmosaic]

Many thanks for looking into this, btw 🍻

[ghost]

Where do you see the issue exactly?

I don't necessarily see issues, just differences. Particularly, we aren't calling mixGamma anywhere in the F# Seed.split.

[moodmosaic]

I don't remember that off the top of my head (around 2017 is when I went through the SplitMix paper). I'd have to look in the paper again. Happy to open an issue for it (here, in the .NET/F# version).

[ghost]

I don't remember that off the top of my head (around 2017 is when I went through the SplitMix paper). I'd have to look in the paper again.

But you're supposed to know everything! 😅 I don't think we're too far off the mark on the F# side. I've got a branch on my fork called seed-fixes that addresses any differences, and I've also updated some of the doc comments so they are more in line with Haskell Hedgehog.

Happy to open an issue for it (here, in the .NET/F# version).

We can open an issue and/or I can open a PR with my branch.

[ghost]

This was addressed in #362.