Kto to jest PRNG?

27

Biorąc pod uwagę sekwencję 625 32-bitowych liczb całkowitych bez znaku (to jest w zakresie [0, 2**32)), wyprowadza, który z następujących generatorów liczb pseudolosowych wygenerował sekwencję:

  1. Generator liniowy kongruencjalny
  2. Xorshift
  3. Mersenne Twister

W szczególności implementacje C tych trzech generatorów używanych do tego wyzwania są następujące:

#include <stdint.h>

/* all code adapted from the sample implementations on the following Wikipedia pages:
     https://en.wikipedia.org/wiki/Linear_congruential_generator
     https://en.wikipedia.org/wiki/Xorshift
     https://en.wikipedia.org/wiki/Mersenne_Twister
*/

uint32_t lcg_seed;
uint32_t xor_x, xor_y, xor_z, xor_w;

void lcg_srand(uint32_t seed) {
    lcg_seed = seed;
}

uint32_t lcg(void) {
    lcg_seed = ((uint64_t) lcg_seed * 1103515245 + 12345) & ( (uint64_t) 0xFFFFFFFF  );
    return (uint32_t) lcg_seed;
}

void xorshift128_srand(uint32_t x, uint32_t y, uint32_t z, uint32_t w) {
    xor_x = x;
    xor_y = y;
    xor_z = z;
    xor_w = w;
}

uint32_t xorshift128(void) {
    uint32_t t = xor_x;
    t ^= t << 11;
    t ^= t >> 8;
    xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
    xor_w ^= xor_w >> 19;
    xor_w ^= t;
    return xor_w;
}

enum {
    // Assumes W = 32 (omitting this)
    N = 624,
    M = 397,
    R = 31,
    A = 0x9908B0DF,

    F = 1812433253,

    U = 11,
    // Assumes D = 0xFFFFFFFF (omitting this)

    S = 7,
    B = 0x9D2C5680,

    T = 15,
    C = 0xEFC60000,

    L = 18,

    MASK_LOWER = (1ull << R) - 1,
    MASK_UPPER = (1ull << R)
};

static uint32_t  mt[N];
static uint16_t  index;

// Re-init with a given seed
void mt_Initialize(const uint32_t seed) {
    uint32_t  i;

    mt[0] = seed;

    for ( i = 1; i < N; i++ ) {
        mt[i] = (F * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i);
    }

    index = N;
}

static void mt_Twist() {
    uint32_t  i, x, xA;

    for ( i = 0; i < N; i++ ) {
        x = (mt[i] & MASK_UPPER) + (mt[(i + 1) % N] & MASK_LOWER);

        xA = x >> 1;

        if ( x & 0x1 )
            xA ^= A;

        mt[i] = mt[(i + M) % N] ^ xA;
    }

    index = 0;
}

// Obtain a 32-bit random number
uint32_t mt_ExtractU32() {
    uint32_t  y;
    int       i = index;

    if ( index >= N ) {
        mt_Twist();
        i = index;
    }

    y = mt[i];
    index = i + 1;

    y ^= (mt[i] >> U);
    y ^= (y << S) & B;
    y ^= (y << T) & C;
    y ^= (y >> L);

    return y;
}

Zasady

  • Dane wejściowe i wyjściowe mogą być w dowolnym jednoznacznym, spójnym formacie. Jeśli nie masz pewności, czy format będzie dozwolony, możesz zapytać.
  • Gwarantujemy, że wszystkie wejścia odpowiadają dokładnie jednemu wyjściu PRNG (nigdy nie będzie przypadku, gdy sekwencja wejściowa nie będzie pasować do żadnego wyjścia PRNG lub więcej niż jednego).

Przypadki testowe

Ze względu na ograniczenia długości postów uwzględniono tylko 3 przypadki testowe. Większa lista przypadków testowych znajduje się tutaj . Pamiętaj, że wartości są podawane w systemie szesnastkowym.

[CEE63876, DE7E2E77, 54EC3AE4, 92DEBB4D, D0756602, EE9D3B13, 04A42150, 0FE8BF49, 2BD7E04E, BB96756F, B9B2027C, B5750705, 9DD5B35A, E23EF98B, D15ACA68, C1C40E81, 35ABAB26, 2DA1A367, 36462514, 3CA211BD, E79753B2, A49B0F03, B3EA7E80, 64630CB9, BC22F8FE, D535985F, 14B902AC, EE9EBB75, A831A70A, 79C55B7B, F7099D98, 98AC99F1, D9CB29D6, 53C43457, 04C6FB44, 43DFE42D, 05A80D62, D86DBEF3, F9DA87B0, 99839629, 017D9DAE, 0B1B574F, A5586EDC, F2966BE5, B709E6BA, A160196B, D16B9CC8, FF46E161, 3BDFB486, 4CE4E147, BE01BD74, 6A2F329D, 99F29312, C7044AE3, 9A373CE0, 73515B99, 94E2CE5E, FA26B23F, 2883470C, 3ED31855, 7809726A, 64DE335B, 79A3C7F8, 5379E4D1, B9444B36, 92C2AA37, 6A496BA4, 84E6FD0D, FC81E4C2, 470DB2D3, 4F839E10, 45935D09, C40D8B0E, B4F6A92F, FDEC8B3C, 1C8BC0C5, D99B4A1A, E1CEA94B, 17951F28, BAECA441, 3C13EDE6, 0CDC8F27, 4CB105D4, ED1E437D, 1E210272, B8F8F6C3, FB02AB40, 63D09A79, 4178D3BE, B3EA3C1F, 58073B6C, 10B76535, BAEA6DCA, 37807B3B, 11E2A258, 93061FB1, EB299C96, 00719017, 130B8C04, EFAC05ED, 385AEC22, F6F516B3, D4B76470, 915013E9, D45FA86E, C5206B0F, 6C06579C, 4C0D05A5, 9BE1DD7A, 7702A92B, 3DEF5188, E0ED5721, DA205746, 0080AD07, 05EBFE34, 3D27445D, 7D7AA1D2, 44F112A3, 9B64C9A0, 7118C959, 08BD091E, FC7835FF, A1DCDFCC, 1B03A215, 4D2C992A, 9324331B, 0FDE2CB8, C1894A91, B9531DF6, DDC8E5F7, 38A55C64, 59E6FECD, C88B2382, 409BEA93, C48DDAD0, F5F1BAC9, DF4BF5CE, A3909CEF, C43DD3FC, 55D23A85, A035A0DA, 5074190B, CA9233E8, D980FA01, 85DCF0A6, 96C93AE7, B94AA694, 0E02353D, 4D577132, D1649E83, AC759800, D261E839, 7D876E7E, 29C89FDF, 309C342C, D06FCEF5, 1727F48A, 35415AFB, AFAE6718, C53B6571, 3998CF56, 47C0ABD7, C0AEDCC4, D54FE7AD, 486A8AE2, 187A2E73, C61F0130, E8B051A9, DDAA732E, 143F3ECF, 072B005C, CA935F65, 94EE943A, 799AF8EB, 2F95C648, 88DF8CE1, 7B21BA06, 1AAE38C7, E264FEF4, 4F67161D, AF0F7092, 60CB9A63, CB4D1660, BAE3F719, 7EB003DE, EDD379BF, 5ADD388C, 5FB3EBD5, 0D347FEA, F74FF2DB, 196B5178, 00547051, 4DD2B0B6, 3750E1B7, 3CC00D24, AF9EC08D, DF512242, 0F07E253, EC82D790, DAC3D889, 1453208E, 372450AF, 6165DCBC, F7087445, 3464B79A, 19EF48CB, CB1208A8, 4F410FC1, C1C6B366, B327A6A7, A8D30754, 2D0DE6FD, 4FFA9FF2, 919E0643, 010344C0, 59D6F5F9, 370EC93E, 5690C39F, A337ECEC, B387F8B5, 2FAA3B4A, CEC7FABB, 612CEBD8, 510C6B31, A3D8C216, 81718797, EA70ED84, 728B896D, 4096E9A2, 50BD0633, B6D15DF0, 39644F69, 141DFDEE, 8837D28F, 2B86691C, E3E97925, 44F00AFA, 74E908AB, E71EFB08, 08DD82A1, 2DA3DCC6, 632D8487, E02CBFB4, 0EAEA7DD, 6970FF52, 9E53E223, C2B02320, DA72E4D9, 1D7BBE9E, CDF87D7F, B844514C, 72A3F595, 8AE126AA, CD21729B, 870B3638, 119B5611, B5830376, D71A9D77, B3597DE4, E3CE424D, AB93E102, A6119A13, 10229450, 6DC9B649, B9E30B4E, DF71C46F, EA24A57C, 55EE6E05, 98E88E5A, EA00388B, B9D49D68, 0DECE581, 5E913626, 09B7D267, 080A2814, 980158BD, C0CA8EB2, 5D652E03, F16BB180, 63EFC3B9, F4CEE3FE, 1A02A75F, 749A65AC, FFBFE275, 3731420A, 1FD45A7B, 771E3098, 183930F1, C8A974D6, C5442357, 2D11BE44, 051EEB2D, EBA00862, 737D9DF3, 4F8E7AB0, DD2C0D29, 2E7A48AE, 70CA264F, 4DD891DC, CDCF52E5, 0EA641BA, F4ACD86B, 654AEFC8, 32A73861, C066BF86, 61BE9047, 4C034074, A8BDF99D, A75F4E12, 4149E9E3, DA4DEFE0, 19859299, CBE0395E, 5CA7413F, DED22A0C, 7993BF55, 58F28D6A, 1058B25B, 097DDAF8, B71DFBD1, EF241636, B4E61937, 9931AEA4, 1435840D, 58135FC2, B97911D3, 382D1110, E8C35409, E6BBB60E, CC38F82F, 333A2E3C, 884427C5, 9081251A, 2C66E84B, F799F228, C7447B41, 8AFC78E6, 0239BE27, 83B008D4, 5C9C8A7D, FA873D72, 587A15C3, 366EDE40, 1A6C5179, FD87BEBE, 13DE4B1F, 29839E6C, BAD78C35, 207D08CA, 04267A3B, 02423558, BC81B6B1, 06CAE796, EAF87F17, E5514F04, 8ACA0CED, D445E722, 147BF5B3, F9165770, EDC78AE9, A37F536E, DDB63A0F, A2E17A9C, 7E04ECA5, 14D1387A, 44A6682B, 6AD9A488, 97FCAE21, C22A6246, 5E215C07, 32A88134, 0B550B5D, 239A5CD2, 4D6DB1A3, 2AE67CA0, 81DC0059, 309D741E, 199FC4FF, B346C2CC, 5A434915, CA28B42A, 7CB5B21B, 11833FB8, 729C6191, B975E8F6, 887354F7, AB089F64, 1E9485CD, CF8F9E82, BCFE4993, 2D624DD0, 4570B1C9, 719D20CE, ED39EBEF, D16676FC, 63C9A185, 9DEE7BDA, 0CE3580B, A52206E8, ED07D101, 35C87BA6, C46D69E7, 8884A994, 489F7C3D, 17F0AC32, 669CBD83, 48CCCB00, 670C9F39, 57F9597E, A3E3AEDF, 06B3972C, AA8EF5F5, 9E4D8F8A, 177E59FB, D358FA18, 9FA5FC71, 7CFD1A56, 8A4E9AD7, 2FEF9FC4, C14CEEAD, 454885E2, 87780D73, DC28F430, 44F6C8A9, A9ED1E2E, 9EBC0DCF, 1F61235C, AA4A4665, 3A30EF3A, 7095B7EB, 788B1948, 8A9DE3E1, 81AEC506, 6015E7C7, 60DC81F4, E433DD1D, 58E22B92, 867F3963, 8D39C960, DD362E19, B2736EDE, 44A208BF, DA621B8C, BA7292D5, F1439AEA, 8DF871DB, CFDB6478, 85D68751, 93387BB6, C98250B7, 659E5024, A0AB478D, BCC89D42, E4614153, 78824A90, 3D91CF89, F1474B8E, F2349FAF, 19697FBC, 7E3EDB45, 03F0929A, 773587CB, A32CDBA8, B0F6E6C1, 0DB53E66, 3812D5A7, 43480A54, E9CA2DFD, F3C6DAF2, 2B8D2543, 614577C0, F390ACF9, CAE3B43E, E9D2D29F, 10EA4FEC, 54A61FB5, 2362D64A, B59BF9BB, 7B227ED8, E3660231, 0A000D16, FB067697, E9ACB084, 2667906D, 4967E4A2, E031E533, E18650F0, 7C79C669, 3883A8EE, 439BA18F, 78178C1C, C85F6025, 218565FA, 443AC7AB, CF1F4E08, 1C4AD9A1, 0DB3E7C6, 2F5C3387, 635F42B4, A11A6EDD, 81F6BA52, 703E8123, 9A07D620, B5541BD9, 7822299E, DD6E0C7F, B8E4344C, FFE19C95, A10341AA, 7FE0F19B, 35464938, F28C6D11, BB2BCE76, AFD30C77, 05B2C0E4, F839C94D, 8A7E5C02, 2361F913, 624D0750, 4AE6AD49, BC7A364E, 4AE9136F, 2003487C, 2D63D505, C547695A, 171D778B, 927A7068, 04D1BC81, 8182C126, 04EA0167, A0BA2B14, 8DDC9FBD, 28C9C9B2, 0B0B4D03, 7898E480, 29B87AB9, DD06CEFE, C56BB65F, 0CE7C8AC, FEDD0975, E27CDD0A, FA3F597B, 4A5EC398, 6981C7F1, 4C93BFD6, 54E01257, AF488144, F7D9F22D, AB640362, F2697CF3, B1EE6DB0, EE108429, 0602F3AE, 1C14F54F, 21C4B4DC, 0E0439E5, 2D8E9CBA, 4B55976B, 6F5642C8, 1EC38F61, 34F9CA86, 53B43F47, 86F0C374, 6FC8C09D, 99980912, 4E6B88E3, AA10A2E0, 53F5C999, 6869A45E, A3C3D03F, 738D0D0C, 50506655, 6C27A86A, 4E2F315B, F283EDF8, 7A7E12D1, 300FE136, 33258837, 8805F1A4, 43000B0D, 6370DAC2, 2DC070D3, F3828410, A72F4B09, E9F5E10E, 2717472F, B9F3D13C, 86F88EC5, A4B3001A, 585B274B, D3CAC528, 9A585241, BFF103E6, 92B2ED27, 4D9B0BD4, 4296D17D, 11B97872, 28D734C3, 47871140, 33440879, D522A9BE, D66E5A1F, 7F6C016C, AEF3B335, CE5BA3CA, C128793B, 51CDC858, D3B94DB1, A3783296, 6F9B6E17, DD831204, 336413ED, F5FCE222, 51DED4B3, B6214A70, B37B01E9, 892AFE6E, 37E8090F, 51289D9C, 70F8D3A5, 810C937A, D1A6272B, 19EFF788, 23C80521, 86406D46] -> LCG
[7D17504D, 9FED269B, 939C3D03, C8FCFA6C, 0FAE4E06, F9816896, 8B872680, A4878206, D92436EE, 2B133084, 9912A040, 011D96D6, F976435D, 4B53DBE7, 474F626D, AA09E774, E12E35C3, 347746E2, 0817160B, EDC0623A, 7DD0D26C, F31ECB62, 43093C44, AD3657AD, 568EB3D5, 53CE27BD, 592FDA9C, 46BB652B, 65886632, 475956F1, 60859FBC, FD8A3CBA, DB156CCF, 56764782, 1A424A8F, B681CA91, C682BB9A, 222CBE9F, 2A329E67, 925F0CF2, 41D22B48, 064DBDAB, B832DAA3, D26069CB, 023890A4, 69F3D5AD, 473AFDF2, 96C5EAEF, 50BEF523, A7171C24, 3752B059, 8E79B6CE, 29C95DCF, 362092EE, 94523C0B, D7DE2789, B49A3F98, 861F7C07, 83A8BAAB, A56C2738, C06FAAF2, BDED09BC, 7B568148, BFC73CFD, 024229CD, D73760D0, 18A4E7BF, 9E021082, 8D1D4ECE, E1408E5D, DEE614D5, 50EE898B, 37E2D666, D23584A1, 3C9B628E, 181D1647, 396DA2C4, 470339C4, A06BACB8, 503439DC, 041BCA9C, 5A881EC2, A77B7747, 567040AD, 8CE52FD5, 96814E85, EA3CD25D, 3E9D929F, 9BA3891E, 07CA0989, 0B689D17, D9B3FF8F, 5EDF76DE, 090EBACD, 46C11EDE, 00C8DE0E, A504314F, D9A02FF0, 97D9EDF4, D1A769AF, 55ADB49D, 8DAACE77, D544247B, 3F44C56D, 07759744, DC7738AB, 28E4B8A2, 31927F7E, 9AF601BF, FF21C02A, F20D56C4, 50C6AE74, 7A17A62A, 8BC619D2, 13E5C518, 76357C1E, B1D4A204, 0A673565, 3797FC34, EA9FA354, FE4FF881, CDB03630, 454E05EE, 52DC8B10, D3D6FA3A, 9F9B57C6, AACF50AE, 1CFDCAEC, 789EE463, 3DFEA9D1, ED64C4E0, 1F3CD90A, 900E9B72, 58761883, 93FE94A9, 6AF3FB55, 8EC22872, 66988B29, 01A4008F, F4787ABD, 6B665DF8, C905527E, E88493A9, DF1EB196, 86CEBE10, 65BB9A15, A96E54D0, 83D6D26A, 701BC23E, C9C9951A, 12DA9027, 27AA5594, 890E696D, 0CEA5C13, CA77AE01, BF04442E, 45BB17A2, 1BEFD1C2, 6C9F7318, F1276F91, 6CBC7010, 09B8DD84, 9E286818, 54B9C7AB, DB0A01DC, 1491B3C4, C92471E6, 533A73F6, D8B59CAC, 41231BED, AB62F96E, 2B478A37, 5F63230F, 06C6A77D, BAD38742, ADD2B41D, EBEF81F3, D8212EBC, FEEE4B6D, C6A47AF1, 51D39BCF, 80560B87, 0C6F8DC3, E9F90D4D, 2439FE5E, 1403C36D, 647255BB, 45C0AF1D, AEE062F5, A4F2C4EF, 52DB8247, 12237746, BF79483D, 8D9E3681, 03D954CF, 0A498AB5, 7F041361, 0352083E, CAE45BB7, 8CBE7C7C, D37EE991, 40FE1838, A82FCA73, D70D1E96, F31B5787, 4394AE04, 953E8857, 2A78CDC8, 03F6006F, E5F46A9B, 84E93A42, 6813B19A, DB55318F, 9DB338CC, 50453A12, A52FCEE1, D7844A82, D3F57DE6, AA195820, 719AD344, 84BF57AF, FCDD1093, 9C658F70, 3BC26F4B, 45BE45B3, 51F39C1F, E15D875E, C9CD1409, 7EE9435E, B3373BF8, BE5D3DB7, 1F911B29, 2B565836, 21B44E5F, 76537F5B, E18C6AEB, 78820904, FBC776FD, 16836779, 94DA8C70, FC787DC6, 3CC88C2A, 317D9C65, 71842F36, 4E2DFA8D, 36FC86BE, EBBFAAB0, BB12D56E, 9ACAA913, 48D10582, 5E2DCC02, 73B9DB0C, BCF46659, 7CC99950, 4CB40717, F168D436, EEB1A2EC, DE82A573, 32E28D0B, 859C2605, E6595298, 2D3BDA1D, 0B978064, 6F5F231D, 43BE71FC, B0A6A0A4, 07858274, 91540E52, 21D5BC15, A4F39B0B, 8F4E3BC3, BE5992E6, 32E0A42C, 0AF34AB8, F49DF806, 86218AD1, B1D79FFD, 21E1A5F5, 3AA73407, B05A4680, BD7F0F01, 919DDB56, 9299C26E, F095F8FB, B5D7E6EF, CAEFDC68, 9639FDE9, C9349DF5, C3DEFAA2, 7766722D, 2EE91F9D, 435FF480, 77601DA3, 33D3FE78, 55A01A68, E9E71FA8, 9E1D8A32, 329187B7, 67B7A8D7, B67CE1D6, C442A131, 7A502A31, A07BC4BC, F158F334, 20C28F07, DB38288C, A5184973, 93EFCFB7, A761D07A, BD07F052, DA336550, 374C9BD6, 9E077F45, 1C0089B7, 5D587682, 0E99C4D4, ABC16F15, B39406EB, 2DE69A7D, ED994471, 4D802710, 5E30D315, 471C9FDC, 6081E182, 2C75F225, F40524C5, 5744A7E6, 38A6D17D, BBC1E896, 663FD027, 14363091, 1A152653, AE24F8DF, 3602BBD4, 9315B73D, 20813CB2, A9EADA7D, 8A15088F, B487EAAF, 9DCA3421, 620C2CD7, 407F0169, CB26495B, 07810722, 04E8F991, BC24C42C, 45B12E62, 4A0689E1, 0961D541, 93FE75E5, 5FF09BC6, 21C75858, 260B4AFC, 463A4285, 9DCFCF2F, 86D14156, FAF1A7DA, 6E4BFC6B, 8D1EF03A, 81C9CB3E, F67163AA, C7E871AB, BD0DD64C, 72526AE8, 0F433B3B, 8BA27651, 58CE6EDF, B92A4A04, AFA624F9, 372EDFA2, 1CBDF70E, F72CE4F7, 69339707, 28A1864C, DB5701D1, 4BCC4D10, BEB260C1, 9A0502BD, F93FC1A5, D0B2B75F, FD2B71E0, 4F899412, 48BC46AF, 0DF108A8, ABF3DC87, A8D9E4EF, 02FA4665, 87CBBADA, B2E95940, D5702D6E, 056990CB, DFAEE7D6, 2775863A, 733AC4E7, 3A9CED83, 92A42D51, 196B2D69, BCD3CF5F, 61FEDDB3, D283BA78, 92C3C524, B0484914, 27CC09EB, E8532710, 643535DB, 96C7D0A0, D10310C2, A019C655, 6D4FA460, C5A53BB9, 0CE9A6CF, 62ACE269, 72D026F8, 9E44A3E8, DFDAB131, DA60BF09, 2974A55B, 9294187E, 98CD6024, 478A1CC3, CB583714, F93D91E9, 0A0202AA, 1D796B2D, 17931F01, 023476C3, 1839337D, CECF1354, 412B769B, E0089213, 317BF7B4, 8798177C, 9D1D36BA, 3921B700, D70921C7, 906DEFAD, E4B1B3FC, D01C81DD, 4E858500, B16A1BFA, D82D7078, EC0B10C9, 8EC425CD, 6F904A24, DC8D591E, 68B4971E, C7F13D88, 2ADD8E38, 9C2E67D4, 50EE1F28, 1EBD75C0, D8D79461, 37285868, 171F16FA, E2F972AC, 86E9860E, F37765A3, 1C3015F1, 357568C9, FF66419F, B77479AD, 2B776D2F, B5DA7BA8, 787DBE35, 6CD01986, FC5E1F26, 9A3F3C3E, 0F26B55A, E3D68111, EF7D1562, 8CC01A7F, B676E2D8, E1FF230E, E62EEC56, 6AB1010E, 6BD04EA2, 732FF785, E2F2E9EA, 00A93DCB, E9E5C622, E57A9744, 90B28FB8, D9BCBF00, 1EAFA6C3, 2F5ED2E5, 2B9557F9, 17EDA934, 74178CB4, AD07B129, 2CAC11EF, 5672B947, 9EC8ED11, 0ED68918, 42B9C244, 81C2F3D5, 58BB2699, E29FFADF, 6EB8AF2A, F872A573, 797CDB0A, 64289FF8, CF42ADA8, A276D00E, 3D4DEBC1, 1DBA64CF, C74FA53D, D3ADEB7A, 81EC012D, 4FBE91C3, F562B344, 492860A9, A82CE5C8, 13A74987, F3BF2024, F9983BD2, 3655838C, 1F971FB0, 1523A266, 2D5D4DBB, B78EE27F, 104301A1, 187BA15D, DF8C077C, 1FD19BE8, 1797DFBA, D223E55C, 6D2BAF83, FEB67715, 57750D76, 9AB10BC1, AAD6F8A3, E7953C33, 1874830A, 0A896CC6, 17879ED4, 59BD4CB3, E56DF85D, A4C3576A, 8F990C18, 3CF2118C, B6D7A95F, 0811C0E8, 4FAFF43E, E37DF236, E8EB2257, 6E7BA922, 5E45AED7, 52A50B6B, E3ED62F2, 506CF514, 232CDAD8, 59A87385, D1DA70B0, E629FBCA, A39607CD, B9B87C61, BBE5C416, 12BB8F0B, 01004AFE, 7B2165CB, EE71DBCD, 207CD2DF, 23283B94, 53570D07, 33981B13, F5B4DD95, 9722AC2C, 7CF6B4FA, 8F4578F4, DC4E44FC, 5E8FD095, 9717EEDA, 3331A614, 9DF66D2A, BDDD0D79, 95944526, 2B2B5086, 059AF7F4, 507984FB, 67F346A7, 162D85BF, C4DAF5D9, 5818EFE5, A5235C3F, DF593559, CC3E6756, 53C6DEF3, ECBBB210, FA5EA123, C5656DE9, A03102F0, 912B0FD4, 9E73F36B, 7097CF69, 58996509, 91059461, 90ECC581, 5ECEBC72, CDEC2B8F, 70F708CF, 86C10B9D, ADC71A1B, 01DBEC7F, C9A22DFB, 47B14AB1, D233979E, 0C5521B3, D4401837, 196924CC, 57A8CF18, F25524E7, 26001B3A, 761F1472, 67DEC5A6, 3CF7A7A6, 1A08B2C9, 943A897E, 05589DAA, 8413C030, DBD2B481, 9BE3A7FC, 5A97CCE7, 409F95C5, 0EA757EB, 88FDCD84] -> Xorshift
[4BB6DADF, 8EEF8EA3, 06E8FD49, 88A2AF49, E3269CD4, ECA4F09A, 3ADC8EFB, AA4DD059, AC3B1AAE, DA22C244, B67C2EC6, DFD9C12F, B4A6DBAF, 354C372C, 2C6CA407, 0AC93693, 725C7716, B439DF25, 7C04626F, 67824F17, 21EE364D, 77D8D72F, 4BF90371, 7BC3C716, 472A4204, B842AEFE, 38270462, 3B17B189, 22760085, 2A801D85, 8DE334B5, A72580F7, F187AA9B, 2E04DC0C, 8A701C0D, 471B61E6, 98F859D9, 9EBC2F45, 02544E96, C2785B15, 20623FAB, 8001F9B4, 0E438545, CFA2A2A5, 9DA35720, BAA84901, 908758C8, FCF5557F, F905B3B4, BE7DEBCD, FED08B1E, 7E9472CB, AC3A29C1, 5BED194F, B6932F25, 1C95E32D, 67E94371, D7CCB4CE, DF296D87, 6AAEF0F6, 8CFFF867, 093F9F79, FB280F6C, DE7735A8, 684C17B5, A0DA757E, 374EC162, 1764A62D, 82C244F6, 9E4583C7, 56F02388, 0018E400, 815A0F1E, FD80C932, 30EDD175, D37AF8D8, 7C8E4633, 7D8E4E5D, 660A7F79, 4C2C08BD, B6656A5B, CCFD6607, B0AA17FA, 060EE305, DEE9752F, B38BE439, F04EB964, D4E6C330, DCD4F7AB, DF7D83BF, 309047C6, 51FFC819, 9E59C7D6, 46821973, 01B47792, F800809B, 6050BB64, C13CB495, A305F788, 7AD27279, B7F9151F, 9F154C4F, D3F688F1, FF830866, A9C059A3, FFBF160E, EA8D827A, 1F1DA6E8, FDC52EFC, 5325CE11, 765B86EB, A852DC5C, 74ADAF62, 45BFACA5, 8E1FF6C3, 83ADCF0A, 91D6626E, 316008CC, 0DAD4110, C28EA37D, 5F077B03, AF70C5E3, 13A7C50C, 0A737B9D, E236FCBB, DDADB0C5, F4CAA3C8, 73679470, 87AE2E8E, EAA6ADA4, F30CCA79, 2B2FED65, 9B55A25D, 7317A6DB, D505929C, 0F90C693, 5CED397C, C1CB0AB9, C81895F1, 828D68BF, C2D0D855, 70585D86, 1ACD41B1, D8227B76, 1CB6DD69, B71EF185, 3EB11656, 6674378A, BA543682, 895A464E, B9E6CC48, FDAB6657, AB815F3B, A717AF55, 5826ABAB, 7CAF7DA1, 33EB26C0, 9367A48F, 32334888, 6BD35F76, 21F56A13, B7E72B51, 2B110FC2, A7A6ED6F, 1B2E72D1, 855EC1F3, A320F92E, 05609603, 5AA26082, 937BB417, F7A082EF, 370690A8, 074B4C00, EFB2EF14, A449B9F8, 9AA7E8A8, 3AEC4108, E5DDDB2A, C2CC4D30, 8589EB3D, 030ED83E, 4230E9B3, 619B03C0, E2B2BB64, 839A7C40, 2527B162, D03987D6, F8D66424, B950968F, F41E4D21, 9BAEEC89, DB8C65CD, D19F0371, 42507672, F133D6DC, 8FF10301, 6267E094, 339A1D5D, 3DD9DDE3, 139AA839, 440F8A94, 5E10CEAF, 60A1BA78, 02576968, 9AE7D81E, B9BF647E, F1698EC1, 5EC4890B, 88CF1A87, 9F3442AD, 4ED7DB9A, 08BD20C4, DA4B2F8E, 7EE018A9, 41968817, 519BE32C, 26CC3EFD, 1C3CBCBB, 551FC090, D06676D9, 02BF4E3F, 5B331917, AA121020, 840B84DD, 1C04DB26, 42DC049A, 58E92781, 95DA8984, CEDFF185, 149A43E5, 9B4CAAE7, 9E61CFFC, C33F9485, 2ABFE975, 75F8E915, 167D7A60, 1086ABF9, FE0B87DC, 095EFA20, 79FC720C, 99DB743E, 8F4B2F19, 00A9188A, B5DE7C2D, DAF3734B, CCAD1F47, 0C9DB549, 0158D55C, BCD5F151, 72A210D9, ABB80C09, 99934B39, F92DF281, A35193BD, C3CB4E8B, 322DBEE4, 26E2E30D, 36F25EDD, F1C8C5DC, 44B5C836, 878075ED, 1140849C, DEBA2848, 6B8D4AD7, 0209883A, AEFFDC8B, F7862944, F2CAE4AB, 77A1EB21, C77D6350, 4749AA23, 1ECDFD3C, 55D6943C, FC9B102A, 80363E80, C28E5369, 7E4BDC16, 8DDD321E, 46E4B844, 71169596, 6EC788CA, 508E25D4, A3249379, C5493848, 67ECFFDB, F6B03518, D4FE2A7D, D6C8D739, 7A93EC17, 84E2A797, 08CB6F22, D09D5BFF, 7FF783FD, 749A4AA7, 9EE69739, 01BB87ED, CDB15087, 32FE625F, 3C8E72C6, 2386A26E, 0F243847, F9E50890, D10F1EC5, 6E1C032D, CE27B59B, 84F2447B, 62AFD23B, 2361B77C, 1532E2F5, BC65F691, D8106771, BC9F8553, 94B67790, CE7F4B32, E36DAA85, D42336C1, 414ABF42, F5D5E7FA, B17620A4, D42A5D6C, E1118425, 17C4B3F2, EBDCB06E, 1F8F7F65, 0AD89423, 32848E5D, 0A5028D0, 463B71B1, E896017F, C1DA750C, DB89FC54, AF665A17, 11F5A446, 45F2DD58, 9C66340A, F4DB1D19, 87AFFD89, 75CA495D, DE608110, 78EC9F5C, 7840FE7C, 6F4DA231, 1CF2E830, CD521794, CE4F5EBA, 79B79437, 5A91D18E, 95F1D139, D9CA1102, E3822EB3, F7C52D20, F917AEEE, 5EDCD7BF, 4BD3725C, 94EE3441, 713CF5DF, 937E1AA9, 08926562, 084E8DD4, 41100547, 1C706FF6, 2ED60298, 0D2E30BA, 82FECB1F, 831BCCE8, 0CB829DB, 0C522998, E0AD92F6, F8969EA4, 386650CD, CA41F763, 7BB34065, D79B9F81, 967FBB17, 7C2F61B2, 7B4E9B33, 8359EDDA, 3201D25E, 5F41BAA6, D94A1FD8, 6E29F112, EDB7885C, C4F4380D, DAD428C7, 40609A88, 66DF9A6C, D61B84E4, C4C77436, D6F4B201, 1C0AD2D4, 3A69D216, 1DD70F43, C887E79C, 8579D94E, F2D069EA, 17B4926F, 55BE153C, A783F442, C03D53D2, 5ED56627, C114DB61, 9B0BFD2C, 825DDE34, 97523F35, EE476E00, EB2ED50C, 567BB078, 9B70520D, DC96668B, FCFD7253, 0197E3F8, 7785825E, 0B00322C, B510F809, 51FB92EE, B6F7D331, 2DE0AC32, 00B41A7B, A432B1FE, 94ED9578, 4B56F086, F8BEADE1, 8C899DF2, EAB17808, 240BF736, 7CBA75E0, E06E352C, 3BBD94E5, 427CB86A, 31CB345E, C1226EE3, F9F4697B, 8820CBB6, C3F9BB4C, 509D403F, 03990E8E, 6C5CCD8B, 24F235C0, C5FC6E59, 05E627C9, 4B0C0C96, 45A35E8E, BBF14335, 89B957A1, 3E272204, EC501927, 00ADCBC3, 13DC9199, A682B338, BE42D97C, F97E0F28, 8C1A6128, 76ED6951, D7D8B74F, 80A6C9D2, 87111413, 48268EB5, 69DDA6F7, 8900B2E1, DBF809E0, D50D7B42, 9716581E, A7AE9B6E, 52366624, 85BAF9A3, DE28F70A, 890E37EC, 7F82541D, 9BA2C144, 8766E737, EA8B0E73, 6BC46E1A, 04A2D3E8, F01716BB, 3D0F7338, 93282BAA, 3A9E51C0, 7B26AFBD, FA2B6A90, 36DD5832, 18161A71, FDE783A2, FF84185B, C251868E, 957CA33D, 6D2BD402, F7E61B15, BAAD0068, 8413463A, 63F0F132, 55FBBC6A, 58E3298D, 845AA664, 02D242A7, A456CEED, 2C198D04, 89A25422, 3A4CABFB, 9D24D792, DFBB850F, 76E30332, 58B59723, 1B1A6913, 9FB961E8, B363CA07, 9CC01B66, 00E9E1DF, 9AF48078, F67167D2, 5D8EBE54, F0819D2D, A003D04B, BD20E32A, 7647BD73, DE509593, E381BF67, BB5D56E0, 675636A1, 983C7C47, C7D92CF8, 335F0477, A6EE6787, F2A67D0E, 29D7F83A, 3DA85C1F, 8E31E016, 5FBEB7EA, 01F017A9, 021B93ED, 8E2AE731, 3391B82D, 6AFEC318, C1E9610D, B50DE358, 46E16C1F, D7A03E8A, 74E52044, 4797BCBC, 49FC24BC, 119F71CB, 51ADB9AC, 1F7A8641, 373911A6, 79424584, 2D69A297, 32859E0B, FF812B02, 2060307E, 6AD9173E, AFCB84DA, 4F5B70D0, 34A63D93, 6DBD6388, BBD76CFA, 94EE5483, 20214C3F, E45B9B77, 8B3192D9, 109D8CE6, 8EBA320B, 53FA8CE2, 56A4A45A, 61AB8FDB, 3ABFD0EB, F92E5F91, 3CBA25FE, C2E19318, 2E5DC1D6, 751C25DB, 572BBA47, DF53AB19, 407F623F, EB9E4EE6, C98E9BFD, DA77A48F, 79D4B4D2, E4320563, 2C1C4BA4, CDCCD4A9, 5B74662F, 3B74B8C1, B1792883, 88D53BDA, FDFAB951, D2D3F844, 199D47E1, 7500E432, B0C714BD, EC5CCDCB, EC949808, 9B39D67F, 15D138B8, 17FE54A4, AD28C768, FE473BF7, AE29CB10, C987A478, EE50D094, 10ED5447, E2BF7CCF, BDD93708, D57E6C1B, 01079D4B, 6C6C547F, 363A37F3, 6D4D828A, EE1622DE, AF1D8240, B068E4C1, 9C5901F8, 17822119, 3C7837B0, DEFFD993, 28FA9C3A, EAADDC4E, 05705400, 0046CB17, E843346D, 2F33C418, AF1A47BD, E4C12B9E, BC3F9B15, 01E90C74, DE0C8A00, 5D52587A] -> MT
Mego
źródło
5
Świetne pytanie!

Odpowiedzi:

16

Galaretka , 23 bajty

^Ḋṫ4^^æ«11$æ»31ż&2\ḂS<4

Pobiera tablicę liczb całkowitych; zwraca [0, 1] dla LCG , [1, 0] dla Xorshift i [0, 0] dla MT .

Wypróbuj online! (Łącze bezpośrednie może być zbyt długie w przypadku niektórych przeglądarek).

tło

Najbardziej losową rzeczą w LCG jest to, że jest uważana za PRNG. Na początek, dolne k bitów stanu nie są dotknięte przez wyższe 32 - k bitów, co czyni go wyjątkowo złym wyborem dla większości zastosowań. W szczególności na LSB stanu zaktualizowanego wpływa tylko LSB poprzedniego, a ponieważ zarówno 1103515245, jak i 12345 są nieparzyste, wygenerowane liczby będą miały wzór parzysty-nieparzysty-parzysty-nieparzysty.

Wady Xorshift są bardziej subtelne, ale generowane bity nadal są zgodne z prostymi równaniami liniowymi. Biorąc pod uwagę pięć kolejnych generowanych słów w k , w k + 1 , w k + 2 , w k + 3 , w k + 4 , (równanie nieliniowe)
w k + 4 = w k + 3 ⊕ w k + 3 > > 19 ⊕ w k ⊕ w k ≪ 11 ⊕ (w k ⊕ w k ≪ 11) ≫ 8 jest z definicji. Jeśli policzymy bity słów ( 0 oznacza najniższą, 31 najwyższą), możemy zauważyć, że równanie (liniowe) w k, 20⊕ W k, 31 ⊕w k + 3,31 ⊕ w k + 4,31 = 0 trzyma. Aby to sprawdzić, wystarczy zauważyć, że słowa, które zostały przesunięte w prawo nie może wpłynąć w k + 4,31 , najbardziej znaczący bit wag k +4 .

To pozostawia Mersenne Twister. Chociaż istnieją lepsze (szybsze, mniej stronnicze lub oba) PRNG, identyfikacja danych generowanych przez MT19937 jest o wiele bardziej skomplikowana niż w przypadku LCG i Xorshift. Na szczęście nie musimy. Jeśli dane nie pasują do żadnego z dwóch poprzednich wzorców, zostały wygenerowane przez Mersenne Twister.

Jak to działa

^Ḋṫ4^^æ«11$æ»31ż&2\ḂS<4  Main link. Argument: A (array of integers)

 Ḋ                       Dequeue; drop the first integer.
^                        XOR the k-th element of A with the k-th element of the
                         previous result, effectively computing the XOR of all
                         neighboring integers in A.
  ṫ4                     Tail; drop the first three elements of the result.
    ^                    XOR the remaining integers with the corr. integers in A.
      æ«11$              Yield the integers in A, shifted 11 times to the left.
     ^                   XOR the results to both sides.
           æ»31          Shift all results 31 times to the right.
                &2\      Yield A, pairwise reduced by bitwise AND.
               ż         Zip the results to both sides.
                   Ḃ     Bit; compute their parities.
                    S    Sum; add the parities of the results left and right to ż.
                     <4  Compare the sums with 4.
                         This is necessary since A and the various modifications
                         with dropped elements have different lengths, which
                         introduces a few garbage values. 
Dennis
źródło
^Ḋṫ4^^Dlaczego widzę tu zbyt wiele powtórzeń? Czuję coś, ale nie jestem pewien, czy istnieje krótsza droga niż XOR [...] XOR XOR.
Erik the Outgolfer
Z ciekawości, jak wyglądałoby rozwiązanie, gdybyś musiał zidentyfikować sekwencje MT19337 (być może, gdyby dane wejściowe nie były wymagane do wygenerowania z jednego z trzech PRNG)?
Mego
1
@Mego Dużo bardziej skomplikowane. Być może będę musiał zaimplementować MT19937.
Dennis,
Byłbym zainteresowany takim rozwiązaniem, jeśli jesteś zainteresowany jego napisaniem. Kiedy początkowo pisałem wyzwanie, rozważałem, czy dane wejściowe prawdopodobnie nie pasują do żadnego z trzech PRNG (co wymagałoby walidacji względem wszystkich trzech, a nie tylko dwóch). Zdecydowałem jednak nie uwzględniać tej możliwości, ponieważ obawiałem się, że utrudni to wyzwanie.
Mego