+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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*/ 62private static class RandomConstant { 63final Unsigned16 a ; 64final Unsigned16 c ; 65public RandomConstant (String left ,String right ) { 66a =new Unsigned16 (left ); 67c =new Unsigned16 (right ); 68 } 69 } 70 71private 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*/ 336public static Unsigned16 skipAhead (Unsigned16 advance ) { 337Unsigned16 result =new Unsigned16 (); 338long bit_map ; 339 340bit_map =advance .getLow8 (); 341for (int i =0 ;bit_map !=0 &&i <64 ;i ++) { 342if ((bit_map & (1L <<i )) !=0 ) { 343/* advance random number by f**(2**i) (x) 344*/ 345result .multiply (genArray [i ].a ); 346result .add (genArray [i ].c ); 347bit_map &= ~(1L <<i ); 348 } 349 } 350bit_map =advance .getHigh8 (); 351for (int i =0 ;bit_map !=0 &&i <64 ;i ++) 352 { 353if ((bit_map & (1L <<i )) !=0 ) { 354/* advance random number by f**(2**(i + 64)) (x) 355*/ 356result .multiply (genArray [i +64 ].a ); 357result .add (genArray [i +64 ].c ); 358bit_map &= ~(1L <<i ); 359 } 360 } 361return result ; 362 } 363 364/** 365* Generate the next 16 byte random number. 366*/ 367public 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*/ 371rand .multiply (genArray [0 ].a ); 372rand .add (genArray [0 ].c ); 373 } 374}