Multi-Stream Lehmer RNGsDiscrete-Event Simulation:A First CourseSection 3.2: Multi-Stream Lehmer RNGsSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsSection 3.2: Multi-Stream Lehmer RNGsTypical DES models have many stochastic componentsWant a unique source of randomness for each componentOne (poor) option: multiple RNGsBetter option: one RNG with multiple “streams” of randomnumbersone stream per stochastic componentWe will partition output from our Lehmer RNG into multiplestreamsSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsExample 3.2.1: ssq2 Arrival and Service Processesssq2 has two stochastic comp onents : arrival and serviceAllocate a different generator state variable to eachGetService with Unique Seeddouble GetService(void){double s;static long x = 12345;PutSeed(x);s = Uniform(1.0, 2.0);GetSeed(&x);return (s);}x represents the current state of the service pro ces sSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsExample 3.2.2: ssq2 Arrival and Service ProcessesArrival should have its own static variable, initializeddifferentlyGetArrival with Unique Seeddouble GetArrival(void){static double arrival = START;static long x = 54321;PutSeed(x);arrival += Exponential(2.0);GetSeed(&x);return (arrival);}x represents the current state of arrival processSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsThe Modified Arrival and Service ProcessesAs modified, arrival and service times are drawn from differentstreams of random numbersNothing magic about the choice of seed for each stre amThe choices may, in fact, be poor ones!Provided the streams don’t overlap, the processes areuncoupledExecution time cost is negligible (see Example 3.2.3)Section 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsStream ConsiderationsPotential problem: assignment of initial seeds to facilitatestreamsEach initial state should be chosen to produce disjoint streamsIf states are picked at whim, no guarantee of disjoint streamsSome initial states may only be a few calls to Random apart..............................................................................................................................••(a, m) = (48271, 231− 1)1234554321Section 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsJump MultipliersWe will develop a multi-st ream version of rngTheorem (3.2.1)Given g(x) = ax mod m and integer j(1 < j < m − 1)Jump function : gj(x) = (ajmod m)x mod mJump multiplier : ajmod mIf g(·) generates x0, x1, x2, . . . then gj(·) generates x0, xj, x2j, . . .Theorem 3.2.1 is the key to creating streamsSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsExample 3.2.4: An Example Jump FunctionIf m = 31 and a = 3 and j = 6, the jump multiplier isajmod m = 36mod 31 = 16If x0= 1 then g(x) = 3x mod 31 generates1,3,9,27,19,26,16,17,20,29,25,13,8,24,10, 30,28,22,4,. . .The jump function g6(x) = 16x mod 31 generates1,16,8,4,2,. . .I.e., the first sequence is x0, x1, x2, . . .; the second isx0, x6, x12, . . .Section 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsUsing the Jump FunctionFirst, compute the jump multiplier ajmod m (one time cost)Then, gj(·) permits jumping from x0to xjto x2jto . . .The user supplies one initial seedIf j is chosen well, gj(·) can “plant” additional initial seedsEach planted seed corresponds to a different streamEach planted seed is separated by j calls to RandomSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsAn Example 4-Stream Sequence..............................................................................................................................••••(a, m) = (48271, 231− 1)x0xjx2jx3jSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsExample 3.2.5: An Appropriate Jump MultiplierConsider 256 = 28different streams of random numbersPartition the RNG output sequence into 256 disjointsubsequences of equal lengthFind the largest j < 231/28= 223such that the jumpmultiplier is modulus-compatiblegj(x) = (48271jmod m)x mod m can be implemented via Alg2.2.1Then gj(x) can be used to plant the other 255 initial seedsPossibility of stream overlap is minimized (though noteliminated!)Section 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsMaximal Modulus-Compatible Jump MultipliersMaximal jump multiplier : ajmod m where j is the largestinteger less than ⌊m/s⌋ such that ajmod m is moduluscompatibleExample 3.2.6: multipliers for (a, m) = (48271, 231− 1) RNG# of streams s ⌊m/s⌋ jump size j jump multiplierajmod m1024 2097151 2082675 97070512 4194303 4170283 44857256 8388607 8367782 22925128 16777215 16775552 40509Section 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsLibrary rngsrngs is an upward-compatible multi-stream replacement forrngBy default, provides 256 streams, indexed 0 to 255 (0 i s thedefault)Only one stream is active at any timeSix available functions:Random(void)PutSeed(long x): superseded by PlantSeedsGetSeed(long *x)TestRandom(void)SelectStream(int s): used to define the active streamPlantSeeds(long x): “plants” one seed per streamHenceforth, rngs is the library of choiceSection 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer RNGsExample 3.2.7: ssq2 RevisitedUse rngs functions for GetArrival, GetServiceGetArrival Methoddouble GetArrival(void) {static double arrival = START;SelectStream(0);arrival += Exponential(2.0);return (arrival);}GetService Methoddouble GetService(void) {SelectStream(2);return (Uniform(1.0, 2.0));}Include "rngs.h" and use PlantSeeds(12345)Section 3.2: Multi-Stream Lehmer RNGs Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Multi-Stream Lehmer