arc4random

This topic contains 37 replies, has 13 voices, and was last updated by  bigubosu 2 years, 3 months ago.

Viewing 25 posts - 1 through 25 (of 38 total)
Author Posts
Author Posts
April 5, 2010 at 12:18 am #220885

indy2005
@indy2005

Hi,

Could I just be clear that to use arc4random to generate a number from 0 to 10, it is (arc4random() % 11).

i.e. to go from 0 to X you arc4random to 0 to (X+1).

Seems to work, but have seen conflicting information on the web.

Regards

i

April 5, 2010 at 12:51 am #279009

liquidfire
Participant
@liquidfire

What you said is correct.

April 5, 2010 at 3:48 am #279010

Karl
@karl

Just be warned: arc4random is SLOW.

http://www.indieappsalliance.org/forum/viewtopic.php?f=10&t=13

April 5, 2010 at 8:33 am #279011

CJ
Moderator
@wiseganesha

@Karl thanks for the tip. I tried including the SFMT into my project but I get linker errors now:

Undefined symbols:
"gen_rand32()", referenced from:
.. list of files that used this.

"init_gen_rand(unsigned int)", referenced from:
.. my app delegate

I added the files to the Cocos2D static lib, which seems to work, except any place I reference the functions in my application it won’t link.

UPDATE: Solved. It was because I was nesting macros and unrelated to the actual code.

April 5, 2010 at 10:09 am #279012

CJ
Moderator
@wiseganesha

Oh, and I found this, which seems to be a good option as well:

http://en.wikipedia.org/wiki/Xorshift

April 5, 2010 at 3:44 pm #279013

indy2005
@indy2005

Hi,

I guess I dont need to worry too much about speed in this instance as it is to generate random Tetris style blocks, but I am concerned if I get an uneven distribution towards one end of the random number range…as arc4random is stated to

i

April 5, 2010 at 6:14 pm #279014

Karl
@karl

Using modulus will also bias your result, though it’s not very noticeable with small ranges.

Here’s how you guarantee a distribution as even as your RNG will allow:

double probability = get_random_uint32() / 4294967296.0;
double range = maxValue - minValue + 1;
return range * probability + minValue;

I ran some tests, and the performance difference between this solution and modulus are negligible.

April 5, 2010 at 6:16 pm #279015

Karl
@karl

Here’s an easy way to integrate SFMT into the cocos library for those who are interested:

First, I copied the whole SFMT directory into Support/SFMT (be sure to add it to the project, as well).

In ccMacros.h, I made some handy macros in case I ever decide to change implementations later. I also replaced CCRANDOM_MINUS1_1() and CCRANDOM_0_1():

#import "SFMT.h"

#define rng_seed(A) init_gen_rand(A)

#define rng_rand32() gen_rand32()

/// returns a random float between -1 and 1
//#define CCRANDOM_MINUS1_1() ((random() / (float)0x3fffffff )-1.0f)
#define CCRANDOM_MINUS1_1() ((gen_rand32() * (1.0/2147483647.0))-1.0f)

/// returns a random float between 0 and 1
//#define CCRANDOM_0_1() ((random() / (float)0x7fffffff ))
#define CCRANDOM_0_1() genrand_real1()

After that, there are some rand() calls to replace with rng_rand32() in CCGrid3dAction.m and CCTiledGridAction.m, as well as replacing srand() with rng_seed().

April 5, 2010 at 8:37 pm #279016

CJ
Moderator
@wiseganesha

@Karl thanks :)

Can you explain why you add 1 here:

double probability = get_random_uint32() / 4294967296.0;
double range = maxValue - minValue + 1;
return range * probability + minValue;

Here is what I have for random between two numbers (inclusive):

#define CCRANDOM_X_Y(__X__, __Y__) (((__Y__) - (__X__)) * (get_random_uint32() / (float)0xffffffff) + (__X__))

I did 100 test with range from 3 to 4 and the results never went over or under.

April 5, 2010 at 9:34 pm #279017

onedayitwillmake
Participant
@onedayitwillmake

Out of curiousity, if you seed random with the time at the beginning of your program, is it still considered a bad option?

I’m still using the built in cocos2d random macro after calling srandom(time(null)) in my game

April 5, 2010 at 9:46 pm #279018

Karl
@karl

Suppose you want a value from 10 to 20. That gives a range of 10 (actually, 11 discrete values).

If you multiply 10 by a probability ranging from 0.0 to 1.0, the only time it would fall on 10 would be when probability = 1.0. Basically, all values from 0-9 would have an equal chance of occurring, but 10 would only occur when you get exactly 1.0 (i.e. almost never).

If you add 1 to the range, you sidestep the issue. Now, 0-10 can occur with equal probability, and 11 will only occur on 1.0. Of course, you don’t want to ever see 11, but since I’m dividing by 4294967296 (max uint32 + 1) instead of 4294967295, the result of the division can never actually be 1.0 (though it will get damn close!).

April 5, 2010 at 9:48 pm #279019

Karl
@karl

@oneday: For games, seeding with time() is fine.

April 6, 2010 at 4:34 am #279020

CJ
Moderator
@wiseganesha

@karl that is certainly interesting, but shouldn’t every int returned by get_random_int32() be equally likely? and as such dividing the int by the range available would give you a float from 0.0 to 1.0 with even distribution including the end points? Thus following through to convert this 0-1 scale to an arbitrary range like 3-5 would return 4.7 just as often as 3.0 ?

April 6, 2010 at 5:31 am #279021

Karl
@karl

Every value in the range of 0 to 4294967295 is equally likely (well, given a perfect random number generator anyway!). As such, dividing the random number by 4294967295 will give a float from 0.0 to 1.0, evenly distributed as you said.

The issue is that C converts from float to int by clamping DOWN. So 0.99999999 is still 0 when you convert it to an integer.

Take, for example, the range 0 to 4. You want the values 0 or 1, 2, 3, or 4, with an even probability of each of those numbers resulting. So you take your random probability and multiply it by the range, which is 4 – 0 = 4.

When you convert the result to an integer, you get:

From 0.0 to 0.9999999 (p = 0.0 to 0.249999999) = 0

From 1.0 to 1.9999999 (p = 0.25 to 0.49999999) = 1

From 2.0 to 2.9999999 (p = 0.5 to 0.749999999) = 2

From 3.0 to 3.9999999 (p = 0.75 to 0.99999999) = 3

From 4.0 to 4.0 (p = 1.0 to 1.0) = 4

So the number 4 can ONLY result when the probability is 1.0, which will occur on average once in 4294967296 tries.

However, if you add 1 to the range, you get 5. Trying the probabilities again:

From 0.0 to 0.9999999 (p = 0.0 to 0.199999999) = 0

From 1.0 to 1.9999999 (p = 0.2 to 0.399999999) = 1

From 2.0 to 2.9999999 (p = 0.4 to 0.599999999) = 2

From 3.0 to 3.9999999 (p = 0.6 to 0.899999999) = 3

From 4.0 to 4.9999999 (p = 0.8 to 0.999999999) = 4

From 5.0 to 5.0 (p = 1.0 to 1.0) = 5

Now, there’s an even chance of any of the numbers 0, 1, 2, 3, or 4 occurring, but there’s also a 1 in 4294967296 chance of 5 occurring, which we don’t want. So instead of dividing the random integer value by 4294967295.0 (the maximum possible 32-bit unsigned integer value), we divide by 4294967296.0. Now, even if the random integer value is 4294967295, you’ll still only end up with a resulting probability calculation of 4294967295 / 4294967296.0 = 0.99999999976716935634613037109375. And so with this little trickery, we get a 20% chance of 0, 1, 2, 3, or 4 occurring, and absolutely no chance of 5.

There is an ever so tiny skew against the maximum number of the range occurring, but we’re talking a probability bias of 0.00000000023283064365386962890625 here, which is such a trivial amount that it can pretty much be ignored until you get to very large ranges of numbers.

April 6, 2010 at 5:42 am #279022

CJ
Moderator
@wiseganesha

Ok, I think I see now. You are talking about getting a random int in a range like 3-5, and I was talking about getting random float values in the range 3.0-5.0…. right?

Thanks :)

April 6, 2010 at 6:03 am #279023

Karl
@karl

Yeah. For floating point values a simple multiplication by the probability will do ;-)

April 6, 2010 at 3:28 pm #279024

Lam
Moderator
@lam

@Karl

I’ve learned so much from this thread haha. Thanks Karl you’ve boosted my experience points (in life) again. :D

The issue is that C converts from float to int by clamping DOWN.

So could we use a rounding function first before casting to an int to solve this issue and so the probabilities that we expect (25% of occurrence for 4 events {0,1,2,3} instead of a 20%)

I guess it really would be up to the user to know to round first before a cast but maybe that’s kind of like common sense when we deal with probabilities.

April 6, 2010 at 3:52 pm #279025

Karl
@karl

You could round manually, but that involves making a decision (using an IF statement), which will stall the CPU’s instruction pipeline 50% of the time. Overall performance would plummet.

April 6, 2010 at 4:12 pm #279026

indy2005
@indy2005

Hi

double probability = get_random_uint32() / 4294967296.0;
double range = maxValue - minValue + 1;
return range * probability + minValue;

…is this to complement SFMT, instead of SFMT. Is the above an alternative to arc4random?

Regards

i

April 6, 2010 at 5:56 pm #279027

Lam
Moderator
@lam

@Karl

Would this be a faster round? What are the inherit problems with:

int roundme(float probability)
{
return (int)(probability + 0.5f);
}

Hopefully it’s faster than a conditional if.

April 6, 2010 at 6:34 pm #279028

Karl
@karl

So you mean:

unsigned int getRandomValue(unsigned int minValue, unsigned int maxValue)
{
double probability = get_random_uint32() / 4294967296.0;
double range = maxValue - minValue + 1;
return roundme(range * probability) + minValue;
}

unsigned int roundme(float probability)
{
return (unsigned int)(probability + 0.5f);
}

In doing that, you guarantee that the first value in the range will have only half as much chance to occur as the rest. You also end up with bleed-over on the top end.

Continuing from the previous example:

From 0.5 to 0.9999999 (p = 0.0 to 0.099999999) = 0 (10% chance)

From 1.0 to 1.9999999 (p = 0.1 to 0.299999999) = 1 (20% chance)

From 2.0 to 2.9999999 (p = 0.3 to 0.499999999) = 2 (20% chance)

From 3.0 to 3.9999999 (p = 0.5 to 0.699999999) = 3 (20% chance)

From 4.0 to 4.9999999 (p = 0.7 to 0.899999999) = 4 (20% chance)

From 5.0 to 5.5 (p = 0.9 to 1.0) = 5 (10% chance)

April 6, 2010 at 6:42 pm #279029

Karl
@karl

@indy2005: That routine can be used with any random number generator that spits out values ranging from 0 to 4294967295 (0xffffffff). Just replace get_random_uint32() with a call to whatever RNG you choose.

April 6, 2010 at 7:06 pm #279030

indy2005
@indy2005

thanks,

…didnt help I was confusing RNG with “range” :-)

i

May 20, 2010 at 9:18 am #279031

ashmira
Participant
@ashlovemira

Karl actually i didnt understand here, how to be sure to add it to a project? and how to copy. i got error SFMT.h:No such file or directory.

First, I copied the whole SFMT directory into Support/SFMT (be sure to add it to the project, as well). Sorry for double posting.

Need your help. T.T

May 20, 2010 at 11:07 am #279032

Karl
@karl

Sure thing. The key is to make sure it gets added to the cocos2d library target rather than your application target.

Step 1: Drag the SFMT directory into “cocos2d/Suppport” in Finder (not in XCode).

Step 2: Drag from the place you just copied to (inside the cocos2d/Support directory of your project) into the “Support” group of your project in XCode.

Make sure “Copy items into destination folder” is UNCHECKED.

Under “Add to targets”, uncheck your application and check “cocos2d libraries”.

Once you do this, the project should look like this:

Step 3: Add [#import "SFMT.h"] to ccMacros.h:

Step 4: Change the cocos macros to use SFMT. I also like to add non-library-specific macros that point to SFMT.

Step 5: Use the code in your program.

Step 6: Compile and run!

Note: I sometimes get XCode issues where it still refuses to recognize that SFMT.h is there. If you get that problem, you can usually fix it using “Get Info” on the SFMT.h file and uncheck ALL targets (including cocos2d libraries). Normally you want the cocos library to be selected, but XCode is temperamental sometimes.

Viewing 25 posts - 1 through 25 (of 38 total)

You must be logged in to reply to this topic.