[erlang-bugs] Unstated limits of random:uniform/1

[Kenji Rikitake]

random:uniform/1 is defined as (in lib/stdlib/src/random.erl)

uniform(N) when is_integer(N), N >= 1 -> trunc(uniform() * N) + 1.

random:uniform/0 is within [0, 1), and is an IEEE 754 double precision
float, which only has 53 significand bits.  So giving anything larger
than 2^53 to N will give no additional meaningful resolution other
than the 53 MSBs of the result.

And as in

++> Michael Truog <mjtruog@REDACTED> [2014-02-11 07:28:22 -0800]:
> 27817185604309 == 30269 * 30307 * 30323 is the highest N should ever be, otherwise the result is garbage.

the output resolution is slightly less than 2^45 (27817185604309 = ~
2^(44.66)).

I wonder, however, how many of the bits in random:uniform/0 really has
the meaningful randomness, since it is a simple multiplying
congruential generator.  Should N be allowed as high as 2^44? I don't
think so.

Reference:

B. A. Wichmann and I. D. Hill,
Algorithm AS 183: An Efficient and Portable Pseudo-Random Number
Generator, 
Journal of the Royal Statistical Society. Series C (Applied
Statistics), Vol. 31, No. 2 (1982), pp. 188-190.

Kenji Rikitake

> On 02/11/2014 06:47 AM, Kostis Sagonas wrote:
> > The documentation of random:uniform/1 reads:
> >
> >   uniform(N) -> integer() >= 1
> >
> >   Types:
> >
> >     N = integer() >= 1
> >
> >   Given an integer N >= 1, uniform/1 returns a random integer uniformly distributed between 1 and N, updating the state in the process dictionary.
> >
> > and from it a (naive?) Erlang programmer would assume that it works for Erlang integers. However, apparently there is an (unstated) upper limit.
> >
> > ========================================================================
> > Eshell V6.0  (abort with ^G)
> > 1> random:uniform(1 bsl 42).
> > 1950905779137
> > 2> random:uniform(1 bsl 1023).
> > 64990220693815292632299777453770053245701880982584490305757715776780176648584151835529728245903303858071465265235635364507930685677056366431569479144084789774752709050314473717035731429737215919311815680621634352115003928201262448305879457258028874562676857884269587024825648343920396535221283000212783104001
> > 3> random:uniform(1 bsl 1024).
> > ** exception error: an error occurred when evaluating an arithmetic expression
> >      in function  random:uniform/1
> >      in call from erl_eval:do_apply/6
> >      in call from shell:exprs/7
> >      in call from shell:eval_exprs/7
> >      in call from shell:eval_loop/3
> >      in call from prim_file:set_cwd/2
> > ========================================================================
> >
> > Minimally, the published documentation (and the types of all functions of this module) has to be updated to explicitly mention this limit.
> >
> > Ideally, the implementation has to change to avoid use of floats when manipulating Erlang integers.  IMO, it does not really have to do this and result in crashes like that.
> >
> > Kostis