How Random Numbers Work In Swift

Before Swift 4.2, generating random numbers involved using raw C APIs. With the addition of the RandomNumberGenerator protocol in Swift 4.2, developers were graced with an easy way to generate random numbers. Let's see how to use the new APIs, but most importantly, how they are implemented inside the Swift compiler.

RandomNumberGenerator

Deep down, the generation of random numbers in Swift still works exactly like before. The difference is that Swift 4.2 introduced some nice abstractions on top of it in the form of protocols -- allowing you to create your own randomization algorithms if you need to.

The generation of random numbers in Swift begins with RandomNumberGenerator -- a protocol that does nothing but generate random UInt64 values:

public protocol RandomNumberGenerator {
    mutating func next() -> UInt64
}

Types that can access/generate random values are meant to receive an implementation of this protocol, generate a (possibly very big) random number and use it to determine which value to return (for example, by calculating randomNumber % range.upperBound).

The Swift Standard Library provides an all-purpose implementation of RandomNumberGenerator called SystemRandomNumberGenerator, which pulls a random number from the innards of the compiler.

public struct SystemRandomNumberGenerator: RandomNumberGenerator {
  public mutating func next() -> UInt64 {
      var random: UInt64 = 0
      swift_stdlib_random(&random, MemoryLayout<UInt64>.size)
      return random
  }
}

The actual random mechanism used differs by platform, but is guaranteed to be type-safe in all of them. For Apple platforms, the compiler uses arc4random_buf (whose functionality requires a separate article):

#if defined(__APPLE__)

SWIFT_RUNTIME_STDLIB_API
void swift::swift_stdlib_random(void *buf, __swift_size_t nbytes) {
  arc4random_buf(buf, nbytes);
}

Swift Random APIs

From Swift 4.2, numeric types like Int, Float and Bool can generate random numbers through the new .random(in:) APIs:

let randomInt = Int.random(in: 1..<5)
let randomFloat = Float.random(in: 1..<10)
let randomBool = Bool.random()

All of these APIs support taking a RandomNumberGenerator argument, but you're allowed to not provide one, as the compiler is rigged to use SystemRandomNumberGenerator by default. For example, here's how the default API for Bool is defined:

public static func random() -> Bool {
    var g = SystemRandomNumberGenerator()
    return Bool.random(using: &g)
}

Bool.random()

In the case of Bool, the full implementation of the API will get the raw UInt64 value from the generator, bit shift it to the right 17 times, and return true if the first bit of the resulting value is 0.

public static func random<T: RandomNumberGenerator>(
    using generator: inout T
) -> Bool {
    return (generator.next() >> 17) & 1 == 0
}

The reason the value is shifted exactly 17 times is that (some) weak RNGs have better randomness properties in the middle bits over the low/high bits, and the Swift team felt like protecting us from APIs that decided to use these RNGs instead of the default SystemRandomNumberGenerator. Before the PR that implemented this improvement, Bool.random() used to simply return generator.next() % 2 == 0.

Int.random() and others

The implementation of the random API for other numeric types is similar to Bool, with the difference being how the value is pre/post-processed. For example, for ..< Int ranges, Swift calculates the distances between the bounds, generates a value, makes sure it's less than upperBound and adds lowerBound to it, resulting in a random value inside the requested range.

// Note: The actual implementation is slightly different than this
// because it treats compiler edge cases and uses some different types.
let delta = range.upperBound &- range.lowerBound
return range.lowerBound + generator.next(upperBound: delta)

An interesting note is that generator.next(upperBound: delta) isn't simply a value % delta calculation -- it uses Daniel Lemire’s “Fast Random Integer Generation in Interval” algorithm, which produces a higher quality result (for example, it avoids module bias).

public mutating func next<T: FixedWidthInteger & UnsignedInteger>(
  upperBound: T
) -> T {
  var random: T = next()
  var m = random.multipliedFullWidth(by: upperBound)
  if m.low < upperBound {
    let t = (0 &- upperBound) % upperBound
    while m.low < t {
      random = next()
      m = random.multipliedFullWidth(by: upperBound)
    }
  }
  return m.high
}

A funny aspect of this algorithm is that it can, in theory, take forever to run as it has a while loop that continuously discards what it considers to be "low quality" values, but in reality, the odds of it being anything slower than "pretty much instant" are so low that you should never consider this.

randomElement()

To top it off, let's take a look at another API added in Swift 4.2: The randomElement() method for Collections, which returns a random element from the collection:

let string = ["Swift", "Rocks", "by", "Bruno", "Rocha"].randomElement()
// Bruno

randomElement() is defined as a Collection extension, and simply grabs a random index through the Int.random(in:) method that we spelunked previously.

public func randomElement<T: RandomNumberGenerator>(
  using generator: inout T
) -> Element? {
    guard !isEmpty else { return nil }
    let random = Int.random(in: 0 ..< count, using: &generator)
    let idx = index(startIndex, offsetBy: random)
    return self[idx]
}

Perhaps an interesting take here is that this is a global Collection extension, which means that this will work for any type of collection (usually, you would see something like this only for RandomAccessCollections). This also means that the runtime complexity of this method will vary depending on the collection, as count is only O(1) in RandomAccessCollections. In other types of collections, count is O(n).

References and Good Reads