4 ms·

> You mean because of the modulo operator, presumably, and yes, the technically correct way to do it is to retry if the raw random number is larger than N*floor

> You mean because of the modulo operator, presumably, and yes, the technically correct way to do it is to retry if the raw random number is larger than N*floor(UINT32_MAX/N). Still, that's a pretty minor bug considering what a minor deviation from uniformity it causes. Yes, because of the modulo operator and this is not a minor thing in my opinion. Especially with small arrays his implementation will return the the 0th or 1st element much much more often than other elements. I think the correct way would be to use arc4random_uniform(...). > Yeah, this is a common mistake for people making "additions" frameworks, and it just strikes me as egotistical. When I was doing ObjC development, I'd even prefix my own private category methods, because hey, you never know. Yes. He even did create about 30 functions which use the CG-prefix.

mistercow 14y ago
Edit: I just realized for my math below I used 2^32 as UINT32_MAX instead of 2^32 - 1. The rest of my reasoning holds up though. >Especially with small arrays his implementation will return the the 0th or 1st element much much more often than other elements. Much, much more often? Correct me if my reasoning is wrong, but for a, say, 6 element array, this bug would make a difference less than 0.0000001% of the time ((UINT32_MAX%6)/UINT32_MAX). For a 3 element array, it would make a difference about 0.000000023% of the time. Maybe you mean by small "less than 100 elements", in which case the worst case is 96 elements, where it happens a whopping 0.0000015% of the time. Indeed, the problem is only pronounced for large arrays, because that's when there's an opportunity for UINT32_MAX%N to be large (since A%B < B). There is no case where the 0th and 1st element are significantly skewed ahead of everything else. The bias is characterized by the last few elements of the array being selected significantly less often, but the "significantly" part only kicks in for very big arrays. In fact, the first array length for which you will even see a difference 0.01% of the time would be 430,142 elements [ed: this holds up even adjusting UINT32_MAX to the correct value]. Considering that this is a framework intended to be used for iOS development, I think once your NSArray has grown that large, you might have more important fish to fry than worrying about a small bias in your randomization.
- LinaLauneBaer 14y ago
  You are correct. I have just checked my code that I used a couple of years ago to generate random numbers using %. I had the impression back then, when I then switched to arc4random_uniform that it works much better. It must have been something different or my perception tricks me. Nevertheless not knowing or caring about uniformly distributed random numbers and charging $1000/hours seems a bit strange. One could argue that % needs less CPU cycles but then again: Does this matter? Using arc4random_uniform makes your code much more readable etc. So from a pure code review standpoint of view I would argue that arc4random_uniform should be used if possible. Of course he might also not have used it because of compatibility reasons. Who knows. Btw: I would like to talk to you in private. How can I contact you?

mistercow 14y ago

Edit: I just realized for my math below I used 2^32 as UINT32_MAX instead of 2^32 - 1. The rest of my reasoning holds up though. >Especially with small arrays his implementation will return the the 0th or 1st element much much more often than other elements. Much, much more often? Correct me if my reasoning is wrong, but for a, say, 6 element array, this bug would make a difference less than 0.0000001% of the time ((UINT32_MAX%6)/UINT32_MAX). For a 3 element array, it would make a difference about 0.000000023% of the time. Maybe you mean by small "less than 100 elements", in which case the worst case is 96 elements, where it happens a whopping 0.0000015% of the time. Indeed, the problem is only pronounced for large arrays, because that's when there's an opportunity for UINT32_MAX%N to be large (since A%B < B). There is no case where the 0th and 1st element are significantly skewed ahead of everything else. The bias is characterized by the last few elements of the array being selected significantly less often, but the "significantly" part only kicks in for very big arrays. In fact, the first array length for which you will even see a difference 0.01% of the time would be 430,142 elements [ed: this holds up even adjusting UINT32_MAX to the correct value]. Considering that this is a framework intended to be used for iOS development, I think once your NSArray has grown that large, you might have more important fish to fry than worrying about a small bias in your randomization.

LinaLauneBaer 14y ago
You are correct. I have just checked my code that I used a couple of years ago to generate random numbers using %. I had the impression back then, when I then switched to arc4random_uniform that it works much better. It must have been something different or my perception tricks me. Nevertheless not knowing or caring about uniformly distributed random numbers and charging $1000/hours seems a bit strange. One could argue that % needs less CPU cycles but then again: Does this matter? Using arc4random_uniform makes your code much more readable etc. So from a pure code review standpoint of view I would argue that arc4random_uniform should be used if possible. Of course he might also not have used it because of compatibility reasons. Who knows. Btw: I would like to talk to you in private. How can I contact you?