+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
22.0 KiB374 linesraw
1/**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements.  See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership.  The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License.  You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18package org.apache.hadoop.examples.terasort;
19
20/**
21 * This class implements a 128-bit linear congruential generator.
22 * Specifically, if X0 is the most recently issued 128-bit random
23 * number (or a seed of 0 if no random number has already been generated,
24 * the next number to be generated, X1, is equal to:
25 * X1 = (a * X0 + c) mod 2**128
26 * where a is 47026247687942121848144207491837523525
27 *            or 0x2360ed051fc65da44385df649fccf645
28 *   and c is 98910279301475397889117759788405497857
29 *            or 0x4a696d47726179524950202020202001
30 * The coefficient "a" is suggested by:
31 * Pierre L'Ecuyer, "Tables of linear congruential generators of different
32 * sizes and good lattice structure", Mathematics of Computation, 68
33 * pp. 249 - 260 (1999)
34 * http://www.ams.org/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf
35 * The constant "c" meets the simple suggestion by the same reference that
36 * it be odd.
37 *
38 * There is also a facility for quickly advancing the state of the
39 * generator by a fixed number of steps - this facilitates parallel
40 * generation.
41 *
42 * This is based on 1.0 of rand16.c from Chris Nyberg 
43 * <chris.nyberg@ordinal.com>.
44 */
45class Random16 {
46
47  /** 
48   * The "Gen" array contain powers of 2 of the linear congruential generator.
49   * The index 0 struct contain the "a" coefficient and "c" constant for the
50   * generator.  That is, the generator is:
51   *    f(x) = (Gen[0].a * x + Gen[0].c) mod 2**128
52   *
53   * All structs after the first contain an "a" and "c" that
54   * comprise the square of the previous function.
55   *
56   * f**2(x) = (Gen[1].a * x + Gen[1].c) mod 2**128
57   * f**4(x) = (Gen[2].a * x + Gen[2].c) mod 2**128
58   * f**8(x) = (Gen[3].a * x + Gen[3].c) mod 2**128
59   * ...
60
61   */
62  private static class RandomConstant {
63    final Unsigned16 a;
64    final Unsigned16 c;
65    public RandomConstant(String left, String right) {
66      a = new Unsigned16(left);
67      c = new Unsigned16(right);
68    }
69  }
70
71  private static final RandomConstant[] genArray = new RandomConstant[]{
72    /* [  0] */ new RandomConstant("2360ed051fc65da44385df649fccf645", 
73                                   "4a696d47726179524950202020202001"),
74    /* [  1] */ new RandomConstant("17bce35bdf69743c529ed9eb20e0ae99", 
75                                   "95e0e48262b3edfe04479485c755b646"),
76    /* [  2] */ new RandomConstant("f4dd417327db7a9bd194dfbe42d45771", 
77                                   "882a02c315362b60765f100068b33a1c"),
78    /* [  3] */ new RandomConstant("6347af777a7898f6d1a2d6f33505ffe1", 
79                                   "5efc4abfaca23e8ca8edb1f2dfbf6478"),
80    /* [  4] */ new RandomConstant("b6a4239f3b315f84f6ef6d3d288c03c1", 
81                                   "f25bd15439d16af594c1b1bafa6239f0"),
82    /* [  5] */ new RandomConstant("2c82901ad1cb0cd182b631ba6b261781", 
83                                   "89ca67c29c9397d59c612596145db7e0"),
84    /* [  6] */ new RandomConstant("dab03f988288676ee49e66c4d2746f01", 
85                                   "8b6ae036713bd578a8093c8eae5c7fc0"),
86    /* [  7] */ new RandomConstant("602167331d86cf5684fe009a6d09de01", 
87                                   "98a2542fd23d0dbdff3b886cdb1d3f80"),
88    /* [  8] */ new RandomConstant("61ecb5c24d95b058f04c80a23697bc01", 
89                                   "954db923fdb7933e947cd1edcecb7f00"),
90    /* [  9] */ new RandomConstant("4a5c31e0654c28aa60474e83bf3f7801", 
91                                   "00be4a36657c98cd204e8c8af7dafe00"),
92    /* [ 10] */ new RandomConstant("ae4f079d54fbece1478331d3c6bef001", 
93                                   "991965329dccb28d581199ab18c5fc00"),
94    /* [ 11] */ new RandomConstant("101b8cb830c7cb927ff1ed50ae7de001", 
95                                   "e1a8705b63ad5b8cd6c3d268d5cbf800"),
96    /* [ 12] */ new RandomConstant("f54a27fc056b00e7563f3505e0fbc001", 
97                                   "2b657bbfd6ed9d632079e70c3c97f000"),
98    /* [ 13] */ new RandomConstant("df8a6fc1a833d201f98d719dd1f78001",
99                                   "59b60ee4c52fa49e9fe90682bd2fe000"),
100    /* [ 14] */ new RandomConstant("5480a5015f101a4ea7e3f183e3ef0001", 
101                                   "cc099c88030679464fe86aae8a5fc000"),
102    /* [ 15] */ new RandomConstant("a498509e76e5d7925f539c28c7de0001", 
103                                   "06b9abff9f9f33dd30362c0154bf8000"),
104    /* [ 16] */ new RandomConstant("0798a3d8b10dc72e60121cd58fbc0001", 
105                                   "e296707121688d5a0260b293a97f0000"),
106    /* [ 17] */ new RandomConstant("1647d1e78ec02e665fafcbbb1f780001", 
107                                   "189ffc4701ff23cb8f8acf6b52fe0000"),
108    /* [ 18] */ new RandomConstant("a7c982285e72bf8c0c8ddfb63ef00001", 
109                                   "5141110ab208fb9d61fb47e6a5fc0000"),
110    /* [ 19] */ new RandomConstant("3eb78ee8fb8c56dbc5d4e06c7de00001", 
111                                   "3c97caa62540f2948d8d340d4bf80000"),
112    /* [ 20] */ new RandomConstant("72d03b6f4681f2f9fe8e44d8fbc00001", 
113                                   "1b25cb9cfe5a0c963174f91a97f00000"),
114    /* [ 21] */ new RandomConstant("ea85f81e4f502c9bc8ae99b1f7800001", 
115                                   "0c644570b4a487103c5436352fe00000"),
116    /* [ 22] */ new RandomConstant("629c320db08b00c6bfa57363ef000001", 
117                                   "3d0589c28869472bde517c6a5fc00000"),
118    /* [ 23] */ new RandomConstant("c5c4b9ce268d074a386be6c7de000001", 
119                                   "bc95e5ab36477e65534738d4bf800000"),
120    /* [ 24] */ new RandomConstant("f30bbbbed1596187555bcd8fbc000001", 
121                                   "ddb02ff72a031c01011f71a97f000000"),
122    /* [ 25] */ new RandomConstant("4a1000fb26c9eeda3cc79b1f78000001", 
123                                   "2561426086d9acdb6c82e352fe000000"),
124    /* [ 26] */ new RandomConstant("89fb5307f6bf8ce2c1cf363ef0000001", 
125                                   "64a788e3c118ed1c8215c6a5fc000000"),
126    /* [ 27] */ new RandomConstant("830b7b3358a5d67ea49e6c7de0000001", 
127                                   "e65ea321908627cfa86b8d4bf8000000"),
128    /* [ 28] */ new RandomConstant("fd8a51da91a69fe1cd3cd8fbc0000001", 
129                                   "53d27225604d85f9e1d71a97f0000000"),
130    /* [ 29] */ new RandomConstant("901a48b642b90b55aa79b1f780000001", 
131                                   "ca5ec7a3ed1fe55e07ae352fe0000000"),
132    /* [ 30] */ new RandomConstant("118cdefdf32144f394f363ef00000001", 
133                                   "4daebb2e085330651f5c6a5fc0000000"),
134    /* [ 31] */ new RandomConstant("0a88c0a91cff430829e6c7de00000001", 
135                                   "9d6f1a00a8f3f76e7eb8d4bf80000000"),
136    /* [ 32] */ new RandomConstant("433bef4314f16a9453cd8fbc00000001", 
137                                   "158c62f2b31e496dfd71a97f00000000"),
138    /* [ 33] */ new RandomConstant("c294b02995ae6738a79b1f7800000001", 
139                                   "290e84a2eb15fd1ffae352fe00000000"),
140    /* [ 34] */ new RandomConstant("913575e0da8b16b14f363ef000000001", 
141                                   "e3dc1bfbe991a34ff5c6a5fc00000000"),
142    /* [ 35] */ new RandomConstant("2f61b9f871cf4e629e6c7de000000001", 
143                                   "ddf540d020b9eadfeb8d4bf800000000"),
144    /* [ 36] */ new RandomConstant("78d26ccbd68320c53cd8fbc000000001", 
145                                   "8ee4950177ce66bfd71a97f000000000"),
146    /* [ 37] */ new RandomConstant("8b7ebd037898518a79b1f78000000001", 
147                                   "39e0f787c907117fae352fe000000000"),
148    /* [ 38] */ new RandomConstant("0b5507b61f78e314f363ef0000000001", 
149                                   "659d2522f7b732ff5c6a5fc000000000"),
150    /* [ 39] */ new RandomConstant("4f884628f812c629e6c7de0000000001", 
151                                   "9e8722938612a5feb8d4bf8000000000"),
152    /* [ 40] */ new RandomConstant("be896744d4a98c53cd8fbc0000000001", 
153                                   "e941a65d66b64bfd71a97f0000000000"),
154    /* [ 41] */ new RandomConstant("daf63a553b6318a79b1f780000000001", 
155                                   "7b50d19437b097fae352fe0000000000"),
156    /* [ 42] */ new RandomConstant("2d7a23d8bf06314f363ef00000000001", 
157                                   "59d7b68e18712ff5c6a5fc0000000000"),
158    /* [ 43] */ new RandomConstant("392b046a9f0c629e6c7de00000000001", 
159                                   "4087bab2d5225feb8d4bf80000000000"),
160    /* [ 44] */ new RandomConstant("eb30fbb9c218c53cd8fbc00000000001", 
161                                   "b470abc03b44bfd71a97f00000000000"),
162    /* [ 45] */ new RandomConstant("b9cdc30594318a79b1f7800000000001", 
163                                   "366630eaba897fae352fe00000000000"),
164    /* [ 46] */ new RandomConstant("014ab453686314f363ef000000000001", 
165                                   "a2dfc77e8512ff5c6a5fc00000000000"),
166    /* [ 47] */ new RandomConstant("395221c7d0c629e6c7de000000000001", 
167                                   "1e0d25a14a25feb8d4bf800000000000"),
168    /* [ 48] */ new RandomConstant("4d972813a18c53cd8fbc000000000001", 
169                                   "9d50a5d3944bfd71a97f000000000000"),
170    /* [ 49] */ new RandomConstant("06f9e2374318a79b1f78000000000001", 
171                                   "bf7ab5eb2897fae352fe000000000000"),
172    /* [ 50] */ new RandomConstant("bd220cae86314f363ef0000000000001", 
173                                   "925b14e6512ff5c6a5fc000000000000"),
174    /* [ 51] */ new RandomConstant("36fd3a5d0c629e6c7de0000000000001", 
175                                   "724cce0ca25feb8d4bf8000000000000"),
176    /* [ 52] */ new RandomConstant("60def8ba18c53cd8fbc0000000000001", 
177                                   "1af42d1944bfd71a97f0000000000000"),
178    /* [ 53] */ new RandomConstant("8d500174318a79b1f780000000000001", 
179                                   "0f529e32897fae352fe0000000000000"),
180    /* [ 54] */ new RandomConstant("48e842e86314f363ef00000000000001", 
181                                   "844e4c6512ff5c6a5fc0000000000000"),
182    /* [ 55] */ new RandomConstant("4af185d0c629e6c7de00000000000001",
183                                   "9f40d8ca25feb8d4bf80000000000000"),
184    /* [ 56] */ new RandomConstant("7a670ba18c53cd8fbc00000000000001",
185                                   "9912b1944bfd71a97f00000000000000"),
186    /* [ 57] */ new RandomConstant("86de174318a79b1f7800000000000001",
187                                   "9c69632897fae352fe00000000000000"),
188    /* [ 58] */ new RandomConstant("55fc2e86314f363ef000000000000001",
189                                   "e1e2c6512ff5c6a5fc00000000000000"),
190    /* [ 59] */ new RandomConstant("ccf85d0c629e6c7de000000000000001",
191                                   "68058ca25feb8d4bf800000000000000"),
192    /* [ 60] */ new RandomConstant("1df0ba18c53cd8fbc000000000000001",
193                                   "610b1944bfd71a97f000000000000000"),
194    /* [ 61] */ new RandomConstant("4be174318a79b1f78000000000000001",
195                                   "061632897fae352fe000000000000000"),
196    /* [ 62] */ new RandomConstant("d7c2e86314f363ef0000000000000001",
197                                   "1c2c6512ff5c6a5fc000000000000000"),
198    /* [ 63] */ new RandomConstant("af85d0c629e6c7de0000000000000001",
199                                   "7858ca25feb8d4bf8000000000000000"),
200    /* [ 64] */ new RandomConstant("5f0ba18c53cd8fbc0000000000000001",
201                                   "f0b1944bfd71a97f0000000000000000"),
202    /* [ 65] */ new RandomConstant("be174318a79b1f780000000000000001",
203                                   "e1632897fae352fe0000000000000000"),
204    /* [ 66] */ new RandomConstant("7c2e86314f363ef00000000000000001",
205                                   "c2c6512ff5c6a5fc0000000000000000"),
206    /* [ 67] */ new RandomConstant("f85d0c629e6c7de00000000000000001",
207                                   "858ca25feb8d4bf80000000000000000"),
208    /* [ 68] */ new RandomConstant("f0ba18c53cd8fbc00000000000000001",
209                                   "0b1944bfd71a97f00000000000000000"),
210    /* [ 69] */ new RandomConstant("e174318a79b1f7800000000000000001",
211                                   "1632897fae352fe00000000000000000"),
212    /* [ 70] */ new RandomConstant("c2e86314f363ef000000000000000001",
213                                   "2c6512ff5c6a5fc00000000000000000"),
214    /* [ 71] */ new RandomConstant("85d0c629e6c7de000000000000000001",
215                                   "58ca25feb8d4bf800000000000000000"),
216    /* [ 72] */ new RandomConstant("0ba18c53cd8fbc000000000000000001",
217                                   "b1944bfd71a97f000000000000000000"),
218    /* [ 73] */ new RandomConstant("174318a79b1f78000000000000000001",
219                                   "632897fae352fe000000000000000000"),
220    /* [ 74] */ new RandomConstant("2e86314f363ef0000000000000000001",
221                                   "c6512ff5c6a5fc000000000000000000"),
222    /* [ 75] */ new RandomConstant("5d0c629e6c7de0000000000000000001",
223                                   "8ca25feb8d4bf8000000000000000000"),
224    /* [ 76] */ new RandomConstant("ba18c53cd8fbc0000000000000000001",
225                                   "1944bfd71a97f0000000000000000000"),
226    /* [ 77] */ new RandomConstant("74318a79b1f780000000000000000001",
227                                   "32897fae352fe0000000000000000000"),
228    /* [ 78] */ new RandomConstant("e86314f363ef00000000000000000001",
229                                   "6512ff5c6a5fc0000000000000000000"),
230    /* [ 79] */ new RandomConstant("d0c629e6c7de00000000000000000001",
231                                   "ca25feb8d4bf80000000000000000000"),
232    /* [ 80] */ new RandomConstant("a18c53cd8fbc00000000000000000001",
233                                   "944bfd71a97f00000000000000000000"),
234    /* [ 81] */ new RandomConstant("4318a79b1f7800000000000000000001",
235                                   "2897fae352fe00000000000000000000"),
236    /* [ 82] */ new RandomConstant("86314f363ef000000000000000000001",
237                                   "512ff5c6a5fc00000000000000000000"),
238    /* [ 83] */ new RandomConstant("0c629e6c7de000000000000000000001",
239                                   "a25feb8d4bf800000000000000000000"),
240    /* [ 84] */ new RandomConstant("18c53cd8fbc000000000000000000001",
241                                   "44bfd71a97f000000000000000000000"),
242    /* [ 85] */ new RandomConstant("318a79b1f78000000000000000000001",
243                                   "897fae352fe000000000000000000000"),
244    /* [ 86] */ new RandomConstant("6314f363ef0000000000000000000001",
245                                   "12ff5c6a5fc000000000000000000000"),
246    /* [ 87] */ new RandomConstant("c629e6c7de0000000000000000000001",
247                                   "25feb8d4bf8000000000000000000000"),
248    /* [ 88] */ new RandomConstant("8c53cd8fbc0000000000000000000001",
249                                   "4bfd71a97f0000000000000000000000"),
250    /* [ 89] */ new RandomConstant("18a79b1f780000000000000000000001",
251                                   "97fae352fe0000000000000000000000"),
252    /* [ 90] */ new RandomConstant("314f363ef00000000000000000000001",
253                                   "2ff5c6a5fc0000000000000000000000"),
254    /* [ 91] */ new RandomConstant("629e6c7de00000000000000000000001",
255                                   "5feb8d4bf80000000000000000000000"),
256    /* [ 92] */ new RandomConstant("c53cd8fbc00000000000000000000001",
257                                   "bfd71a97f00000000000000000000000"),
258    /* [ 93] */ new RandomConstant("8a79b1f7800000000000000000000001",
259                                   "7fae352fe00000000000000000000000"),
260    /* [ 94] */ new RandomConstant("14f363ef000000000000000000000001",
261                                   "ff5c6a5fc00000000000000000000000"),
262    /* [ 95] */ new RandomConstant("29e6c7de000000000000000000000001",
263                                   "feb8d4bf800000000000000000000000"),
264    /* [ 96] */ new RandomConstant("53cd8fbc000000000000000000000001",
265                                   "fd71a97f000000000000000000000000"),
266    /* [ 97] */ new RandomConstant("a79b1f78000000000000000000000001",
267                                   "fae352fe000000000000000000000000"),
268    /* [ 98] */ new RandomConstant("4f363ef0000000000000000000000001",
269                                   "f5c6a5fc000000000000000000000000"),
270    /* [ 99] */ new RandomConstant("9e6c7de0000000000000000000000001",
271                                   "eb8d4bf8000000000000000000000000"),
272    /* [100] */ new RandomConstant("3cd8fbc0000000000000000000000001",
273                                   "d71a97f0000000000000000000000000"),
274    /* [101] */ new RandomConstant("79b1f780000000000000000000000001",
275                                   "ae352fe0000000000000000000000000"),
276    /* [102] */ new RandomConstant("f363ef00000000000000000000000001",
277                                   "5c6a5fc0000000000000000000000000"),
278    /* [103] */ new RandomConstant("e6c7de00000000000000000000000001",
279                                   "b8d4bf80000000000000000000000000"),
280    /* [104] */ new RandomConstant("cd8fbc00000000000000000000000001",
281                                   "71a97f00000000000000000000000000"),
282    /* [105] */ new RandomConstant("9b1f7800000000000000000000000001",
283                                   "e352fe00000000000000000000000000"),
284    /* [106] */ new RandomConstant("363ef000000000000000000000000001",
285                                   "c6a5fc00000000000000000000000000"),
286    /* [107] */ new RandomConstant("6c7de000000000000000000000000001",
287                                   "8d4bf800000000000000000000000000"),
288    /* [108] */ new RandomConstant("d8fbc000000000000000000000000001",
289                                   "1a97f000000000000000000000000000"),
290    /* [109] */ new RandomConstant("b1f78000000000000000000000000001",
291                                   "352fe000000000000000000000000000"),
292    /* [110] */ new RandomConstant("63ef0000000000000000000000000001",
293                                   "6a5fc000000000000000000000000000"),
294    /* [111] */ new RandomConstant("c7de0000000000000000000000000001",
295                                   "d4bf8000000000000000000000000000"),
296    /* [112] */ new RandomConstant("8fbc0000000000000000000000000001",
297                                   "a97f0000000000000000000000000000"),
298    /* [113] */ new RandomConstant("1f780000000000000000000000000001",
299                                   "52fe0000000000000000000000000000"),
300    /* [114] */ new RandomConstant("3ef00000000000000000000000000001",
301                                   "a5fc0000000000000000000000000000"),
302    /* [115] */ new RandomConstant("7de00000000000000000000000000001",
303                                   "4bf80000000000000000000000000000"),
304    /* [116] */ new RandomConstant("fbc00000000000000000000000000001",
305                                   "97f00000000000000000000000000000"),
306    /* [117] */ new RandomConstant("f7800000000000000000000000000001",
307                                   "2fe00000000000000000000000000000"),
308    /* [118] */ new RandomConstant("ef000000000000000000000000000001",
309                                   "5fc00000000000000000000000000000"),
310    /* [119] */ new RandomConstant("de000000000000000000000000000001",
311                                   "bf800000000000000000000000000000"),
312    /* [120] */ new RandomConstant("bc000000000000000000000000000001",
313                                   "7f000000000000000000000000000000"),
314    /* [121] */ new RandomConstant("78000000000000000000000000000001",
315                                   "fe000000000000000000000000000000"),
316    /* [122] */ new RandomConstant("f0000000000000000000000000000001",
317                                   "fc000000000000000000000000000000"),
318    /* [123] */ new RandomConstant("e0000000000000000000000000000001",
319                                   "f8000000000000000000000000000000"),
320    /* [124] */ new RandomConstant("c0000000000000000000000000000001",
321                                   "f0000000000000000000000000000000"),
322    /* [125] */ new RandomConstant("80000000000000000000000000000001",
323                                   "e0000000000000000000000000000000"),
324    /* [126] */ new RandomConstant("00000000000000000000000000000001",
325                                   "c0000000000000000000000000000000"),
326    /* [127] */ new RandomConstant("00000000000000000000000000000001",
327                                   "80000000000000000000000000000000")};
328
329  /**
330   *  generate the random number that is "advance" steps
331   *  from an initial random number of 0.  This is done by
332   *  starting with 0, and then advancing the by the
333   *  appropriate powers of 2 of the linear congruential
334   *  generator.
335   */
336  public static Unsigned16 skipAhead(Unsigned16 advance) {
337    Unsigned16 result = new Unsigned16();
338    long          bit_map;
339
340    bit_map = advance.getLow8();
341    for (int i = 0; bit_map != 0 && i < 64; i++) {
342      if ((bit_map & (1L << i)) != 0) {
343        /* advance random number by f**(2**i) (x)
344         */
345        result.multiply(genArray[i].a);
346        result.add(genArray[i].c);
347        bit_map &= ~(1L << i);
348      }
349    }
350    bit_map = advance.getHigh8();
351    for (int i = 0; bit_map != 0 && i < 64; i++)
352    {
353      if ((bit_map & (1L << i)) != 0) {
354        /* advance random number by f**(2**(i + 64)) (x)
355         */
356        result.multiply(genArray[i+64].a);
357        result.add(genArray[i+64].c);
358        bit_map &= ~(1L << i);
359      }
360    }
361    return result;
362  }
363
364  /** 
365   * Generate the next 16 byte random number.
366   */
367  public static void nextRand(Unsigned16 rand) {
368    /* advance the random number forward once using the linear congruential
369     * generator, and then return the new random number
370     */
371    rand.multiply(genArray[0].a);
372    rand.add(genArray[0].c);
373  }
374}