%--------------------------------------------------% % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0 %--------------------------------------------------% % Copyright (C) 1994-1998,2001-2006, 2011 The University of Melbourne. % This file may only be copied under the terms of the GNU Library General % Public License - see the file COPYING.LIB in the Mercury distribution. %--------------------------------------------------% % % File: random.m % Main author: conway % Stability: low % % Define a set of random number generator predicates. This implementation % uses a threaded random-number supply. The supply can be used in a % non-unique way, which means that each thread returns the same list of % random numbers. However, this may not be desired so in the interests % of safety it is also declared with (backtrackable) unique modes. % % The coefficients used in the implementation were taken from Numerical % Recipes in C (Press et al), and are originally due to Knuth. These % coefficients are described as producing a "Quick and Dirty" random number % generator, which generates the numbers very quickly but not necessarily % with a high degree of quality. As with all random number generators, % the user is advised to consider carefully whether this generator meets % their requirements in terms of "randomness". For applications which have % special needs (e.g. cryptographic key generation), a generator such as % this is unlikely to be suitable. % % Note that random number generators of this type have several known % pitfalls which the user may need to avoid: % % 1) The high bits tend to be more random than the low bits. If % you wish to generate a random integer within a given range, you % should something like 'div' to reduce the random numbers to the % required range rather than something like 'mod' (or just use % random.random/5). % % 2) Similarly, you should not try to break a random number up into % components. Instead, you should generate each number with a % separate call to this module. % % 3) There can be sequential correlation between successive calls, % so you shouldn't try to generate tuples of random numbers, for % example, by generating each component of the tuple in sequential % order. If you do, it is likely that the resulting sequence will % not cover the full range of possible tuples. % %--------------------------------------------------% %--------------------------------------------------% :- module random. :- interface. :- import_module list. %--------------------------------------------------% % The type `supply' represents a supply of random numbers. % :- type supply. % init(Seed, RS). % % Creates a supply of random numbers RS using the specified Seed. % :- pred init(int::in, supply::uo) is det. % random(Num, !RS). % % Extracts a number Num in the range 0 .. RandMax from the random number % supply !RS. % :- pred random(int, supply, supply). :- mode random(out, in, out) is det. :- mode random(out, mdi, muo) is det. % random(Low, Range, Num, !RS). % % Extracts a number Num in the range Low .. (Low + Range - 1) from the % random number supply !RS. For best results, the value of Range should be % no greater than about 100. % :- pred random(int, int, int, supply, supply). :- mode random(in, in, out, in, out) is det. :- mode random(in, in, out, mdi, muo) is det. % randmax(RandMax, !RS). % % Binds RandMax to the maximum random number that can be returned from the % random number supply !RS, the state of the supply is unchanged. % :- pred randmax(int, supply, supply). :- mode randmax(out, in, out) is det. :- mode randmax(out, mdi, muo) is det. % randcount(RandCount, !RS). % % Binds RandCount to the number of distinct random numbers that can be % returned from the random number supply !RS. The state of the supply is % unchanged. This will be one more than the number returned by randmax/3. % :- pred randcount(int, supply, supply). :- mode randcount(out, in, out) is det. :- mode randcount(out, mdi, muo) is det. % permutation(List0, List, !RS). % % Binds List to a random permutation of List0. % :- pred permutation(list(T), list(T), supply, supply). :- mode permutation(in, out, in, out) is det. :- mode permutation(in, out, mdi, muo) is det. %--------------------------------------------------% %--------------------------------------------------%