Skip to content

Instantly share code, notes, and snippets.

@paulp
Created September 19, 2017 15:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save paulp/19cd4ee7a783a804b60c5912183be53a to your computer and use it in GitHub Desktop.
Save paulp/19cd4ee7a783a804b60c5912183be53a to your computer and use it in GitHub Desktop.
property("longs are evenly-distributed") =
forAll { (seed: Seed, b: Base) =>
val base = b.value
def countZeros(s0: Seed, i: Int, seen0: Int): Int =
if (i <= 0) seen0 else {
val (x, s1) = s0.long
val n = (x & 0x7fffffff).toInt % base
val seen = if (n == 0) seen0 + 1 else seen0
countZeros(s1, i - 1, seen)
}
val count = 10000
val mean = count.toDouble / base
val stdDev = Math.sqrt(mean * ((base.toDouble - 1) / base))
val delta = 5 * stdDev // 1 in 1.7M false positives
val zeros = countZeros(seed, count, 0)
(mean - delta) <= zeros && zeros <= (mean + delta)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment