Incorrect documentation of PcgRandom:rand_normal_dist(...)

[ArguablySane]

Lua_api.txt documents the function as follows:

`rand_normal_dist(min, max, num_trials=6)`: return normally distributed random number [`min`...`max`]
This is only a rough approximation of a normal distribution with mean=(max-min)/2 and variance=1
Increasing num_trials improves accuracy of the approximation

Note that it says that the variance is always equal to 1.

The code which provides that function is:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

s32 PcgRandom::randNormalDist(s32 min, s32 max, int num_trials)
{
   s32 accum = 0;
   for (int i = 0; i != num_trials; i++)
      accum += range(min, max);
   return myround((float)accum / num_trials);
}


What it's doing is basically just taking the average of num_trials random numbers in the range [min - max].

Now, it should be obvious that if num_trials is 1, then it's equivalent to a discreet uniform distribution between min and max. Similarly, the law of large numbers tells us that if num_trials is very large then the result will almost always lie very close to half way between min and max. Neither of these distributions have a variance of 1. In fact, the variance changes depending on both the range and num_trials, and approximately equals ((max-min)^2)/(12*num_trials).


Also, on a somewhat related note, is the code in the PcgRandom::range(bound) correct?

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

u32 PcgRandom::range(u32 bound)
{
   // If the bound is 0, we cover the whole RNG's range
   if (bound == 0)
      return next();
   /*
   If the bound is not a multiple of the RNG's range, it may cause bias,
   e.g. a RNG has a range from 0 to 3 and we take want a number 0 to 2.
   Using rand() % 3, the number 0 would be twice as likely to appear.
   With a very large RNG range, the effect becomes less prevalent but
   still present.  This can be solved by modifying the range of the RNG
   to become a multiple of bound by dropping values above the a threshhold.
   In our example, threshhold == 4 - 3 = 1 % 3 == 1, so reject 0, thus
   making the range 3 with no bias.
   This loop looks dangerous, but will always terminate due to the
   RNG's property of uniformity.
   */
   u32 threshhold = -bound % bound;
   u32 r;

   while ((r = next()) < threshhold)
      ;

   return r % bound;
}

From my brief testing in python and lua, -n%n seems to always return 0 regardless of what n is (which makes sense), leaving threshold at zero for all possible inputs. Should that line read

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

u32 threshhold = RANDOM_MIN + (RANDOM_RANGE % bound);

instead? That way it would actually work as described in that long comment and would usually perform almost twice as fast because it wouldn't be throwing away any negative random numbers.

Please check my reasoning and correct me if I got anything wrong. It has been a while since I touched any c++.