BS ISO28640:2010ICS 03.120.30NO COPYING WITHOUT BSI PERMISSION EXCEPT AS PERMITTED BY COPYRIGHT LAWBRITISH STANDARDRandom variategeneration methodsThis British Standardwas published under theauthority of the StandardsPolicy and StrategyCommittee on 30 June2010© BSI 2010ISBN 978 0 580 57787 1Amendments/corrigenda issued since publicationDate CommentsBS ISO 28640:2010National forewordThis British Standard is the UK implementation of ISO 28640:2010.The UK participation in its preparation was entrusted to TechnicalCommittee SS/5, Acceptance sampling schemes.A list of organizations represented on this committee can be obtained onrequest to its secretary.This publication does not purport to include all the necessary provisionsof a contract. Users are responsible for its correct application.Compliance with a British Standard cannot confer immunityfrom legal obligations.BS ISO 28640:2010Reference numberISO 28640:2010(E)©ISO 2010INTERNATIONAL STANDARD ISO28640First edition2010-03-15Random variate generation methods Méthodes de génération de nombres pseudo-aléatoires BS ISO 28640:2010ISO 28640:2010(E) PDF disclaimer This PDF file may contain embedded typefaces. In accordance with Adobe s licensing policy, this file may be printed or viewed but shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In downloading this file, parties accept therein the responsibility of not infringing Adobe s licensing policy. The ISO Central Secretariat accepts no liability in this area. Adobe is a trademark of Adobe Systems Incorporated. Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below. COPYRIGHT PROTECTED DOCUMENT © ISO 2010 All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or ISO s member body in the country of the requester. ISO copyright office Case postale 56 • CH-1211 Geneva 20 Tel. + 41 22 749 01 11 Fax + 41 22 749 09 47 E-mail

[email protected] Web www.iso.org Published in Switzerland ii © ISO 2010 – All rights reservedBS ISO 28640:2010ISO 28640:2010(E) © ISO 2010 – All rights reserved iiiContents Page Foreword iv Introduction.v 1 Scope1 2 Normative references1 3 Terms and definitions .1 4 Symbols and mathematical binary operations.2 4.1 Symbols2 4.2 Mathematical binary operations 2 5 Uniformly distributed pseudo-random numbers3 5.1 General .3 5.2 M-sequence method definition 3 5.3 Pentanomial GFSR method 4 5.4 Combined Tausworthe method4 5.5 Mersenne Twister method 5 6 Generation of random numbers from various distributions.6 6.1 Introduction6 6.2 Uniform distribution 6 6.3 Standard beta distribution7 6.4 Triangular distribution 8 6.5 General exponential distribution with location and scale parameters 8 6.6 Normal distribution .9 6.7 Gamma distribution.9 6.8 Weibull distribution .11 6.9 Lognormal distribution .11 6.10 Logistic distribution 11 6.11 Multivariate normal random variate generation .12 6.12 Binomial distribution.12 6.13 Poisson distribution14 6.14 Discrete uniform distribution .14 Annex A (informative) Table of physical random numbers 16 A.1 Table of random numbers 16 A.2 Method of physical random number generation17 Annex B (informative) Algorithm for pseudo-random number generation.18 B.1 Program code for the trinomial GFSR method.18 B.2 Program code for the pentanomial GFSR method.22 B.3 Program code for the combined Tausworthe method.28 B.4 Program code for the Mersenne Twister method 32 B.5 Linear congruential method .38 B.6 Reference examples52 Bibliography53 BS ISO 28640:2010ISO 28640:2010(E) iv © ISO 2010 – All rights reservedForeword ISO (the International Organization for Standardization) is a worldwide federation of national standards bodies (ISO member bodies). The work of preparing International Standards is normally carried out through ISO technical committees. Each member body interested in a subject for which a technical committee has been established has the right to be represented on that committee. International organizations, governmental and non-governmental, in liaison with ISO, also take part in the work. ISO collaborates closely with the International Electrotechnical Commission (IEC) on all matters of electrotechnical standardization. International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2. The main task of technical committees is to prepare International Standards. Draft International Standards adopted by the technical committees are circulated to the member bodies for voting. Publication as an International Standard requires approval by at least 75 % of the member bodies casting a vote. Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. ISO shall not be held responsible for identifying any or all such patent rights. ISO 28640 was prepared by Technical Committee ISO/TC 69, Applications of statistical methods. This is the first edition. BS ISO 28640:2010ISO 28640:2010(E) © ISO 2010 – All rights reserved vIntroduction This International Standard specifies typical algorithms by which the users can regard the generated numerical sequences as if they were real random variates. Nowadays most statisticians, scientists and engineers have enough computer power at their disposal to carry out large computer simulations, and it is important that these be based on sound pseudo-random generators. This International Standard has been developed to help ensure that randomization, where needed, is carried out correctly and efficiently. Six uses of randomization can be identified in statistical standardization: ⎯ selection of a random sample; ⎯ analysis of sample data; ⎯ development of standards; ⎯ checking theoretical results; ⎯ demonstrating that a proposed procedure has the properties claimed of it; ⎯ resolving uncertainty in the statistical literature. BS ISO 28640:2010BS ISO 28640:2010INTERNATIONAL STANDARD ISO 28640:2010(E)© ISO 2010 – All rights reserved 1Random variate generation methods 1 Scope This International Standard specifies methods for generating uniform and non-uniform random variates for Monte Carlo simulation purposes. Cryptographic random number generation methods are not included. This International Standard is applicable, inter alia, by ⎯ researchers, industrial engineers or experts in operations management, who use statistical simulation, ⎯ statisticians who need randomization related to SQC methods, statistical design of experiments or sample surveys, ⎯ applied mathematicians who plan complex optimization procedures that require the use of Monte Carlo methods, and ⎯ software engineers who implement algorithms for random variate generation. 2 Normative references The following referenced documents are indispensable for the application of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies. ISO/IEC 2382-1, Information technology — Vocabulary — Part 1: Fundamental terms ISO 3534-1, Statistics — Vocabulary and symbols — Part 1: General statistical terms and terms used in probability ISO 3534-2, Statistics — Vocabulary and symbols — Part 2: Applied statistics 3 Terms and definitions For the purposes of this document, the terms and definitions given in ISO/IEC 2382-1, ISO 3534-1 and ISO 3534-2 apply, except where redefined below. 3.1 random variate random number number as the realization of a specific random variable NOTE 1 The term “random number” is often used for uniformly distributed random variate. NOTE 2 Random numbers provided as a sequence are called a “random number sequence”. BS ISO 28640:2010ISO 28640:2010(E) 2 © ISO 2010 – All rights reserved3.2 pseudo-random number random number (3.1) generated by an algorithm, that appears to be random NOTE If there is no fear of misunderstanding, a pseudo-random number may simply be called a “random number”. 3.3 physical random number random number (3.1) generated by a physical mechanism 3.4 binary random number sequence random number (3.1) sequence consisting of zeros and ones 3.5 seed initialization value required for pseudo-random number generation 4 Symbols and mathematical binary operations 4.1 Symbols For the purposes of this document, the symbols given in the normative references as the latest versions of ISO/IEC 2382-1, ISO 3534-1 and ISO 3534-2 apply, except where redefined below. The symbols and abbreviations specifically used in this International Standard are as follows: X integer type uniform random number U standard uniform random number Z normal random variate n suffix of random number sequence 4.2 Mathematical binary operations The mathematical binary operations specifically used in this International Standard are as follows: mod(m; k) residue from dividing integer m by k m ⊕ k bitwise exclusive logical disjunction of binary integers m and k EXAMPLE 1 1 ⊕ 1 = 0 0 ⊕ 1 = 1 1 ⊕ 0 = 1 0 ⊕ 0 = 0 1010 ⊕ 1100 = 0110 BS ISO 28640:2010ISO 28640:2010(E) © ISO 2010 – All rights reserved 3m ∧ k bitwise logical conjunction of binary integers m and k EXAMPLE 2 1 ∧ 1 = 1 0 ∧ 1 = 0 1 ∧ 0 = 0 0 ∧ 0 = 0 1010 ∧ 1100 = 1000 m := k replaces value m by k m k k-bit right shift of binary integer m m 1 (when the last bit of X = 0) XA = (X 1) ⊕ a (when the last bit of X = 1) Here, X is regarded as a w dimensional 0-1 vector. BS ISO 28640:2010ISO 28640:2010(E) 6 © ISO 2010 – All rights reservedNOTE The necessary amount of memory for this computation is p words, the period becomes 2pw−r− 1, and the efficiency is better than that of the GFSR methods described previously. To improve the randomness of the first w − r bits, the following series of conversions can be applied to Xn. y := Xny := y ⊕ (y u) y := y ⊕ [(y l) where b, c are constant bits masks to improve the randomness of the first w − r bits. The parameters of this algorithm are (p, q, r, w, a, u, s, t, l, b, c). The seeds are X2, ., Xq + 1and the first w − r bits of X1. The final value of y is the pseudo-random number. 6 Generation of random numbers from various distributions 6.1 Introduction Methods of generating random numbers Y from various distributions by using uniform random numbers X of integer type, are described below. The distribution function is denoted by F(y). If it is a continuous distribution, its probability density function is denoted by f(y), and if it is a discrete distribution, its probability mass function is denoted by p(y). 6.2 Uniform distribution 6.2.1 Standard uniform distribution 6.2.1.1 Probability density function 1, 0 1()0, otherwiseyfy⎧=⎨⎩uu6.2.1.2 Random variate generation method If the maximum value of uniform random number X of integer type is m − 1, the following formula should be used to generate standard uniform random numbers. XUm= EXAMPLE For any w-bit integer sequences generated by the method described in 5.2 through 5.5, m = 2. NOTE 1 Because X takes on discrete values, the values of U are also discrete. NOTE 2 The value of U never becomes 1,0. The value of U becomes 0,0 only when X = 0. In the case of M-sequence random numbers, any generation method may cause this phenomenon. NOTE 3 Random numbers from the standard uniform distribution are called standard uniform random numbers, and are represented by U1, U2, … They are assumed to be independent of each other. BS ISO 28640:2010ISO 28640:2010(E) © ISO 2010 – All rights reserved 76.2.2 General uniform distribution 6.2.2.1 Probability density function 1/ , ()0, otherwise bayabfy+⎧=⎨⎩uuwhere b 0. 6.2.2.2 Random variate generation method If the standard uniform random number U is generated by the method specified in 6.2.1.2, then the general uniform random number should be generated by the following formula: YbUa=+ 6.3 Standard beta distribution 6.3.1 Probability density function ()()11101,()Β ,otherwise0, dcyyyfycd−−⎧−⎪=⎨⎪⎩uuwhere () ( )1110Β ,1ddccd x x x−−=−∫is the beta function and the parameters c and d are greater than 0. 6.3.2 Random variate generation method by Jöhnk If the standard uniform random numbers U1and U2are independently generated by the method specified in 6.2.1, then the standard beta random number Y should be generated by the following procedures. If 1/ 1/12cdYU U=+is less than or equal to 1, set 1/1/cYU Y=; otherwise, generate two standard uniform random numbers again until the inequality is satisfied. 6.3.3 Random variate generation method by Cheng If the standard uniform random numbers U1and U2are independently generated by the method specified in 6.2.1, then the standard beta random number Y should be generated by the following procedures. [Set-up] a) Let () (,)2()21min , , if min, otherwisecd cdqcd c dcd0. 6.4.2 Random variate generation method If the standard uniform random numbers U1and U2are independently generated by the method specified in 6.2.1, then the triangular random number Y should be generated by ()121YabUU=+ + −. 6.5 General exponential distribution with location and scale parameters 6.5.1 Probability density function {}()/()1exp , 0, yaby afy bya⎧−−⎪=⎨⎪1/3 a) Set () /( )31/3, , ln , 1 3rc s rtrrrp s=− = =− = and .3qr=− b) Generate standard normal random number Z. c) If Z −In(1,0 − U), then go to b). NOTE This method is based on the Wilson-Hilferty transformation of chi-square distributions to an approximate standard normal distribution. The accuracy of this approximation depends on the parameter values of c, and the dependency is rather complicated. A very rough idea is as follows: the absolute difference between the percentage point of the approximate distribution and the exact distribution is always less than 0,2. 6.7.2.5 Exact generation method when c 1/2, by Cheng a) Set q = c – ln 4 and 2 1rc c=+ −. b) Generate standard uniform random numbers U1and U2. c) Set (), (),211121ln exp1UVc Wc UZUUU===−and R = q + rV − W. d) If R W 4,5Z − (1 + In 4,5) then employ Y = a + bW and stop. e) If R W InZ then employ Y = a + bW and stop. f) Go to b). BS ISO 28640:2010ISO 28640:2010(E) © ISO 2010 – All rights reserved 11()11/2 , 21211121 1 ln4 1 ln 4,5 (1 ln4,5)ppUUpcqc rccqpr c UUYabcU⎛⎞⎛⎞= − =− =+ − + − − +⎜⎟⎜⎟−−⎝⎠⎝⎠⎛⎞=+⎜⎟−⎝⎠W6.8 Weibull distribution 6.8.1 Probability distribution function ()1exp , 0, cyayaFy bya⎧ ⎧⎫−⎪⎪⎛⎞⎪ −−⎪⎨ ⎬⎜⎟=⎝⎠⎨⎪⎪⎩⎭⎪0. 6.13.2 Method of using a relationship with an exponential distribution Generate standard uniform random numbers U1, U2, ., and let Y be the