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 */ 18 package 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 */ 45 class 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; RandomConstant(String left, String right)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 */ skipAhead(Unsigned16 advance)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 */ nextRand(Unsigned16 rand)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 } 375