![]() |
![]() |
![]() |
![]() |
![]() |
Abstract Data Type for Random Numbers
One important feature, especially in performance simulations, is the possibility to generate random numbers according to a number of distributions, like for example the negative exponential distribution and the Erlang distribution. It is also important that the random number sequences are reproducible, to be able to run a slightly modified version of a simulation with the same sequence of random numbers.
In this section an SDL abstract data type according to the previous discussion is presented. This data type may be included in any SDL system. This ADT can also be used in OS integrations and in Cmicro. It is, however, necessary to check that the typedef for the RandomControl, see below, refers to an unsigned 32-bit type.
Purpose
The SDL RandomControl data type allows you to generate pseudo-random numbers. A number of distributions are supported, including the negative exponential distribution and the Erlang distribution. In performance simulations, which is the main application area for this data type, the most important need for random numbers is in connection with Time and Duration values. It is, for example, interesting to draw inter- arrival times in job generators, and service lengths in servers. Distributions returning positive real numbers are thus most meaningful.
The basic mechanism behind pseudo-random number generation is as follows. A sequence of bit-patterns is defined using a formula of type:
![]()
The function f should be such that the sequence of elements seen as numbers should be "random", and the number of element in the sequence, before it starts to repeat itself, should be as large as possible.
To obtain a new random number is thus a two step process:
- Compute and store a new bit-pattern from the old bit-pattern
- Interpret the new bit-pattern as a number, which is returned as the new random number.
In this data type, 32 bit patterns, implemented in C using the type unsigned long, are used together with the formula:
![]()
The result returned by the operator Random, which is the basic random number generator, is this bit-pattern seen as a number between 0 and 1, and expressed as a float.
The data type RandomControl may be included in any SDL system using an analyzer include statement, where the file containing the definition of the data type is included. Example:
/*#include 'random.pr' */As the C standard functions log and exp are used in the random.pr file, it is necessary to link the application together with the library for math functions, i.e. to have -lm in the link operation in the makefile. See Makefile Options. To use the entry -lm in the link list seems to be a fairly standard way to find the library for math functions. If this does not work, or you want more details, please see the documentation for your C compiler.
Available Operators
The type RandomControl, introduced by this data type, is in C implemented as the address of an unsigned long.
typedef unsigned long * RandomControl;Note that you have check that unsigned long is a 32 bit type, otherwise you have to change the typedef.
The reason for passing the address to the bit-pattern (that is to the unsigned long), is that this bit-pattern has to be updated by the random functions.
Below the operators provided in this data type are listed. There are, for many of the operators, several versions with different sets of parameters and/or result types to support different usage of the operator.
Random : RandomControl -> Real;Random : RandomControl -> Duration;Random : RandomControl -> Time;Erlang : Real, Integer, RandomControl -> Real;Erlang : Real, Integer, RandomControl -> Duration;Erlang : Real, Integer, RandomControl -> Time;Erlang : Duration, Integer, RandomControl -> Real;Erlang : Duration, Integer, RandomControl -> Duration;Erlang : Duration, Integer, RandomControl -> Time;Erlang : Time, Integer, RandomControl -> Real;Erlang : Time, Integer, RandomControl -> Duration;Erlang : Time, Integer, RandomControl -> Time;HyperExp2 :Real, Real, Real, RandomControl -> Real;HyperExp2 :Real, Real, Real, RandomControl -> Duration;HyperExp2 :Real, Real, Real, RandomControl -> Time;HyperExp2 :Duration, Duration, Real, RandomControl -> Real;HyperExp2 :Duration, Duration, Real, RandomControl -> Duration;HyperExp2 :Duration, Duration, Real, RandomControl -> Time;HyperExp2 :Time, Time, Real, RandomControl -> Real;HyperExp2 :Time, Time, Real, RandomControl -> Duration;HyperExp2 :Time, Time, Real, RandomControl -> Time;NegExp : Real, RandomControl -> Real;NegExp : Real, RandomControl -> Duration;NegExp : Real, RandomControl -> Time;NegExp : Duration, RandomControl -> Real;NegExp : Duration, Rando mControl -> Duration;NegExp : Duration, RandomControl -> Time;NegExp : Time, RandomControl -> Real;NegExp : Time, RandomControl -> Duration;NegExp : Time, RandomControl -> Time;Uniform : Real, Real, RandomControl -> Real;Uniform : Real, Real, RandomControl -> Duration;Uniform : Real, Real, RandomControl -> Time;Uniform : Duration, Duration, RandomControl -> Real;Uniform :Duration, Duration, RandomControl -> Duration;Uniform : Duration, Duration, RandomControl -> Time;Uniform : Time, Time, RandomControl -> Real;Uniform : Time, Time, RandomControl -> Duration;Uniform : Time, Time, RandomControl -> Time;Draw : Real, RandomControl -> Boolean;Geometric : Real, RandomControl -> Integer;Geometric : Real, RandomControl -> Duration;Geometric : Real, RandomControl -> Time;Geometric : Duration, RandomControl -> Integer;Geometric : Duration, RandomControl -> Duration;Geometric : Duration, RandomControl -> Time;Geometric : Time, RandomControl -> Integer;Geometric : Time, RandomControl -> Duration;Geometric : Time, RandomControl -> Time;Poisson : Real, RandomControl -> Integer;Poisson : Real, RandomControl -> Duration;Poisson : Real, RandomControl -> Time;Poisson : Duration, RandomControl -> Integer;Poisson : Duration, RandomControl -> Duration;Poisson : Duration, RandomControl -> Time;Poisson : Time, RandomControl -> Integer;Poisson : Time, RandomControl -> Duration;Poisson : Time, RandomControl -> Time;RandInt : Integer, Integer, RandomControl -> Integer;RandInt : Integer, Integer, RandomControl -> Duration;RandInt : Integer, Integer, RandomControl -> Time;DefineSeed : Integer -> RandomControl;GetSeed : Charstring -> Integer;Seed : RandomControl -> Integer;Random (RandomControl)
The operator Random is the basic random generator and is called by all the other operators. Random uses the formula
![]()
to compute the next value stored in the parameter of type RandomControl. The result from Random is a real random number in the interval 0.0 < Value < 1.0.
Erlang (Mean, N, RandomControl)
The operator Erlang provides random numbers from the Erlang-N distribution with mean Mean. The first parameter Mean should be > 0.0, and the second parameter N should be > 0.
HyperExp2 (Mean1, Mean2, Alpha, RandomControl)
The HyperExp2 operator provides random numbers from the hyperexponential distribution. With probability Alpha it return a random number from the negative exponential distribution with mean Mean1, and with the probability 1-Alpha it returns a random number from the negative exponential distribution with mean Mean2. Mean1 and Mean2 should be > 0.0, and Alpha should be in the range 0.0 <= Alpha <= 1.0.
NegExp (Mean, RandomControl)
The operator NegExp provides random numbers from the negative exponential distribution with mean Mean. Mean should be > 0.0.
Uniform (Low, High, RandomControl)
The operator Uniform is given a range Low to High and returns a uniformly distributed random number in this range.
Low should be <= High.Draw (Alpha, RandomControl)
The Draw operator returns true with the probability Alpha and false with the probability 1-Alpha. Alpha should be in the range
0.0 <= Alpha <= 1.0.Geometric (p, RandomControl)
The operator Geometric returns an integer random number according to the geometric distribution with the mean p/(1-p). The parameter p should be 0.0 <= p < 1.0.
Since the range of feasible samples from the distribution is infinite and the result type is integer, integer overflow may occur.
Poisson (m, RandomControl)
The operator Poisson returns an integer random number according to the Poisson distribution with mean m. The parameter m should be >= 0.0.
Since the range of feasible samples from the distribution is infinite and the result type is integer, integer overflow may occur.
RandInt (Low, High, RandomControl)
This operator RandInt returns one of the values Low, Low+1,..., High-1, High, with equal probability. Low should be <= High.
DefineSeed (Integer) -> RandomControl
Each RandomControl variable, which is used as a control variable for a random generator, has to be initialized correctly so the first bit-pattern used by the basic random function is a legal pattern. This DefineSeed operator takes an integer parameter, which should be an odd value in the range 1 to 32767, and creates a legal bit-pattern. This first value is usually referred to as the seed for the random generator. Using the same seed value, the same random number sequence is generated, which means that the random number sequences are reproducible.
Seed (RandomControl) -> Integer
The Seed operator returns random numbers that are acceptable as parameters to the operator DefineSeed. If many RandomControl variables are to be initialized, the Seed operator may be useful.
GetSeed (Prompt) -> Integer
The GetSeed operator, which is implemented in the data type TextFile (see The ADT TextFile), may be used to read an integer value that is acceptable as parameter to the DefineSeed operator.
Using the Data Type
To use the abstract data type for random number generation you must:
- Include the definition of the data type using an analyzer include. Usually it is appropriate to include the data type in a text symbol in the system diagram.
- Define a suitable number of RandomControl variables, one for each random number sequence that is to be used.
- Initialize the RandomControl variables, either in the variable declaration or in a TASK often placed in the start transition of the process. The operator DefineSeed should be used to initialize a RandomControl variable.
- Use the RandomControl variables in appropriate random number operators.
SDL variables can only be declared in processes and will be local to the process instances.
To have global RandomControl variables you may, however, define synonyms of type RandomControl and use them in random generator operators.
Example 541 : Using RandomControl, DefineSeed
SYNONYM Seed1 RandomControl =DefineSeed(GetSeed(stdin, 'Seed1 : '));TASK Delay := NegExp(Mean1, Seed1);This is correct according to SDL as operators only have IN parameters and therefore expressions are allowed as actual parameters. In C it is also an IN parameter and cannot be changed. But as a RandomControl value is an address it is possible to change the contents in that address.
The SDL to C Compiler will, for synonyms that cannot be computed at generation time, allocate a variable and initialize it according to the synonym definition at start-up time. Note that this will be performed before any transitions have been executed.
A typical application of RandomControl synonyms are together with the Seed operator. The Seed operator is used to generate values suitable to initialize RandomControl variables with.
Example 542 : Using RandomControl, Seed
SYNONYM BasicSeed RandomControl =DefineSeed(GetSeed(stdin, 'Seed : '));DCL S1 RandomControl :=DefineSeed(Seed(BasicSeed));DCL S2 RandomControl :=DefineSeed(Seed(BasicSeed));The variety of operators with the same name makes it possible to directly use operators in many more situations. This is called overloading of operators. If, for example, there were only the NegExp version:
NegExp : Real, RandomControl -> Real;then explicit conversion operators would have been necessary to draw, for example, a Duration value from the negative exponential distribution. The code to draw a Duration value would then be something like:
RealToDuration(NegExp(Mean, Seq))We have instead introduced several operators with the same name and purpose, but with different combinations of parameter types and result type. So for the NegExp operator discussed above, there is also a version:
NegExp : Real, RandomControl -> Duration;which is exactly what we wanted.
There is, however, a price to be paid for having overloaded operators. It must be possible for the SDL Analyzer to tell which operator that is used in a particular situation. It then uses all available information about the parameters and what the result is used for. Consider Example 543 below.
Example 543 : Overloaded Operator
TIMER T;DCLMean, Rand Real,D Duration,Seq RandomControl :=DefineSeed(GetSeed('Seed : '));TASK Rand := NegExp(Mean, Seq);TASK D := NegExp(Mean, Seq);TASK D := NegExp(TYPE Real 1.5, Seq);DECISION NegExp(Mean, Seq) >TYPE Duration 10.0;(true) : ....ELSE :ENDDECISION;SET (Now + NegExp(Mean, Seq), T);
- The first two applications of NegExp are no problem, as the parameter type is given by the type of the Mean variable, and the result type is given by the variable that result is assigned to.
- In the third NegExp call, the value 1.5 has to be given a qualifier, that is, TYPE Real, as the literal 1.5 may be of type Real, Duration, or Time.
- In the fourth example it is the result type that cannot be determined if the literal 10.0 was not given with a qualifier.
- In the fifth example the only + operator that takes Time as left parameter and returns Time (SET should have a Time value as first parameter) is:
"+" : Time, Duration -> Time;Most of these problems can be avoided by using SYNONYMS or variables instead of literal values. This is in most cases a better solution than to introduce qualifiers.
If, for example, the synonyms:
SYNONYM MeanValue Real = 1.5;SYNONYM Limit Duration = 10.0;were defined, the third and fourth NegExp call would cause no problem:
TASK D := NegExp(MeanValue, Seq);DECISION NegExp(Mean, Seq) > Limit;(true) : ....ELSE :ENDDECISION;Trace Printouts
Trace printouts are available for the functions in this abstract data type. By assigning a trace value greater or equal to nine (9) using the monitor command Set-Trace, each call to an operator in this data type causes a printout of the name of the operator.
Each operator returning a random number will call the basic operator Random at least once.
Accessing the Operators from C
The operator for random number generation may be used directly in C by using the name given in the appropriate #NAME directive. Please look at the random.pr file for the #NAME directives.
http://www.ibm.com/rational |
![]() |
![]() |
![]() |
![]() |