Math Puzzle: this one goes to 1.0

Your mission:
You have the following piece of code:

int GetIndex()
{
float rand = GetRandomNumber();
return NUM_ITEMS * rand;
}

... which you'd expect to return a value from 0 to NUM_ITEMS-1, giving a nice equal chance of picking any item from some list at random.

The question is this:

Most random number functions return a value from 0.0 to 0.999999999999999'. (Or, to look at it another way, 1-epsilon, where epsilon is the smallest possible floating point value that can be represented).

However, Joey Badrand (that scandalous cur) has come up with a random number function for your use which returns a value between 0.0 and 1.0! And you have no choice but to use it in your function.

Questions

  1. What does this do to your distribution, and why is it a bad thing?
  2. How do you fix your function so that the output of Joey's random number generator can be used to do the Right Thing?
About the author

Simon Cooke is an occasional video game developer, ex-freelance journalist, screenwriter, film-maker, musician, and software engineer in Seattle, WA.

The views posted on this blog are his and his alone, and have no relation to anything he's working on, his employer, or anything else and are not an official statement of any kind by them (and barely even one by him most of the time).

Archived Wordpress comments
Andy wrote on Friday, April 4, 2008:

Can we suggest things here? I hope so, else just delete this ;)

Hmm, I’m not sure how exactly is the best way to fix it, but for sure, a probability of 0-1.0 is not a good idea, you’d tend to having more of the highest numbered item returned.

Since it is floored, after all, for say, 10 items, you’d have…

0 - 0.099999.. (floored = item 0, since if NUM is 10, this is always a maximum of 0.9999…rounding to 0)
0.10 - 0.199999.. (NUMthis = floored to 1)
0.20 - 0.299999..


0.80 - 0.899999..
0.90 - 0.999999.. (floored = item 9)
1.00 (eeek!)

Oops, we have a single case where the *total amount items
can be returned, rather then 0-X, we have 0-X+1. This really would make any array based around it returning 0-X fail hard.

And ouch, it might take a little while to find too, depending on what type of precision the floating number is!

So to fix? Hmmmmmm… I am not sure. You need to get rid of that additional value, without altering the percentage chances of the results (meaning taking off the smallest possible value as you stated usually makes the maximum) is not it.

Gah, I don’t know (it is 2:30AM, urg, but this was too interesting to pass up). I hope you provide answers, and I sure as hell hope I’m right on the first part :)

exquicorp wrote on Thursday, April 10, 2008:

I don’t agree with the assertion that most return a float between 0 and 0.99999999….for uniform distribution rng they usually work on a range versus providing generic results between 0,1 (0 inclusive, 1 exclusive). Not using a range means you’re going to rely on the callers ability to handle truncation/flooring/rounding themselves…a bad thing. This is why most calls are rand(10) etc.

I thought the following…that the function returned a float (well double) which was based on the range / range + 1 so that if your range was 10 it would return 0, .09.., .18.,……9090

Your guy added an extra “level”..and the spread is now out of this range. Random(10) yields 0-10 rather than 0-9.

Anyway just return num_items - 1 * rand…

All adding 1.0 did was add one more to the distribution.

Maybe I missed something -it’s gone 2am and I was just checking in coz I was bored not to think!!

exquicorp wrote on Thursday, April 10, 2008:

Meant to add. If you were doing the normal rand() with range and % the result you get more weird results because 0 is yielded twice as often as any other number…I ran across this once looking at MySQL.

I will say that rand is the most mis documented function I’ve ever seen…the words inclusive/between are used with little thought everywhere :-)

exquicorp wrote on Friday, April 11, 2008:

I thought about this today on my walk. I decided that what I wrote was crap. Today I correct myself.

Firstly, I do disagree still :-) RNG usually provide a number based on a preset range. However, that’s not your question.

Based PURELY on your question. The 0-1 is bad because you’re using implicit compiler truncation to provide you with the intervals as stated by andy. So 0-0.09999/0.1-.19999999….

and 1 gets you the “extra” value.

Solution?
int GetIndex()
{
float rand = GetRandomNumber();
return (rand = 1.0f) ? GetIndex() : NUM_ITEMS * rand;
}

Been a while since I coded!!

I hate the truncation though…..

I think this is better than what I said yesterday….

Andy wrote on Friday, April 11, 2008:

Cool, exquicorp, I noted this to get replies, that I guess is one way of getting around the 1.0f problem - although unlikely (at least, I’d hope so) it could theoretically be a unlimited recursive loop :)

I also too wondered if a floating random generator really returned a percent result - I’ve only needed integer randomness myself, I should look into it more, hehe.

But I know that’s pulling hairs, I didn’t think to simply call GetIndex() again! Dear me, I really must have been tired.

facebook comments