Multiplicative congruential random number generators with modulus 2^{𝛽}: an exhaustive analysis for 𝛽=32 and a partial analysis for 𝛽=48 (1990)

This paper presents the results of a search to find optimal maximal period multipliers for multiplicative congruential random number generators with moduli <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript 32"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>32</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^{32}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript 48"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>48</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^{48}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Here a multiplier is said to be optimal if the distance between adjacent parallel hyperplanes on which <italic>k</italic>-tuples lie does not exceed the minimal achievable distance by more than 25 percent for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k equals 2 comma ellipsis comma 6"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…<!-- … --></mml:mo> <mml:mo>,</mml:mo> <mml:mn>6</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">k = 2, \ldots ,6</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This criterion is considerably more stringent than prevailing standards of acceptability and leads to a total of only 132 multipliers out of the more than 536 million candidate multipliers that exist for modulus <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript 32"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>32</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^{32}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and to only 42 multipliers in a sample of about 67.1 million tested among the more than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="351 times 10 Superscript 11"> <mml:semantics> <mml:mrow> <mml:mn>351</mml:mn> <mml:mo>×<!-- × --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>10</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>11</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">351 \times {10^{11}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> candidate multipliers for modulus <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript 48"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>48</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^{48}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Section 1 reviews the basic properties of multiplicative congruential generators and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="section-sign 2"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">§<!-- § --></mml:mi> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\S 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> describes <italic>worst case</italic> performance measures. These include the maximal distance between adjacent parallel hyperplanes, the minimal number of parallel hyperplanes, the minimal distance between <italic>k</italic>-tuples and the discrepancy. For modulus <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript 32"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>32</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^{32}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="section-sign 3"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">§<!-- § --></mml:mi> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\S 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> presents the ten best multipliers and compares their performances with those of two multipliers that have been recommended in the literature. Comparisons using packing measures in the space of <italic>k</italic>-tuples and in the dual space are also made. For modulus <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript 48"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>48</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^{48}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="section-sign 4"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">§<!-- § --></mml:mi> <mml:mn>4</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\S 4</mml:annotation> </mml:semantics> </mml:math> </inline-formula> also presents analogous results for the five best multipliers and for two multipliers suggested in the literature.