Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

arc4random() and arc4random_uniform() not really random?

I have been using arc4random() and arc4random_uniform() and I always had the feeling that they wasn't exactly random, for example, I was randomly choosing values from an Array but often the values that came out were the same when I generated them multiple times in a row, so today I thought that I would use an Xcode playground to see how these functions are behaving, so I first tests arc4random_uniform to generate a number between 0 and 4, so I used this algorithm :

import Cocoa

var number = 0

for i in 1...20 {
    number = Int(arc4random_uniform(5))
}

And I ran it several times, and here is how to values are evolving most of the time :
enter image description hereenter image description here

So as you can see the values are increasing and decreasing repeatedly, and once the values are at the maximum/minimum, they often stay at it during a certain time (see the first screenshot at the 5th step, the value stays at 3 during 6 steps, the problem is that it isn't at all unusual, the function actually behaves in that way most of the time in my tests.

Now, if we look at arc4random(), it's basically the same :
enter image description hereenter image description here

So here are my questions :

  • Why is this function behaving in this way ?
  • How to make it more random ?

Thank you.

EDIT :
Finally, I made two experiments that were surprising, the first one with a real dice :
enter image description here
What surprised me is that I wouldn't have said that it was random, since I was seeing the same sort of pattern that as described as non-random for arc4random() & arc4random_uniform(), so as Jean-Baptiste Yunès pointed out, humans aren't good to see if a sequence of numbers is really random.

I also wanted to do a more "scientific" experiment, so I made this algorithm :

import Foundation

var appeared = [0,0,0,0,0,0,0,0,0,0,0]
var numberOfGenerations = 1000

for _ in 1...numberOfGenerations {
    let randomNumber = Int(arc4random_uniform(11))
    appeared[randomNumber]++
}

for (number,numberOfTimes) in enumerate(appeared) {
    println("\(number) appeard \(numberOfTimes) times (\(Double(numberOfGenerations)/Double(numberOfTimes))%)")
}

To see how many times each number appeared, and effectively the numbers are randomly generated, for example, here is one output from the console :
0 appeared 99 times.
1 appeared 97 times.
2 appeared 78 times.
3 appeared 80 times.
4 appeared 87 times.
5 appeared 107 times.
6 appeared 86 times.
7 appeared 97 times.
8 appeared 100 times.
9 appeared 91 times.
10 appeared 78 times.

So it's definitely OK 😊

EDIT #2 : I made again the dice experiment with more rolls, and it's still as surprising to me :
enter image description here

like image 491
Pop Flamingo Avatar asked Jan 07 '15 06:01

Pop Flamingo


People also ask

Is arc4random random?

The arc4random() function returns pseudo-random numbers in the range of 0 to (2**32)-1, and therefore has twice the range of rand(3) and random(3).

What is the maximum possible value of r1 in this code INT r1 arc4random () 10?

The arc4random() function generates numbers between 0 and 4,294,967,295, giving a range of 2 to the power of 32 - 1, i.e., a lot.


2 Answers

A true random sequence of numbers cannot be generated by an algorithm. They can only produce pseudo-random sequence of numbers (something that looks like a random sequence). So depending on the algorithm chosen, the quality of the "randomness" may vary. The quality of arc4random() sequences is generally considered to have a good randomness.

You cannot analyze the randomness of a sequence visually... Humans are very bad to detect randomness! They tend to find some structure where there is no. Nothing really hurts in your diagrams (except the rare subsequence of 6 three in-a-row, but that is randomness, sometimes unusual things happens). You would be surprised if you had used a dice to generate a sequence and draw its graph. Beware that a sample of only 20 numbers cannot be seriously analyzed against its randomness, your need much bigger samples.

If you need some other kind of randomness, you can try to use /dev/random pseudo-file, which generate a random number each time you read in. The sequence is generated by a mix of algorithms and external physical events that ay happens in your computer.

like image 71
Jean-Baptiste Yunès Avatar answered Sep 28 '22 00:09

Jean-Baptiste Yunès


It depends on what you mean when you say random.

As stated in the comments, true randomness is clumpy. Long strings of repeats or close values are expected.

If this doesn't fit your requirement, then you need to better define your requirement.

Other options could include using a shuffle algorithm to dis-order things in an array, or use an low-discrepancy sequence algorithm to give a equal distribution of values.

like image 45
Jeffery Thomas Avatar answered Sep 28 '22 00:09

Jeffery Thomas