CPE 619 Random-Number GenerationOverviewRandom-Number GenerationA Sample GeneratorTerminologyDesired Properties of a Good GeneratorTypes of Random-number GeneratorsLinear-Congruential GeneratorsLinear-Congruential Generators (cont’d)Selection of LCG ParametersSelection of LCG Parameters (cont’d)Period vs. AutocorrelationMultiplicative LCGMultiplicative LCG with m=2kExample 26.1aExample 26.1bMultiplicative LCG with m¹2kExample 26.2Schrage's MethodExample 26.3Generator Using Integer ArithmeticGenerator Using Real ArithmeticTausworthe GeneratorsTausworthe Generators (cont’d)Example 26.4Example 26.4 (cont’d)Combined GeneratorsCombined Generators (cont’d)Slide 43Slide 44Survey of Random-Number GeneratorsSurvey of RNG’s (cont’d)Slide 47Survey of RNG’s (Cont)Slide 49Seed SelectionSeed Selection (cont’d)Table of SeedsMyths About Random-Number GenerationMyths (cont’d)Slide 55Example 26.7Example 26.7 (cont’d)SummaryCPE 619Random-Number GenerationAleksandar MilenkovićThe LaCASA LaboratoryElectrical and Computer Engineering DepartmentThe University of Alabama in Huntsvillehttp://www.ece.uah.edu/~milenkahttp://www.ece.uah.edu/~lacasa2OverviewDesired properties of a good generatorLinear-congruential generatorsTausworthe generatorsSurvey of random number generatorsSeed selectionMyths about random number generation3Random-Number GenerationRandom Number = Uniform(0, 1)Random Variate = Other distributions = Function(Random number)4A Sample GeneratorFor example,Starting with x0=5:The first 32 numbers obtained by the above procedure 10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5; 10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5. By dividing x's by 16:0.6250, 0.1875, 0.0000, 0.0625, 0.3750, 0.9375, 0.7500, 0.8125, 0.1250, 0.6875, 0.5000, 0.5625, 0.8750, 0.4375, 0.2500, 0.3125; 0.6250, 0.1875, 0.0000, 0.0625, 0.3750, 0.9375, 0.7500, 0.8125, 0.1250, 0.6875, 0.5000, 0.5625, 0.8750, 0.4375, 0.2500, 0.3125.5TerminologySeed = x0 Pseudo-Random: Deterministic yet would pass randomness testsGenerator function is known (preferred in simulations)Fully Random: Not repeatable Cycle length, Tail, PeriodGoal: Select appropriate generator function and appropriate value for seed6Desired Properties of a Good GeneratorIt should be efficiently computableRepeated many times during a simulationThe period should be largeTo benefit from possibly long simulationsThe successive values should be independent and uniformly distributed The correlation between successive numbers should be small (discussed in Chapter 27)7Types of Random-number GeneratorsLinear congruential generatorsTausworthe generatorsExtended Fibonacci generatorsCombined generators8Linear-Congruential GeneratorsDiscovered by D. H. Lehmer in 1951The residues of successive powers of a number have good randomness propertiesEquivalently,a = multiplierm = modulus9 Linear-Congruential Generators (cont’d)Lehmer's choices: a=23 and m=108+1Good for ENIAC, an 8-digit decimal machine Generalization:Can be analyzed easily using the theory of congruences  Mixed Linear-Congruential Generators or Linear-Congruential Generators (LCG)Mixed = both multiplication by a and addition of b10Selection of LCG ParametersChoice of a, b, and m affect the period and autocorrelation 1) The modulus m should be largeAll x’s are between 0 and m-1,the period can never be more than m2) For mod m computation to be efficient, m should be a power of 2  Mod m can be obtained by truncation11Selection of LCG Parameters (cont’d)3) If b is nonzero, the maximum possible period m is obtained if and only if:Integers m and b are relatively prime, that is, have no common factors other than 1Every prime number that is a factor of m is also a factor of a-1If integer m is a multiple of 4, a-1 should be a multiple of 4Notice that all of these conditions are met if m=2k, a = 4c + 1, and b is oddHere, c, b, and k are positive integers12Period vs. AutocorrelationA generator that has the maximum possible period is called a full-period generatorLower autocorrelations between successive numbers are preferable Both generators have the same full period, but the first one has a correlation of 0.25 between xn-1 and xn, whereas the second one has a negligible correlation of less than 2-1813Multiplicative LCGMultiplicative LCG: b=0Two types:m = 2km  2k14Multiplicative LCG with m=2km = 2ktrivial divisionMaximum possible period 2k-2Period achieved if multiplier a is of the form 8i3, and the initial seed is an odd integerOne-fourth the maximum possible may not be too smallLow order bits of random numbers obtained using multiplicative LCG's with m=2k have a cyclic pattern15Example 26.1aUsing a seed of x0=15, 25, 29, 17, 21, 9, 13, 1, 5,…Period = 8 = 32/4With x0=2, the sequence is 10, 18, 26, 2, 10, …Here, the period is only 416Example 26.1bMultiplier not of the form 8i  3:Using a seed of x0=1, we get the sequence 7, 17, 23, 1, 7,…The period is only 417Multiplicative LCG with m2kModulus m = prime numberWith a proper multiplier a, period = m-1Maximum possible period = mIf and only if the multiplier a is a primitive root of the modulus m a is a primitive root of m if and only if an mod m 1 for n = 1, 2, …, m-218Example 26.2Starting with a seed of x0=11, 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15, 14, 11, 2, 6, 18, 23, 7, 21, 1, …The period is 303 is a primitive root of 31 With a multiplier of a = 5 1, 5, 25, 1,…The period is only 3 5 is not a primitive root of 31Primitive roots of 31= 3, 11, 12, 13, 17, 21, 22, and 2419Schrage's MethodPRN computation assumes: No round-off errors, integer arithmetic, and no overflowsRound-off errors: if computation is done using real numbers  Can't do it in BASICProduct a xn-1 > Largest integerOverflow => Use Scharge’s methodIdentity: Where:And:Here, q = m div a, r = m mod a`A div B' = dividing A by B and truncating the resultFor all x's in the range 1, 2, …, m-1, computing g(x) involves numbers less than m-1If r < q, h(x) is either 0 or 1, and it can be inferred from g(x);h(x) is 1 if and only if g(x) is negative20Example 26.3231-1 = 2147483647 = prime number 75 =