3

I know arc4random() is considered to be one of the best options for randomness. But still, it tends to give obvious duplicates and repetitions at some times.

I thought of using the accelerometers to add some real randomness to the output of arc4random.Before I spend some weeks in developing a better solution: Which other solutions are available?

Proud Member
  • 40,078
  • 47
  • 146
  • 231
  • Whatever you do, don't make the mistake of (for example) adding two random numbers together to produce a "more random" one! All you're doing there is changing the distribution. – Fattie Feb 05 '11 at 15:56
  • Here is one of the most famous answers on stack overflow, which explains it, **with graphs** even! http://stackoverflow.com/questions/3956478/understanding-randomness – Fattie Feb 05 '11 at 16:18
  • My bad; thought of xor – which does indeed not change the randomness of the result. – Joey Feb 05 '11 at 17:22

5 Answers5

6

Duplicates and repetitions are expected from a random stream of numbers. Trying to add "more randomness" is not needed; arc4random already reads from /dev/urandom, which gathers entropy from various sources in the system.

Jesse Rusak
  • 56,530
  • 12
  • 101
  • 102
  • Also to note, that the repetitions and duplicates are likely in an application where he only draws numbers from a very small set, such as for dice. If he looked at the actual output of `arc4random()` then it's unlikely that he'd see any repetitions or duplicates. – Joey Feb 05 '11 at 15:22
  • @Joey: Since `arc4random()` outputs 32-bit values he'd expect to see a repeat after roughly 65000 outputs were generated. Is that "unlikely"? – President James K. Polk Feb 05 '11 at 15:48
  • GregS: Output word size is not equal to state size, therefore repetitions of the sequence are quite rare (iirc arc4random had a period of 2^310) and 32 bit output size would mean 4 million, not 65k. – Joey Feb 05 '11 at 15:55
5

If you are trying to get rid of duplicates and repetitions (especially from arc4random sequences of less than millions in length), you will probably end up with a much less random sequence. It's a common human mental error to expect less repetitions in true randomness.

If you don't want duplicates for some purpose, you should do a random sort of an array with no duplicate elements, as in a card shuffle.

hotpaw2
  • 70,107
  • 14
  • 90
  • 153
4

In answer to your actual question, if you want something better than arc4random(), look in to the 

mersenne twister

which, in certain senses, is "better". Hope it helps!

I also urge anyone who is new to the topic to read one of the most famous answers on stack overflow, which explains distributions nicely, with graphs even!

Understanding "randomness"

"Never, ever add or multiply random numbers in an attempt to get 'better' randomness," is the short version.

Community
  • 1
  • 1
Fattie
  • 27,874
  • 70
  • 431
  • 719
2

IF you wish to cycle through your list "seemingly" randomly and avoid repeating any item ... use arc4random() and after each item has been viewed, removed it from list. When list runs dry, reload it.

Ex:

if (!self.dictionaryValues) {
[self loadList];

} else {

NSMutableDictionary *unusedValueList = [[NSMutableDictionary alloc] initWithDictionary:self.dictionaryValues];

int random = arc4random()%[self.dictionaryValues count]; // note, crashes on nil;
int i=0;
for (NSString *key in self.dictionaryValues) {
        i++;
        if (i == random) {
            NSLog(@"MATCH! on key=%@", key);
            [unusedValueList removeObjectForKey:key];
        }
}
self.dictionaryValues = nil;
self.dictionaryValues = unusedValueList;

}

hope this helps!

Sean of GoSEAN.org
  • 46
  • 1
0

I had a long answer here, but I'm just going to link to this. Because it basically sums up everything that's wrong about trying to make random numbers 'more random'

http://thedailywtf.com/Articles/More-Entropy,-Please.aspx

lxt
  • 31,146
  • 5
  • 78
  • 83