Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Swift - Seeding arc4random_uniform? Or alternative?

Let me start by stating what I'm trying to accomplish:

  1. I need to randomly generate a set of numbers within a range
  2. I would like those numbers to be somewhat uniformly distributed
  3. I need to be able to seed the random number generation such that, given a seed, the resulting random numbers will always be the same.

After experimenting quite a bit with drand48(), rand() and arc4random(), I have currently settled on using rand() for obtaining a random number, and srand() for seeding. Here is a small example simplified from what I am doing:

let seed: UInt32 = 10
srand(seed)
let start = 0
let end = 100
let randomNumber = Double(rand()) % (end + 1 - start) + start

This works. Given the same seed, the same random number comes out. Performing multiple randomNumber calculations results in multiple, different random numbers coming out. Re-seeding via srand starts the "randomness" over again.

The only downside is rand() is not uniformly distributed. Indeed I pretty much always end up with a set of numbers that are linearly increasing for the most part.

It sounds like arc4random_uniform will generate more of a uniform random output, however from my research it isn't possible to seed arc4random, as it seeds itself the first time it is invoked and isn't necessarily "designed" to be seeded externally.

So my question; is there a better alternative to srand() / rand() that will still give me the same outputs for a given seed, but those outputs are more uniformly distributed?

Thanks, - Adam

like image 543
Adam Eisfeld Avatar asked Jul 31 '16 00:07

Adam Eisfeld


2 Answers

I know "GameKit" sounds like it's just for games, but it contains a serious random number generation system. I suggest you take a look at GKMersenneTwisterRandomSource and GKRandomDistribution. The GKMersenneTwisterRandomSource takes a random seed (if you so choose) and the GKRandomDistribution class implements a Uniform Distribution. Used together, they do exactly what you're looking for.

import GameKit

// The Mersenne Twister is a very good algorithm for generating random
// numbers, plus you can give it a seed...    
let rs = GKMersenneTwisterRandomSource()
rs.seed = 1780680306855649768

// Use the random source and a lowest and highest value to create a 
// GKRandomDistribution object that will provide the random numbers.   
let rd = GKRandomDistribution(randomSource: rs, lowestValue: 0, highestValue: 100)

// Now generate 10 numbers in the range 0...100:    
for _ in 1...10 {
    print(rd.nextInt())
}

print("---")

// Let's set the seed back to the starting value, and print the same 10
// random numbers.    
rs.seed = 1780680306855649768
for _ in 1...10 {
    print(rd.nextInt())
}
like image 137
vacawama Avatar answered Oct 01 '22 06:10

vacawama


It turns out, srand / rand combined do suit my needs, the issue causing the results to not appear "uniformly distributed" was a bug in my own logic.

For reference, essentially what I was doing was this (in reality it was much more complex, but for demonstration purposes):

let start = 0
let end = 100

for x in 0..<10 {

   let seed = UInt32(x)
   srand(seed)
   let randomNumber = Double(rand()) % (end + 1 - start) + start

   // Do something with random number

}

Written in the much more simpler form above, the problem becomes obvious. I was re-seeding every iteration of the loop, and the seed value was just incrementing linearly. Because of this, the random results were also incrementing linearly.

The simple solution is to not re-seed each loop iteration, but to instead seed once before the loop. For example:

let start = 0
let end = 100
let seed = UInt32(100)
srand(seed)

for x in 0..<10 {

   let randomNumber = Double(rand()) % (end + 1 - start) + start

   // Do something with random number

}

With this simple change, the resulting values do appear to be somewhat uniformly distributed across the 0 to 100 range used in the example. I can't be sure if there is a "more uniform" way of doing this, but I assume there is since I have read arc4random is "far superior" to drand / rand / erand / etc functions for uniform random number generation, but at least this seems to be working for my needs.

I will leave this question open for a while longer in the event that someone else comes up with a better approach to accomplishing what I am after.

like image 33
Adam Eisfeld Avatar answered Oct 01 '22 05:10

Adam Eisfeld