Scalacheck number generator between 0 <= x < 2^64

Question

I'm trying to right a good number generator that covers uint64_t in C. Here is what I have so far.

def uInt64s : Gen[BigInt] = Gen.choose(0,64).map(pow2(_) - 1)

It is a good start, but it only generates numbers 2^n - 1. Is there a more effective way to generate random BigInts while preserving the number range 0 <= n < 2^64?

Answer 1

Okay, maybe I am missing something here, but isn't it as simple as this?

def uInt64s : Gen[BigInt] = Gen.chooseNum(Long.MinValue,Long.MaxValue)
                               .map(x => BigInt(x) + BigInt(2).pow(63))

Longs already have the correct number of bits - just adding 2^63 so Long.MinValue becomes 0 and Long.MaxValue becomes 2^64 - 1. And doing the addition with BigInts of course.

---

I was curious about the distribution of generated values. Apparently the distribution of chooseNum is not uniform, since it prefers special values, but the edge cases for Longs are probably also interesting for UInt64s:

/** Generates numbers within the given inclusive range, with
  *  extra weight on zero, +/- unity, both extremities, and any special
  *  numbers provided. The special numbers must lie within the given range,
  *  otherwise they won't be included. */
def chooseNum[T](minT: T, maxT: T, specials: T*)(

Answer 2

With ScalaCheck...

Generating a number from 0..Long.MaxValue is easy.

Generating an unsigned long from 0..Long.MaxValue..2^64-1 is not so easy.

   Tried:

   ❌ Gen.chooseNum(BigInt(0),BigInt(2).pow(64)-1)

        Does not work: At this time there is not an implicit defined for BigInt.

   ❌ Arbitrary.arbBigInt.arbitrary

       Does not work: It's type BigInt but still limited to the range of signed Long.

   ✔ Generate a Long as BigInt and shift left arbitrarily to make an UINT64

       Works: Taking Rickard Nilsson's, ScalaCheck code as a guide this passed the test.

This is what I came up with:

// Generate a long and map to type BigInt
def genBigInt : Gen[BigInt] = Gen.chooseNum(0,Long.MaxValue) map (x => BigInt(x))

// Take genBigInt and shift-left a chooseNum(0,64) of positions
def genUInt64 : Gen[BigInt] = for { bi <- genBigInt; n <- Gen.chooseNum(0,64); x = (bi << n) if x >= 0 && x < BigInt(2).pow(64) } yield x

...

// Use the generator, genUInt64()

As noted, Scalacheck number generator between 0 <= x < 2^64, the distribution of the BigInts generated is not even. The preferred generator is @stholzm solution:

def genUInt64b : Gen[BigInt] =
  Gen.chooseNum(Long.MinValue,Long.MaxValue) map (x => 
    BigInt(x) + BigInt(2).pow(63))

it is simpler, the numbers fed to ScalaCheck will be more evenly distributed, it is faster, and it passes the tests.

Answer 3

A simpler and more efficient alternative to stholmz's answer is as follows:

val myGen = {
  val offset = -BigInt(Long.MinValue)
  Arbitrary.arbitrary[Long].map { BigInt(_) + offset }
}

1. Generate an arbitrary Long;
2. Convert it to a BigInt;
3. Add the appropriate offset, i.e. -BigInt(Long.MinValue)).

Tests in the REPL:

scala> myGen.sample
res0: Option[scala.math.BigInt] = Some(9223372036854775807)

scala> myGen.sample
res1: Option[scala.math.BigInt] = Some(12628207908230674671)

scala> myGen.sample
res2: Option[scala.math.BigInt] = Some(845964316914833060)

scala> myGen.sample
res3: Option[scala.math.BigInt] = Some(15120039215775627454)

scala> myGen.sample
res4: Option[scala.math.BigInt] = Some(0)

scala> myGen.sample
res5: Option[scala.math.BigInt] = Some(13652951502631572419)