CODEWITHSUNDEEP
swiftrandom
albianto
albianto

Reputation: 4152

Array shuffle(using: RandomNumberGenerator) strange behavior

Since Xcode 11.4 the array doesn't get shuffled at all (regardless of the seed) when using the second implementation of the next function.

I don't get why, since both functions generate random numbers, even though the first only populates the least significant 32 bits of the random Int64.

You can try this minimal example in Swift Playgrounds, commenting out one of the two functions.

    import GameplayKit

    struct SeededGenerator: RandomNumberGenerator {
        static var shared: SeededGenerator?

        let seed: UInt64
        let generator: GKMersenneTwisterRandomSource

        init(seed: UInt64) {
            self.seed = seed
            generator = GKMersenneTwisterRandomSource(seed: seed)
        }

        // New alternative found to be working
        mutating func next() -> UInt64 {
            let next1 = UInt64(bitPattern: Int64(generator.nextInt()))
            let next2 = UInt64(bitPattern: Int64(generator.nextInt()))
            return next1 | (next2 << 32)
        }

        // Code previously in use that doesn't work anymore.
        mutating func next() -> UInt64 {
            return UInt64(bitPattern: Int64(abs(generator.nextInt())))
        }
    }

    var gen = SeededGenerator(seed: 234)

    var array = ["1", "2", "3"]
    array.shuffle(using: &gen)

Upvotes: 2

Views: 427

Answers (1)

Martin R
Martin R

Reputation: 539795

The problem is that the nextInt() method of all GKRandom types returns an integer value in the range [INT32_MIN, INT32_MAX], which means that your “non-working” implementation of next() returns 64-bit values with the high 32 bits equal to zero. This “violates” the requirement of the RandomNumberGenerator protocol that calls to next() must produce uniformly distributed 64-bit values.

In older Swift releases this might not have caused problems, but with the implementation of Lemire’s Nearly Divisionless Random Integer Generation on 64-bit Intel platforms this has the effect that Random.next(upperBound:) always returns zero:

var gen = SeededGenerator(seed: 234)
print((0..<20).map { _ in Int.random(in: 0..<10, using: &gen) })
// [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

As a consequence, the shuffle() method does not swap array elements at all.

Your alternative implementation of next() works because it fills both the low and the high 32 bits of the 64-bit random number.

Upvotes: 3

Related Questions