|
In computer science, multiply-with-carry (MWC) is a method invented by George Marsaglia for generating sequences of random integers based on an initial set from two to many thousands of randomly chosen seed values. The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around 260 to 22000000. As with most pseudorandom number generators, the resulting sequences are functions of the randomly chosen seed values. ==General theory== A MWC sequence is based on arithmetic modulo a base ''b'', usually ''b'' = 232, because arithmetic modulo of that ''b'' is automatic in most computers. However, sometimes a base such as ''b'' = 232 − 1 is used, because arithmetic for modulus 232 − 1 requires only a simple adjustment from that for 232, and theory for MWC sequences based on modulus 232 has some nagging difficulties avoided by using ''b'' = 232 − 1. In its most common form, a lag-r MWC generator requires a base ''b'', a multiplier ''a'', and a set of ''r+1'' random seed values, consisting of ''r'' residues of ''b'', :''x''0, ''x''1, ''x''2 ,..., ''x''''r''−1, and an initial carry ''c''r''−1'' < ''a''. The lag-''r'' MWC sequence is then a sequence of pairs ''x''''n'', ''c''''n'' determined by : and the MWC generator output is the sequence of ''xs, :''x''''r'' , ''x''''r''+1 , ''x''''r''+2, ... The period of a lag-''r'' MWC generator is the order of ''b'' in the multiplicative group of numbers modulo ''abr'' − 1. It is customary to choose ''as so that ''p = abr'' − 1 is a prime for which the order of ''b'' can be determined. Because 2 is a quadratic residue of numbers of the form ''8k±1'', ''b'' = 232 cannot be a primitive root of ''p = abr'' − 1. Therefore there are no MWC generators for base 232 that have the maximum possible period, one of the difficulties that use of ''b'' = 232 − 1 overcomes. A theoretical problem with MWC generators, pointed out by Couture and l'Ecuyer (1997) is that the most significant bits are slightly biased; complementary-multiply-with-carry generators do not share this problem: "We shall see that, for the complementary MWC, each bit of the output value is fair, that is, the two binary digits will appear equally often in a full period, a property not shared by MWC generators." They do not appear to elaborate further as to the extent of the bias. Complementary-multiply-with-carry generators also require slightly more computation time per iteration, so there is a tradeoff to evaluate depending on implementation requirements. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Multiply-with-carry」の詳細全文を読む スポンサード リンク
|