The fastest random number Generator

Question

I'm intending to implement a random number generator via Swift 3. I have three different methods for generating an integer (between 0 and 50000) ten thousand times non-stop.

Do these generators use the same math principles of generating a value or not?

What generator is less CPU and RAM intensive at runtime (having 10000 iterations)?

method A:

var generator: Int = random() % 50000

method B:

let generator = Int(arc4random_uniform(50000))

method C:

import GameKit
let number: [Int] = [0, 1, 2... 50000]

func generator() -> Int {
    let random = GKRandomSource.sharedRandom().nextIntWithUpperBound(number.count)
    return number[random]
}

Even if you get a detailed answer about this, surely you would still benchmark, would be easy to setup and test. — Alex K., Oct 18 '16 at 11:57
In method c, why don't you just return the result of `nextIntWithUpperBound(...)`? — Palle, Oct 18 '16 at 11:59
Before implementing it I would like to understand a "nature" of each one. — Andy Jazz, Oct 18 '16 at 12:00
They are not using the same principles and they will behave different in regards to quality and speed (e.g. A will generate worse numbers than B). But as always: stick to the documentations within your programming language! — sascha, Oct 18 '16 at 12:08
@Palle I'd like to use a func generator() in case array has a specific random order of numbers. But you are right, generally there's no special need to use a func. — Andy Jazz, Oct 18 '16 at 12:21

score 4 · Accepted Answer · edited May 23 '17 at 12:16

All of these are pretty well documented, and most have published source code.

var generator: Int = random() % 50000

Well, first of all, this is modulo biased, so it certainly won't be equivalent to a proper uniform random number. The docs for random explain it:

The random() function uses a non-linear, additive feedback, random number generator, employing a default table of size 31 long integers. It returns successive pseudo-random numbers in the range from 0 to (2**31)-1. The period of this random number generator is very large, approximately 16*((2**31)-1).

But you can look at the full implementation and documentation in Apple's source code for libc.

Contrast the documentation for arc4random_uniform (which does not have modulo bias):

These functions use a cryptographic pseudo-random number generator to generate high quality random bytes very quickly. One data pool is used for all consumers in a process, so that consumption under program flow can act as additional stirring. The subsystem is re-seeded from the kernel random number subsystem on a regular basis, and also upon fork(2).

And the source code is also available. The important thing to note from arc4random_uniform is that it avoids modulo bias by adjusting the modulo correctly and then generating random numbers until it is in the correct range. In principle this could require generating an unlimited number of random values; in practice it is incredibly rare that it would need to generate more than one, and rare-to-the-point-of-unbelievable that it would generate more than that.

GKRandomSource.sharedRandom() is also well documented:

The system random source shares state with the arc4random family of C functions. Generating random numbers with this source modifies the outcome of future calls to those functions, and calling those functions modifies the sequence of random values generated by this source. As such, this source is neither deterministic nor independent—use it only for trivial gameplay mechanics that do not rely on those attributes.

For performance, you would expect random() to be fastest since it never seeds itself from the system entropy pool, and so it also will not reduce the entropy in the system (though arc4random only does this periodically, I believe around every 1.5MB or so of random bytes generated; not for every value). But as with all things performance, you must profile. Of course since random() does not reseed itself it is less random than arc4random, which is itself less random than the source of entropy in the system (/dev/random).

When in doubt, if you have GameplayKit available, use it. Apple selected the implementation of sharedRandom() based on what they think is going to work best in most cases. Otherwise use arc4random. But if you really need to minimize impact on the system for "pretty good" (but not cryptographic) random numbers, look at random. If you're willing to take "kinda random if you don't look at them too closely" numbers and have even less impact on the system, look at rand. And if you want almost no impact on the system (guaranteed O(1), inlineable), see XKCD's getRandomNumber().

It might also be of interest that arc4random can be slow when used from multiple threads, as observed here: [Performance of concurrent code using dispatch_group_async is MUCH slower than single-threaded version](http://stackoverflow.com/questions/23685920/performance-of-concurrent-code-using-dispatch-group-async-is-much-slower-than-si). — Martin R, Oct 18 '16 at 13:18
Excellent point, @MartinR. One way around this is to read a large amount of random data into a buffer (`arc4random_buf`) since this only locks one time. Then slice up the random values and hand them to your various threads. A similar technique can be used by reading directly from `/dev/random` (or using `SecRandomCopyBytes` which is the same thing) to generate high-quality random values, and then consume them over the life of your operation. This is obviously more complicated, but could greatly improve performance. — Rob Napier, Oct 18 '16 at 14:18

user3441734 · Answer 2 · 2016-11-02T17:04:08.603

Xorshift generators are among the fastest non-cryptographically-secure random number generators, requiring very small code and state.

an example of swift implementation of xorshift128+

func xorshift128plus(seed0 : UInt64, seed1 : UInt64) -> () -> UInt64 {
    var s0 = seed0
    var s1 = seed1
    if s0 == 0 && s1 == 0 {
        s1 =  1 // The state must be seeded so that it is not everywhere zero.    
    }

    return {
        var x = s0
        let y = s1
        s0 = y
        x ^= x << 23
        x ^= x >> 17
        x ^= y
        x ^= y >> 26
        s1 = x
        return s0 &+ s1
    }

}

// create random generator, seed as needed!!
let random = xorshift128plus(seed0: 0, seed1: 0)

for _ in 0..<100 {
// and use it later
    random()
}

to avoid modulo bias, you could use

func random_uniform(bound: UInt64)->UInt64 {
    var u: UInt64 = 0
    let b: UInt64 = (u &- bound) % bound
    repeat {
        u = random()
    } while u < b
    return u % bound
}

in your case

let r_number = random_uniform(bound: 5000) // r_number from interval 0..<5000

The fastest random number Generator

2 Answers2

Linked