[m-rev.] RNGs

Mark Brown mark at mercurylang.org
Mon Aug 19 06:56:04 AEST 2019


Hi Julien.

On Mon, Aug 19, 2019 at 1:45 AM Julien Fischer <jfischer at opturion.com> wrote:
>
>
> Hi Mark,
>
> On Tue, 13 Aug 2019, Mark Brown wrote:
>
> > I've just made a pull request to add some RNGs to the standard library, as
> > well as a typeclass interface to them. Pull request is here:
> >
> > https://github.com/Mercury-Language/mercury/pull/70
> >
> > The diff is also attached, for anyone who would prefer to comment on
> > it via email.
>
> Thanks for looking into this, it's part of the stdlib that has long needed
> fixing.  Here's a partial review that mainly addresses aspects of the interface
> design.  I haven't reviewed the actual RNG implementations as yet.

Thanks. You can leave reviewing the RNG implementations until after
we've decided which ones to keep.

>
> > commit f102ddaf4c128137b27ac6e85ac881faaf435c9b
> > Author: Mark Brown <mark at mercurylang.org>
> > Date:   Tue Aug 13 16:42:38 2019 +1000
> >
> >     Some RNGs for the standard library, plus typeclass interfaces.
> >
> >     library/rng.m:
> >         Top-level module containing typeclasses and generic routines,
> >         as well as overall documentation.
>
> The top-level module for random number generator facilities should really be
> random.  I realise that's taken, however I propose that the new stuff be added
> to it and the existing contents of that file deprecated.  (They ought to be
> able to co-exist in the interim until the old stuff is removed.)

Ok, but see below.

>
> >     library/rng.binfile.m:
> >         A generator that reads from a file.
> >
> >     library/rng.marsaglia.m:
> >         Fast, simple generator. Diehard results for default seed:
> >             PASSED: 109
> >             WEAK:   2
> >             FAILED: 3
> >
> >     library/rng.tausworthe.m:
> >         Combined Tausworthe generators. Diehard results for default seed:
> >
> >         generator T3
> >             PASSED: 113
> >             WEAK:   1
> >             FAILED: 0
> >
> >         generator T4
> >             PASSED: 112
> >             WEAK:   2
> >             FAILED: 0
>
> There's a bit of question as to what RNGs should be included in the
> stdlib by default.

Yes, I've been evaluating more of these, and I'll be happy to leave
out any that we don't in the end have a use case to justify. At the
moment, now that I've compared them to sfc, I'm thinking that both
marsaglia and tausworthe could be removed:

 - The justification for marsaglia is that it is very fast. Sfc16 is
also fast, but marsaglia is about 7 or 8 times faster, so it would
seem to be worthwhile including it. However, the absolute times are so
small that in order to notice a difference in overall time a lot of
numbers will need to be generated, and by this time biases in
marsaglia will have had a chance to show up. So whether you are
generating a small or large set of numbers, it would seem that sfc16
is at least as good as marsaglia.

 - The combined Tausworthe generators were meant to be something
familiar and of better quality than marsaglia, but sfc has turned out
to be faster and of much higher quality than tausworthe.

If anyone thinks we should keep the above, please say so.

I still have a few more generators I want to look at. We don't have
any with arbitrary jumps, or that can accept added entropy during
operation, but those features may be desirable. Sfc is not
cryptographically secure, although I'm not sure we want to offer such
a thing.

>
> >     library/library.m:
> >     library/MODULES_DOC:
> >         Add the new modules to the public interface.
> >
> >     library/float.m:
> >         Add functions to convert from (u)int32/64 to float.
> >
> >     library/uint32.m:
> >         Add function to convert from uint64 to uint32.
> >
> >     tests/hard_coded/Mmakefile:
> >     tests/hard_coded/rng1.{m,exp}:
> >     tests/hard_coded/rng2.{m,exp}:
> >         Test the generators. The expected outputs are derived from
> >         the output of the C reference implementations.
>
> ...
>
> > diff --git a/library/float.m b/library/float.m
> > index e19981c..4e2abfe 100644
> > --- a/library/float.m
> > +++ b/library/float.m
> > @@ -133,13 +133,25 @@
> >  :- func from_int8(int8) = float.
> >
> >      % Convert a signed 16-bit integer into a float.
> > -    % Always succeeds as all unsigned 8-bit integers have an exact
> > +    % Always succeeds as all signed 16-bit integers have an exact
> >      % floating-point representation.
> >      %
> >  :- func from_int16(int16) = float.
> >
> > +    % Convert a signed 32-bit integer into a float.
> > +    % Always succeeds as all signed 32-bit integers have an exact
> > +    % floating-point representation.
>
> Not true in .spf grades.

Fixed, and below.

>
> > +    %
> > +:- func from_int32(int32) = float.
> > +
> > +    % Convert a signed 64-bit integer into a float.
> > +    % The behaviour when the integer exceeds the range of what can be
> > +    % exactly represented by a float is undefined.
> > +    %
> > +:- func from_int64(int64) = float.
> > +
> >      % Convert an unsigned 8-bit integer into a float.
> > -    % Always succeeds as all signed 16-bit integers have an exact
> > +    % Always succeeds as all unsigned 8-bit integers have an exact
> >      % floating-point representation.
> >      %
> >  :- func from_uint8(uint8) =  float.
> > @@ -150,6 +162,18 @@
> >      %
> >  :- func from_uint16(uint16) = float.
> >
> > +    % Convert an unsigned 32-bit integer into a float.
> > +    % Always succeeds as all unsigned 32-bit integers have an exact
> > +    % floating-point representation.
>
> Again, not true in .spf grades.
>
> > +    %
> > +:- func from_uint32(uint32) = float.
> > +
> > +    % Convert an unsigned 64-bit integer into a float.
> > +    % The behaviour when the integer exceeds the range of what can be
> > +    % exactly represented by a float is undefined.
> > +    %
> > +:- func from_uint64(uint64) = float.
>
> In the integer modules I added, the from_* names are typically used for checked
> versions of operations; I think this and the above should be named
> cast_from_uint64/1 etc.

Fixed.

>
> ...
>
> > diff --git a/library/rng.binfile.m b/library/rng.binfile.m
> > new file mode 100644
> > index 0000000..36c1966
> > --- /dev/null
> > +++ b/library/rng.binfile.m
> > @@ -0,0 +1,96 @@
> > +%---------------------------------------------------------------------------%
> > +% vim: ft=mercury ts=4 sts=4 sw=4 et
> > +%---------------------------------------------------------------------------%
> > +% Copyright (C) 2019 The Mercury team.
> > +% This file is distributed under the terms specified in COPYING.LIB.
> > +%---------------------------------------------------------------------------%
> > +%
> > +% File: rng.binfile.m
> > +% Main author: Mark Brown
> > +%
> > +% "Random" number generator that reads numbers from a binary file.
> > +%
> > +%---------------------------------------------------------------------------%
> > +%---------------------------------------------------------------------------%
> > +
> > +:- module rng.binfile.
> > +:- interface.
> > +
> > +:- import_module io.
> > +
> > +%---------------------------------------------------------------------------%
> > +
> > +:- type binfile.
> > +:- instance urng(binfile, io).
> > +
> > +    % Open a binfile generator from a filename. This should be closed
> > +    % when no longer needed.
> > +    %
> > +:- pred open(string, io.res(binfile), io, io).
> > +:- mode open(in, out, di, uo) is det.
>
> Is there a reason not to use predmode declarations here?

Not really. Should I? (And should the coding standard be updated?)

>
> > +
> > +    % Close a binfile generator.
> > +    %
> > +:- pred close(binfile, io, io).
> > +:- mode close(in, di, uo) is det.
> > +
> > +%---------------------------------------------------------------------------%
> > +
> > +    % Generate a number between 0 and max_uint64. This reads 8 bytes
> > +    % at a time from the binfile and interprets them as an unsigned,
> > +    % big-endian integer.
> > +    %
> > +    % Throws an exception if the end-of-file is reached.
> > +    %
> > +:- pred rand(binfile, uint64, io, io).
> > +:- mode rand(in, out, di, uo) is det.
> > +
> > +%---------------------------------------------------------------------------%
> > +
> > +:- implementation.
> > +
> > +:- import_module require.
> > +:- import_module uint64.
> > +
> > +%---------------------------------------------------------------------------%
> > +
> > +:- type binfile
> > +    --->    binfile(binary_input_stream).
> > +
> > +:- instance urng(binfile, io) where [
> > +    pred(urandom/4) is rand,
> > +    ( urandom_max(_) = uint64.max_uint64 )
> > +].
>
> It would be preferable if each generator also exported the predicates that
> implement these methods, so they can be used without going via the type class
> interface.
>
> Ditto for the other generators.

Ok, I've exported a "rand_max" for each generator. The exported
predicates don't always have the same signatures as the typeclass
methods, though, since they are specialized to the needs of the
particular generator. I figure that the main reason to use a specific
generator directly is speed, and as such it is better to leave off
unneeded arguments (as in the sfc32 and sfc generators, which don't
need the params argument). Similarly it is better to use uint16 or
uint32 rather than uint64, if that is what the generator actually
produces.

>
> ...
>
> > diff --git a/library/rng.m b/library/rng.m
> > new file mode 100644
> > index 0000000..24e8086
> > --- /dev/null
> > +++ b/library/rng.m
> > @@ -0,0 +1,345 @@
> > +%---------------------------------------------------------------------------%
> > +% vim: ft=mercury ts=4 sts=4 sw=4 et
> > +%---------------------------------------------------------------------------%
> > +% Copyright (C) 2019 The Mercury team.
> > +% This file is distributed under the terms specified in COPYING.LIB.
> > +%---------------------------------------------------------------------------%
> > +%
> > +% File: rng.m
> > +% Main author: Mark Brown
> > +%
> > +% This module provides an interface to several random number generators,
> > +% which can be found in the submodules.
>
> It also provides one instance of a distribution function (random_gauss);
> such distributions would be better off placed in their own sub-modules.
> (If you look at say the random library in Boost or in more recent versions of
> C++, for example, there a bunch of others that we may well end up adding here.)

As you point out below, all of the predicates that return random
numbers have a distribution, so I'm not sure why the dividing line
should be between random_gauss and random_{int,float}. Is "a bunch"
too many for the top level module? It only has these, plus the
typeclasses themselves.

One thing I was wondering was whether to split it into two top-level
modules, one with the shared interface and one with the unique
interface. Any thoughts on that?

>
> > +% Two styles of the interface are provided, a ground style and a
> > +% unique style. Each has its own advantages and disadvantages:
> > +%
> > +%   - Ground RNGs are easier to use; for example they can be easily
> > +%     stored in larger data structures.
> > +%   - Ground RNGs are easier to implement instances for.
> > +%   - Unique RNGs are able to use destructive update, and therefore
> > +%     are often able to operate more efficiently.
> > +%   - Unique RNGs need to be explicitly duplicated (i.e., to produce
> > +%     a new generator that will generate the same sequence of numbers).
> > +%     This may be regarded as an advantage or a disadvantage.
> > +%   - Some RNGs, for example the binfile generator that reads data from
> > +%     a file, use the IO state and therefore must use the unique interface.
>
> I/O for consistency with other library documentation.

Fixed.

>
> > +% Each RNG defined in the submodules is natively one of these two styles.
> > +% Conversion between the two styles can be done with make_urng/3 and
> > +% make_shared_rng/2, below, although this incurs additional overhead.
> > +%
> > +%
> > +% Example, ground style:
> > +%
> > +%   main(!IO) :-
> > +%       RNG0 = rng.marsaglia.init,
> > +%       roll(RNG0, RNG1, !IO),
> > +%       roll(RNG1, _, !IO).
> > +%
> > +%   :- pred roll(RNG, RNG, io, io) <= rng(RNG).
> > +%   :- mode roll(in, out, di, uo) is det.
> > +%
> > +%   roll(!RNG, !IO) :-
> > +%       random_int(1, 6, N, !RNG),
> > +%       io.format("You rolled a %d\n", [i(N)], !IO).
> > +%
> > +%
> > +% Example, unique style:
> > +%
> > +%   main(!IO) :-
> > +%       rng.tausworthe.init_t3(RP, RS0),
> > +%       roll(RP, RS0, RS1, !IO),
> > +%       roll(RP, RS1, _, !IO).
> > +%
> > +%   :- pred roll(RP, RS, RS, io, io) <= urng(RP, RS).
> > +%   :- mode roll(in, di, uo, di, uo) is det.            % note unique modes
> > +%
> > +%   roll(RP, !RS, !IO) :-
> > +%       urandom_int(RP, 1, 6, N, !RS),
> > +%       io.format("You rolled a %d\n", [i(N)], !IO).
> > +%
> > +%
> > +% Example, converting style:
> > +%
> > +%   main(!IO) :-
> > +%       rng.tausworthe.init_t3(RP, RS),
> > +%       RNG0 = make_shared_rng(RP, RS),
> > +%       random_int(1, 6, N, RNG0, RNG1),
> > +%       ...
> > +%
> > +%   main(!IO) :-
> > +%       RNG = rng.marsaglia.init,
> > +%       make_urng(RNG, RP, RS0),
> > +%       urandom_int(RP, 1, 6, N, RS0, RS1),
> > +%       ...
> > +%
> > +%---------------------------------------------------------------------------%
> > +%---------------------------------------------------------------------------%
> > +
> > +:- module rng.
> > +:- interface.
> > +
> > +:- include_module binfile.
> > +:- include_module marsaglia.
> > +:- include_module tausworthe.
> `> +
> > +%---------------------------------------------------------------------------%
> > +
> > +    % random_int(Start, Range, N, !RNG)
> > +    %
> > +    % Generate a random integer between Start and Start+Range-1 inclusive.
> > +    % Throws an exception if Range < 1 or Range > random_max.
> > +    %
> > +:- pred random_int(int, int, int, RNG, RNG) <= rng(RNG).
> > +:- mode random_int(in, in, out, in, out) is det.
>
> I would hope the intention here is that each call to random_int/5 returns a
> random int uniformly distributed in the given range.  If so, the documentation
> should say that, if not it should say what the user can assume (or not) about
> the distribution of the ints returned.
>
> (I feel a reference to the XKCD random number generator is order here:
> <https://xkcd.com/221/>.)

Heh. Technically, with the binfile generator, you are at the mercy of
the file you decide to use (it's handy for reading /dev/urandom,
though).

>
> > +
> > +    % Generate a random float between 0.0 and 1.0, inclusive.
>
> I believe that [0, 1) is more usual.
>
> > +    %
> > +:- pred random_float(float, RNG, RNG) <= rng(RNG).
> > +:- mode random_float(out, in, out) is det.
>
> I suggest the following predicates here:
>
>      uniform_int
>      uniform_int_range
>      uniform_uint
>      uniform_uint_range
>      ditto for all other integer types
>
>      uniform_float_range
>      uniform_float_01     i.e. in [0, 1).

Will do.

>
> All of the above generate random values uniformly distributed in the
> given range.  The following predicate ...
>
> > +    % Generate two random floats from a normal distribution with
> > +    % mean 0 and standard deviation 1, using the Box-Muller method.
> > +    %
> > +    % We generate two at a time for efficiency; they are independent of
> > +    % each other.
> > +    %
> > +:- pred random_gauss(float, float, RNG, RNG) <= rng(RNG).
> > +:- mode random_gauss(out, out, in, out) is det.
>
> ... should be moved to a separate submodule.  Ditto for the unique variants.

See above reply. If you still want this I don't really object, but
you'll have to think of a module name.

>
> > +%---------------------------------------------------------------------------%
> > +
> > +    % Interface to random number generators.
> > +    %
> > +:- typeclass rng(RNG) where [
> > +
> > +        % Generate a random integer between 0 and random_max, inclusive.
> > +        %
> > +    pred random(uint64, RNG, RNG),
> > +    mode random(out, in, out) is det,
>
> I think the basic unit returned by an RNG ought to be a uint32 rather than a
> uint64 -- I note most of the implementations you have here actually do that
> anyway and just cast the result to a uint64.

What's the advantage of uint32?

>
> I suggest we impose a stronger requirement on RNGs here, namely that each
> call to random/3 returns a random 64-bit (or 32-bit) word.  It is the
> responsbility of the RNG instance to fulfil that requirement.   Most modern
> pseudo-random number generators should be fine with this requirement.

I've documented that the numbers should be uniformly distributed,
although this implies most instances will only be pseudo-correct ;-)

I've also added that random_max should be no less than 65535, as it
doesn't seem too much to ask instances to be able to come up with at
least 16 bits at a time.

>
> Also, I prefer the name 'next' to 'random'.

Will fix.

>
> > +
> > +        % Return the largest integer that can be generated.
> > +        %
> > +    func random_max(RNG) = uint64
> > +].
>
> I would place the typeclass definitions first and then the predicates
> that use them after.

Ok.

>
> > +%---------------------------------------------------------------------------%
> > +%---------------------------------------------------------------------------%
> > +
> > +    % urandom_int(RP, Start, Range, N, !RS)
> > +    %
> > +    % Generate a random integer between Start and Start+Range-1 inclusive.
> > +    % Throws an exception if Range < 1 or Range > urandom_max.
> > +    %
> > +:- pred urandom_int(RP, int, int, int, RS, RS) <= urng(RP, RS).
> > +:- mode urandom_int(in, in, in, out, di, uo) is det.
> > +
> > +    % Generate a random float between 0.0 and 1.0, inclusive.
> > +    %
> > +:- pred urandom_float(RP, float, RS, RS) <= urng(RP, RS).
> > +:- mode urandom_float(in, out, di, uo) is det.
> > +
> > +    % Generate two random floats from a normal distribution with
> > +    % mean 0 and standard deviation 1, using the Box-Muller method.
> > +    %
> > +    % We generate two at a time for efficiency; they are independent of
> > +    % each other.
> > +    %
> > +:- pred urandom_gauss(RP, float, float, RS, RS) <= urng(RP, RS).
> > +:- mode urandom_gauss(in, out, out, di, uo) is det.
>
> Everything I said above applies here with the obvious modifications.
>
> ...
>
> > +%---------------------------------------------------------------------------%
> > +%---------------------------------------------------------------------------%
> > +
> > +:- implementation.
> > +
> > +:- import_module int.
> > +:- import_module float.
> > +:- import_module math.
> > +:- import_module uint64.
> > +
> > +%---------------------------------------------------------------------------%
> > +
> > +random_int(Start, Range0, N, !RNG) :-
> > +    Range = uint64.det_from_int(Range0),
> > +    random(N0, !RNG),
> > +    Max = random_max(!.RNG),
> > +    N1 = N0 // (Max // Range),
> > +    ( if N1 < Range then
> > +        N = Start + uint64.cast_to_int(N1)
> > +    else
> > +        random_int(Start, Range0, N, !RNG)
> > +    ).
>
> Not that it needs to be addressed now, but it should be possible to do better
> here, see:
>
>     Daniel Lemire
>     Fast Random Integer Generation in an Interval
>     ACM Transactions on Modeling and Computer Simulation 29 (1), 2019

Thanks, I will check it out.

Mark

>
> Julien.
-------------- next part --------------
commit b3ecdaee5719489ac938146d30dc8f794d07e4be
Author: Mark Brown <mark at mercurylang.org>
Date:   Mon Aug 19 06:54:33 2019 +1000

    Address some of Julien's review comments.

diff --git a/library/float.m b/library/float.m
index 4e2abfe..14c7aaa 100644
--- a/library/float.m
+++ b/library/float.m
@@ -139,16 +139,16 @@
 :- func from_int16(int16) = float.
 
     % Convert a signed 32-bit integer into a float.
-    % Always succeeds as all signed 32-bit integers have an exact
-    % floating-point representation.
+    % The behaviour when the integer exceeds the range of what can be
+    % exactly represented by a float is undefined.
     %
-:- func from_int32(int32) = float.
+:- func cast_from_int32(int32) = float.
 
     % Convert a signed 64-bit integer into a float.
     % The behaviour when the integer exceeds the range of what can be
     % exactly represented by a float is undefined.
     %
-:- func from_int64(int64) = float.
+:- func cast_from_int64(int64) = float.
 
     % Convert an unsigned 8-bit integer into a float.
     % Always succeeds as all unsigned 8-bit integers have an exact
@@ -163,16 +163,16 @@
 :- func from_uint16(uint16) = float.
 
     % Convert an unsigned 32-bit integer into a float.
-    % Always succeeds as all unsigned 32-bit integers have an exact
-    % floating-point representation.
+    % The behaviour when the integer exceeds the range of what can be
+    % exactly represented by a float is undefined.
     %
-:- func from_uint32(uint32) = float.
+:- func cast_from_uint32(uint32) = float.
 
     % Convert an unsigned 64-bit integer into a float.
     % The behaviour when the integer exceeds the range of what can be
     % exactly represented by a float is undefined.
     %
-:- func from_uint64(uint64) = float.
+:- func cast_from_uint64(uint64) = float.
 
 %---------------------------------------------------------------------------%
 %
@@ -584,7 +584,7 @@ X / Y = Z :-
 %---------------------------------------------------------------------------%
 
 :- pragma foreign_proc("C",
-    from_int32(Int32Val::in) = (FloatVal::out),
+    cast_from_int32(Int32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail,
         does_not_affect_liveness],
 "
@@ -592,21 +592,21 @@ X / Y = Z :-
 ").
 
 :- pragma foreign_proc("C#",
-    from_int32(Int32Val::in) = (FloatVal::out),
+    cast_from_int32(Int32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) Int32Val;
 ").
 
 :- pragma foreign_proc("Java",
-    from_int32(Int32Val::in) = (FloatVal::out),
+    cast_from_int32(Int32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) Int32Val;
 ").
 
 :- pragma foreign_proc("Erlang",
-    from_int32(Int32Val::in) = (FloatVal::out),
+    cast_from_int32(Int32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = float(Int32Val)
@@ -615,7 +615,7 @@ X / Y = Z :-
 %---------------------------------------------------------------------------%
 
 :- pragma foreign_proc("C",
-    from_uint32(UInt32Val::in) = (FloatVal::out),
+    cast_from_uint32(UInt32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail,
         does_not_affect_liveness],
 "
@@ -623,21 +623,21 @@ X / Y = Z :-
 ").
 
 :- pragma foreign_proc("C#",
-    from_uint32(UInt32Val::in) = (FloatVal::out),
+    cast_from_uint32(UInt32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) UInt32Val;
 ").
 
 :- pragma foreign_proc("Java",
-    from_uint32(UInt32Val::in) = (FloatVal::out),
+    cast_from_uint32(UInt32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) (UInt32Val & 0xffffffff);
 ").
 
 :- pragma foreign_proc("Erlang",
-    from_uint32(UInt32Val::in) = (FloatVal::out),
+    cast_from_uint32(UInt32Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = float(UInt32Val)
@@ -646,7 +646,7 @@ X / Y = Z :-
 %---------------------------------------------------------------------------%
 
 :- pragma foreign_proc("C",
-    from_int64(Int64Val::in) = (FloatVal::out),
+    cast_from_int64(Int64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail,
         does_not_affect_liveness],
 "
@@ -654,21 +654,21 @@ X / Y = Z :-
 ").
 
 :- pragma foreign_proc("C#",
-    from_int64(Int64Val::in) = (FloatVal::out),
+    cast_from_int64(Int64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) Int64Val;
 ").
 
 :- pragma foreign_proc("Java",
-    from_int64(Int64Val::in) = (FloatVal::out),
+    cast_from_int64(Int64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) Int64Val;
 ").
 
 :- pragma foreign_proc("Erlang",
-    from_int64(Int64Val::in) = (FloatVal::out),
+    cast_from_int64(Int64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = float(Int64Val)
@@ -677,7 +677,7 @@ X / Y = Z :-
 %---------------------------------------------------------------------------%
 
 :- pragma foreign_proc("C",
-    from_uint64(UInt64Val::in) = (FloatVal::out),
+    cast_from_uint64(UInt64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail,
         does_not_affect_liveness],
 "
@@ -685,21 +685,21 @@ X / Y = Z :-
 ").
 
 :- pragma foreign_proc("C#",
-    from_uint64(UInt64Val::in) = (FloatVal::out),
+    cast_from_uint64(UInt64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) UInt64Val;
 ").
 
 :- pragma foreign_proc("Java",
-    from_uint64(UInt64Val::in) = (FloatVal::out),
+    cast_from_uint64(UInt64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = (double) UInt64Val;
 ").
 
 :- pragma foreign_proc("Erlang",
-    from_uint64(UInt64Val::in) = (FloatVal::out),
+    cast_from_uint64(UInt64Val::in) = (FloatVal::out),
     [will_not_call_mercury, promise_pure, thread_safe],
 "
     FloatVal = float(UInt64Val)
diff --git a/library/rng.binfile.m b/library/rng.binfile.m
index 36c1966..6defd25 100644
--- a/library/rng.binfile.m
+++ b/library/rng.binfile.m
@@ -45,6 +45,11 @@
 :- pred rand(binfile, uint64, io, io).
 :- mode rand(in, out, di, uo) is det.
 
+    % Returns max_uint64, the maximum number that can be returned by this
+    % generator.
+    %
+:- func rand_max(binfile) = uint64.
+
 %---------------------------------------------------------------------------%
 
 :- implementation.
@@ -59,7 +64,7 @@
 
 :- instance urng(binfile, io) where [
     pred(urandom/4) is rand,
-    ( urandom_max(_) = uint64.max_uint64 )
+    func(urandom_max/1) is rand_max
 ].
 
 %---------------------------------------------------------------------------%
@@ -93,4 +98,6 @@ rand(binfile(Stream), N, !IO) :-
         unexpected($pred, io.error_message(E))
     ).
 
+rand_max(_) = uint64.max_uint64.
+
 %---------------------------------------------------------------------------%
diff --git a/library/rng.m b/library/rng.m
index fbca357..202b3ad 100644
--- a/library/rng.m
+++ b/library/rng.m
@@ -23,7 +23,7 @@
 %     a new generator that will generate the same sequence of numbers).
 %     This may be regarded as an advantage or a disadvantage.
 %   - Some RNGs, for example the binfile generator that reads data from
-%     a file, use the IO state and therefore must use the unique interface.
+%     a file, use the I/O state and therefore must use the unique interface.
 %
 % Each RNG defined in the submodules is natively one of these two styles.
 % Conversion between the two styles can be done with make_urng/3 and
@@ -89,13 +89,14 @@
 
     % random_int(Start, Range, N, !RNG)
     %
-    % Generate a random integer between Start and Start+Range-1 inclusive.
+    % Generate a uniformly distributed random integer between Start and
+    % Start+Range-1 inclusive.
     % Throws an exception if Range < 1 or Range > random_max.
     %
 :- pred random_int(int, int, int, RNG, RNG) <= rng(RNG).
 :- mode random_int(in, in, out, in, out) is det.
 
-    % Generate a random float between 0.0 and 1.0, inclusive.
+    % Generate a uniformly distributed random float in the range [0, 1).
     %
 :- pred random_float(float, RNG, RNG) <= rng(RNG).
 :- mode random_float(out, in, out) is det.
@@ -115,12 +116,14 @@
     %
 :- typeclass rng(RNG) where [
 
-        % Generate a random integer between 0 and random_max, inclusive.
+        % Generate a uniformly distributed random integer between 0 and
+        % random_max, inclusive.
         %
     pred random(uint64, RNG, RNG),
     mode random(out, in, out) is det,
 
-        % Return the largest integer that can be generated.
+        % Return the largest integer that can be generated. This must be
+        % no less than 65535.
         %
     func random_max(RNG) = uint64
 ].
@@ -130,13 +133,14 @@
 
     % urandom_int(RP, Start, Range, N, !RS)
     %
-    % Generate a random integer between Start and Start+Range-1 inclusive.
+    % Generate a uniformly distributed random integer between Start and
+    % Start+Range-1 inclusive.
     % Throws an exception if Range < 1 or Range > urandom_max.
     %
 :- pred urandom_int(RP, int, int, int, RS, RS) <= urng(RP, RS).
 :- mode urandom_int(in, in, in, out, di, uo) is det.
 
-    % Generate a random float between 0.0 and 1.0, inclusive.
+    % Generate a uniformly distributed random float in the interval [0, 1).
     %
 :- pred urandom_float(RP, float, RS, RS) <= urng(RP, RS).
 :- mode urandom_float(in, out, di, uo) is det.
@@ -158,12 +162,14 @@
     %
 :- typeclass urng(RP, RS) <= (RP -> RS) where [
 
-        % Generate a random integer between 0 and random_max, inclusive.
+        % Generate a uniformly distributed random integer between 0 and
+        % random_max, inclusive.
         %
     pred urandom(RP, uint64, RS, RS),
     mode urandom(in, out, di, uo) is det,
 
-        % Return the largest integer that can be generated.
+        % Return the largest integer that can be generated. This must be
+        % no less than 65535.
         %
     func urandom_max(RP) = uint64
 ].
@@ -233,7 +239,7 @@ random_int(Start, Range0, N, !RNG) :-
 random_float(F, !RNG) :-
     random(N, !RNG),
     Max = random_max(!.RNG),
-    F = float.from_uint64(N) / float.from_uint64(Max).
+    F = float.cast_from_uint64(N) / (float.cast_from_uint64(Max) + 1.0).
 
 random_gauss(U, V, !RNG) :-
     random_float(X, !RNG),
@@ -261,7 +267,7 @@ urandom_int(RP, Start, Range0, N, !RS) :-
 urandom_float(RP, F, !RS) :-
     urandom(RP, N, !RS),
     Max = urandom_max(RP),
-    F = float.from_uint64(N) / float.from_uint64(Max).
+    F = float.cast_from_uint64(N) / (float.cast_from_uint64(Max) + 1.0).
 
 urandom_gauss(RP, U, V, !RS) :-
     urandom_float(RP, X, !RS),
diff --git a/library/rng.marsaglia.m b/library/rng.marsaglia.m
index 8afac69..25053f1 100644
--- a/library/rng.marsaglia.m
+++ b/library/rng.marsaglia.m
@@ -41,6 +41,11 @@
 :- pred rand(uint32, marsaglia, marsaglia).
 :- mode rand(out, in, out) is det.
 
+    % Return max_uint32, the maximum number that can be returned by this
+    % generator.
+    %
+:- func rand_max(marsaglia) = uint32.
+
 %---------------------------------------------------------------------------%
 
 :- implementation.
@@ -57,7 +62,7 @@
         rand(N0, !RNG),
         N = uint32.cast_to_uint64(N0)
     ),
-    ( random_max(_) = uint32.cast_to_uint64(uint32.max_uint32) )
+    ( random_max(RNG) = uint32.cast_to_uint64(rand_max(RNG)) )
 ].
 
 %---------------------------------------------------------------------------%
@@ -83,6 +88,8 @@ rand(N, RNG0, RNG) :-
     S = pack_uint64(SX, SY),
     RNG = marsaglia(S).
 
+rand_max(_) = uint32.max_uint32.
+
 %---------------------------------------------------------------------------%
 
 :- func pack_uint64(uint32, uint32) = uint64.
diff --git a/library/rng.sfc.m b/library/rng.sfc.m
index 15d240d..a4eb149 100644
--- a/library/rng.sfc.m
+++ b/library/rng.sfc.m
@@ -44,6 +44,11 @@
 :- pred rand16(uint16, sfc, sfc).
 :- mode rand16(out, in, out) is det.
 
+    % Return max_uint16, the maximum number that can be returned by this
+    % generator.
+    %
+:- func rand16_max(sfc) = uint16.
+
 %---------------------------------------------------------------------------%
 %---------------------------------------------------------------------------%
 
@@ -74,6 +79,11 @@
 :- pred rand(uint64, state, state).
 :- mode rand(out, di, uo) is det.
 
+    % Return max_uint64, the maximum number that can be returned by this
+    % generator.
+    %
+:- func rand_max = uint64.
+
     % Duplicate a 64-bit SFC state.
     %
 :- pred dup(state, state, state).
@@ -112,6 +122,11 @@
 :- pred rand32(uint32, state32, state32).
 :- mode rand32(out, di, uo) is det.
 
+    % Return max_uint32, the maximum number that can be returned by this
+    % generator.
+    %
+:- func rand32_max = uint32.
+
     % Duplicate a 32-bit SFC state.
     %
 :- pred dup32(state32, state32, state32).
@@ -139,7 +154,7 @@
         rand16(N0, !RNG),
         N = uint16.cast_to_uint64(N0)
     ),
-    ( random_max(_) = uint16.cast_to_uint64(uint16.max_uint16) )
+    ( random_max(RNG) = uint16.cast_to_uint64(rand16_max(RNG)) )
 ].
 
 init16 = seed16(0x6048_5623_5e79_371e_u64).
@@ -169,6 +184,8 @@ rand16(N, sfc(S0), sfc(S)) :-
     Counter = Counter0 + 1u16,
     S = pack_uint64(A, B, C, Counter).
 
+rand16_max(_) = uint16.max_uint16.
+
 :- func pack_uint64(uint16, uint16, uint16, uint16) = uint64.
 
 pack_uint64(P1, P2, P3, P4) =
@@ -200,7 +217,7 @@ unpack_uint64(S, P1, P2, P3, P4) :-
     ( urandom(_, N, !RS) :-
         rand(N, !RS)
     ),
-    ( urandom_max(_) = uint64.max_uint64 )
+    ( urandom_max(_) = rand_max )
 ].
 
 :- instance urng_dup(state) where [
@@ -258,6 +275,8 @@ rand(N, RS0, RS) :-
     array.unsafe_set(3, Counter, S3, S),
     RS = unsafe_promise_unique(state(S)).
 
+rand_max = uint64.max_uint64.
+
 %---------------------------------------------------------------------------%
 %---------------------------------------------------------------------------%
 
@@ -272,7 +291,7 @@ rand(N, RS0, RS) :-
         rand32(N0, !RS),
         N = uint32.cast_to_uint64(N0)
     ),
-    ( urandom_max(_) = uint32.cast_to_uint64(uint32.max_uint32) )
+    ( urandom_max(_) = uint32.cast_to_uint64(rand32_max) )
 ].
 
 :- instance urng_dup(state32) where [
@@ -330,4 +349,6 @@ rand32(N, RS0, RS) :-
     array.unsafe_set(3, Counter, S3, S),
     RS = unsafe_promise_unique(state32(S)).
 
+rand32_max = uint32.max_uint32.
+
 %---------------------------------------------------------------------------%
diff --git a/library/rng.tausworthe.m b/library/rng.tausworthe.m
index 38aa059..a506245 100644
--- a/library/rng.tausworthe.m
+++ b/library/rng.tausworthe.m
@@ -69,6 +69,11 @@
 :- pred rand(params, uint32, state, state).
 :- mode rand(in, out, di, uo) is det.
 
+    % Return max_uint32, the maximum number that can be returned by this
+    % generator.
+    %
+:- func rand_max(params) = uint32.
+
     % Duplicate a tausworthe RNG state.
     %
 :- pred dup(state, state, state).
@@ -104,7 +109,7 @@
         rand(RP, N0, !RS),
         N = uint32.cast_to_uint64(N0)
     ),
-    ( urandom_max(_) = uint32.cast_to_uint64(uint32.max_uint32) )
+    ( urandom_max(RP) = uint32.cast_to_uint64(rand_max(RP)) )
 ].
 
 :- instance urng_dup(state) where [
@@ -184,6 +189,8 @@ rand_2(RP, I, Size, N0, N, !Seed) :-
         N = N0
     ).
 
+rand_max(_) = uint32.max_uint32.
+
 %---------------------------------------------------------------------------%
 %---------------------------------------------------------------------------%
 


More information about the reviews mailing list