Why the condition in the nonNegativeLessThan implementation works

In Chapter 6 of Functional Programming in Scala, when we’re trying to implement nonNegativeLessThan, the condition to accept the generated random number didn’t make sense to me, so I dug into it a bit more.

def nonNegativeLessThan(n: Int): Rand[Int] = {
  nonNegativeInt.flatMap { i =>
    val mod = i % n
    if (i + (n - 1) - mod >= 0)
      State.unit(mod)
    else
      nonNegativeLessThan(i)
  }

Suppose instead of the regular Int, we used a 4-bit integer instead, which overflows after 15.

We assume that the randomly generated numbers provided to flatMap will be between 0 and 15 (inclusive)

In this example, lets use n = 6. For the randomly generated numbers to be evenly distributed between 0 and 5 (inclusive), we need to retry if the randomly generated number is between 12 and 15 inclusive:

mod 0  1  2  3  4  5
    -----------------
    0  1  2  3  4  5
    6  7  8  9  10 11
    12 13 14 15 __ __  <== __ means it would have overflowed

We need to retry when the randomly generated number falls in the last row, so that generated numbers from nonNegativeLessThan will be evenly distributed between 0 and 5 (inclusive).

The condition i + ((n - 1) - mod) works because the number in the outer parentheses ((n + 1) - mod) is the number needed to increase any i to the last number in a row.

Examples:

• 6 + (6 - 1) - 0 = 11
• 9 + (6 - 1) - 3 = 11
• 13 + (6 - 1) - 1 = 17 (would have overflowed)
• 14 + (6 - 1) - 2 = 17 (would have overflowed)

If i % n = mod where i is the dividend and n is the divisor, i + n - mod will definitely round i up to the next multiple of n, so i + n - mod - 1 will round i up to just less than the next multiple of n.

Hence, if i, rounded up to just less than the next multiple of n, is still positive (no overflow happened), the original number i must not be higher than the largest multiple of n that fits in an Int.

Suppose now we use n = 4 instead:

mod 0  1  2  3
    ----------
    0  1  2  3
    4  5  6  7
    8  9  10 11
    12 13 14 15

Examples:

• 8 + (4 - 1) - 0 = 11 (no overflow, no need to retry)
• 10 + (4 - 1) - 2 = 11 (no overflow, no need to retry)
• 12 + (4 - 1) - 0 = 15 (no overflow, no need to retry)

If our condition had excluded the - 1 part, as in if the condition had been i + n - mod instead, then we would have retried for numbers 12 <= i <= 15, which would still result in a uniform distribution, but at a slight additional computation cost, since it wasn’t necessary to retry for numbers 12 <= i <= 15.