Party Tricks

k-dimensional Equidistribution

A common use case for a random number generator is to provide points in a k-dimensional space, for some k. Any good RNG ought to be well distributed across k dimensions (i.e., there should be no pattern to the k-tuples we see), but some users would prefer a much stronger property: that over the full period of the generator, every possible k-tuple will occur, and they will all occur the same number of times. This property is known as k-dimensional equidistribution. Let's look at why this might be a desirable property.

There is a saying that if you had an infinite number of monkeys typing on an infinite number of typewriters, they would produce all the great works of literature (and an inconceivable amount of dreck, too). We can cast that scenario into the world of random number generation. Suppose we have a generator that outputs 32-bit values (i.e., four bytes), and we grab its output in chunks of 16384 values at once. Each chunk will thus be 64 KB in size. If we demand that the generator be 16384-dimensionally equidistributed, we can know that all possible 64 KB sequences of data must show up eventually over the full period of the generator, which must be at least 2^16384×32 = 2⁵²⁴²⁸⁸. Within that immensely huge collection of outputs lies every valid 64 KB zip file, some of which will contain great literature such as Hamlet. Thus, to make the saying more accurate, you don't need an infinite number of monkeys (k-tuples) to produce the works of Shakespeare—2⁵²⁴²⁸⁸ is ample.

An argument for k-dimensional equidistribution goes like this: Suppose you bought a lottery ticket every week—how would you feel if you discovered that the clerk at the store was handing you a fake ticket and pocketing the money because, at 259 million to one, you were never going to win anyway. You might, rightly, feel cheated. Thus as unlikely as any particular k-tuple might be, we ought to have a real chance, however remote, of producing it.

An argument against providing k-dimensional equidistribution (for large k) is that infinitesimal probabilities aren't worth worrying about. You probably aren't going to win the lottery, and your monkeys won't write Shakespeare.

But what if rather than blindly search for Shakespeare, we manufacture a generator that is just on the cusp of producing it. With the PCG family, that's possible!

64-Dimensional Party Tricks

If a 32-bit generator is 64-dimensionally equidistributed, it will produce every possible 64-tuple of 32-bit integers. We can, in fact, consider it to be a uniformly distributed 2048-bit generator—every possible string of 2048 bits (or 256 bytes) will appear somewhere in its output.

That means that the generator will eventually produce the all-zeros 64-tuple, the (1,2,3,4,5,…,64) tuple, but also (if we see these tuples as 256-byte strings) every tweet that can ever be written, numerous complex and interesting programs in the binary lambda calculus, and it will even generate a plethora of tiny-but-useful Linux utilities and some pretty cool graphical demo programs.

Unfortunately, between every useful/recognizable artifact, there will be a huge amount of completely random-looking junk. At a very rough (but very generous!) guess, we would have to wade through an impossibly huge 2¹⁰²⁴ tuples before we would come to anything interesting, and if we were looking for a particular 64-tuple, we'd need to skip about 2²⁰⁴⁷ tuples before we'd chance upon one we were looking for.

But instead of searching for the interesting stuff, it's possible to contrive a generator that's just about to produce something interesting. And the PCG family provides a mechanism that makes it easy to do just that.

For example, the pcg32_k64 generator with the internal state

6364136223846793005 5046067853215729949 13800261714138603451 399896088 3486423007 3246597219 4150796805 1457473286 103149001 1454810315 2369898655 180913161 3639874284 2985789973 2683455688 84209159 3378778619 788411401 567529281 1244825732 2177833963 195255923 2894214500 1568355479 1559627362 1710915263 3512047102 1209749930 1884366766 2037204943 4266728772 908096551 39669049 2000946068 1183800969 1518120538 1792588107 3627922345 359880652 209474067 1303409834 4227229788 3505170901 1070462315 3186746228 1072443235 3177247533 4173538449 71485472 2988597779 738834096 2137461319 430253936 3705249687 572532478 770765285 3697245156 4067811693 3460610732 1725644907 2582242074 2986303303 2826139613 854797503 1477918637 769755464 2736158824

produces this output:

00000000  3c 6e b1 bb fa c2 33 1d  da df cb 2b bb 07 a0 6f  |<n....3....+...o|
00000010  31 76 0f c6 a0 ea 78 32  84 c6 86 1b cf d3 68 76  |1v....x2......hv|
00000020  79 e3 f9 11 65 a9 9e 37  be 88 e4 82 c9 e4 5f 0d  |y...e..7......_.|
00000030  1f 9e 36 9b 27 3e 2a 9f  78 ae 21 94 ec da c0 38  |..6.'>*.x.!....8|
00000040  ab c3 91 3f af 30 2b fb  4e 50 4f 7b ac 00 be 91  |...?.0+.NPO{....|
00000050  c3 d6 b2 28 e6 5c 12 14  98 8b 6d a5 e2 c0 a7 43  |...(.\....m....C|
00000060  d3 f3 4a f1 02 15 fd e7  71 19 68 97 07 47 ff 49  |..J.....q.h..G.I|
00000070  6a 29 3d 15 a7 80 df d8  33 bf f4 d8 00 28 39 73  |j)=.....3....(9s|
00000080  0e 84 b2 4f 24 ba ad 8d  00 3e 20 d7 45 81 6c 2c  |...O$....> .E.l,|
00000090  0c 2d d0 be 73 fb b9 c5  4f cc 73 57 73 9e 61 13  |.-..s...O.sWs.a.|
000000a0  10 44 2f 75 17 ca 98 0a  79 02 b6 d5 eb c2 8b d3  |.D/u....y.......|
000000b0  72 fa b4 ea 2a 49 64 95  de 9c d6 ae 20 9d c0 7c  |r...*Id..... ..||
000000c0  4d 8e d8 ac 24 3c 6d fb  42 ec 5a 41 4f 82 18 5e  |M...$<m.B.ZAO..^|
000000d0  90 3f ec 81 8a b9 d6 be  70 b1 91 33 61 49 ba 7a  |.?......p..3aI.z|
000000e0  86 52 32 0b 24 66 1a 77  b1 d8 14 31 80 00 15 3f  |.R2.$f.w...1...?|
000000f0  f0 27 9a 99 67 2e 73 f3  8b 28 49 9f 9d 5c 63 78  |.'..g.s..(I..\cx|

00000100  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000110  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000120  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000130  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000140  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000150  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000160  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000170  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000180  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000190  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001b0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001c0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001d0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001e0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

00000200  5b ca ba 47 b6 d4 92 c3  ba f1 34 76 b2 11 3c 6f  |[..G......4v..<o|
00000210  50 21 5e 38 f1 9d 5c 57  0a 64 3c 1e e1 24 91 3c  |P!^8..\W.d<..$.<|
00000220  ae bb cd ec d7 15 81 f6  c0 aa 5a 4f db af b6 a3  |..........ZO....|
00000230  68 47 d4 31 e9 3e 88 e3  f7 84 ca 85 2a a4 d2 5d  |hG.1.>......*..]|
00000240  93 fb 40 f2 aa a8 bb c4  a0 df 45 b1 8b 08 e5 ed  |..@.......E.....|
00000250  9c 08 6b a0 b5 ef c5 fc  3a 58 31 86 59 51 a2 1c  |..k.....:X1.YQ..|
00000260  77 7b 38 c3 94 08 9c 56  19 7d 8e 13 23 9f c5 fd  |w{8....V.}..#...|
00000270  d4 42 3b 78 8c 5e f4 b9  f5 62 c3 12 ed 05 bc 7a  |.B;x.^...b.....z|
00000280  b8 ad 55 87 46 99 2a d0  4e c7 b5 da 64 09 5d a6  |..U.F.*.N...d.].|
00000290  fa c8 e8 c4 64 01 7c 3e  2b b7 23 a6 1d ed 75 4f  |....d.|>+.#...uO|
000002a0  e6 13 82 5a fe a4 d8 4e  80 df bc 52 1a 06 31 52  |...Z...N...R..1R|
000002b0  14 3b b1 09 45 23 be 2a  0d ee 8a 48 76 37 97 12  |.;..E#.*...Hv7..|
000002c0  87 61 aa 90 9b fa 8f 10  56 fa 00 b0 7e 51 25 ef  |.a......V...~Q%.|
000002d0  25 b5 24 30 26 b2 77 c7  b7 25 11 71 4b 0c 0e 66  |%.$0&.w..%.qK..f|
000002e0  37 86 9d e3 fb 3a 1f a3  ff a4 b8 88 77 1c 9f 0f  |7....:......w...|
000002f0  90 32 74 e5 4b 5f 42 62  32 7d f6 6c 2f 6e 3b 38  |.2t.K_Bb2}.l/n;8|

This hex dump shows three 64-tuples. The middle (all zeros) one is insanely unlikely to find purely by accident, but the ones either side are just as unlikely, each one has a probability of 1 in 2²⁰⁴⁸. But we weren't finding it by accident, we found it because we set up the generator so that it was just about to find it.

Of course, there was nothing special about the all-zeros tuple. This pcg32_k64 generator

6364136223846793005 18229966379671291743 3080518731360262058 1720944944 432085256 164919839 3279400193 3664508459 1259284856 3971311073 32898496 1736123209 2781149096 315608947 2110629600 428954957 1646422668 4056717213 366951233 2902166596 4011607104 422547446 878473022 1908729292 2750914239 3148092510 1736075020 2773223631 866169378 1099849907 1961071182 2275775463 2111724403 3665144425 4277577646 4243877966 4104562137 770186120 1946142260 3042053536 1973887130 3758193630 4239953883 1331949016 1449939955 166741979 453090144 1078644917 1508302046 2862162312 2652703760 1056156511 603192735 1652014025 2348212519 367608186 1728434 1384175528 3138084825 1269769983 2630809274 2192622749 3779229149 754727364 1775785551 1990222858 3287727892

produces this output as its first three 64-tuples:

00000000  1c 7e 30 03 99 08 8e 0e  f8 c5 a8 ff b9 98 24 2b  |.~0...........$+|
00000010  8b bb b9 fd a5 df 10 08  17 fc 55 52 2e 51 6e 4a  |..........UR.QnJ|
00000020  fd d3 c8 94 ae 9f 3d a7  57 34 3f 4f 0a 32 34 80  |......=.W4?O.24.|
00000030  1e c0 47 9b a9 d2 06 43  40 ee c3 88 4f 17 b2 40  |..G....C@...O..@|
00000040  d1 25 7f f1 c4 63 8d 41  2f f9 ed 4e c6 2d 7e c9  |.%...c.A/..N.-~.|
00000050  11 1e c0 c3 75 46 6e d3  95 6a 71 6f 5b 5d a6 7a  |....uFn..jqo[].z|
00000060  6b 42 fd a0 4c d3 6b 96  eb cd 9e f2 86 bc 6d 1d  |kB..L.k.......m.|
00000070  73 a7 ad 2e 4e 93 25 96  7e a0 0a 27 1d 35 f7 69  |s...N.%.~..'.5.i|
00000080  54 bb 47 5e b6 8e 51 32  da b9 d8 64 fb 96 1f ab  |T.G^..Q2...d....|
00000090  87 5f 00 a4 e9 ac 65 0c  db 05 66 70 f9 3d 94 6c  |._....e...fp.=.l|
000000a0  91 b4 a0 68 bf ef 19 cb  a8 5d 9c d4 d2 0d 1d 16  |...h.....]......|
000000b0  9b 24 98 2c 59 a5 a7 a2  f6 d1 8a 0d b1 90 ff ea  |.$.,Y...........|
000000c0  cb 56 d5 ae 56 13 e8 e9  af 61 64 7c b8 ae 72 e4  |.V..V....ad|..r.|
000000d0  cd 0a 8b 17 44 ef cf 5b  d0 a3 b5 77 23 e4 76 1b  |....D..[...w#.v.|
000000e0  52 32 f8 2e 39 42 d0 58  8c 4b f8 db 08 9d 89 99  |R2..9B.X.K......|
000000f0  4b 67 0a e0 55 27 c3 7f  b3 1f f3 91 08 c4 f1 83  |Kg..U'..........|

00000100  2f 2f 20 50 43 47 2c 20  73 65 65 20 70 63 67 2d  |// PCG, see pcg-|
00000110  72 61 6e 64 6f 6d 2e 6f  72 67 0a 0a 23 69 6e 63  |random.org..#inc|
00000120  6c 75 64 65 20 3c 73 74  64 69 6f 2e 68 3e 0a 23  |lude <stdio.h>.#|
00000130  69 6e 63 6c 75 64 65 20  3c 73 74 64 69 6e 74 2e  |include <stdint.|
00000140  68 3e 0a 0a 69 6e 74 20  6d 61 69 6e 28 29 20 7b  |h>..int main() {|
00000150  0a 09 75 69 6e 74 36 34  5f 74 20 73 20 3d 20 34  |..uint64_t s = 4|
00000160  32 3b 0a 09 66 6f 72 28  3b 3b 29 20 7b 0a 09 09  |2;..for(;;) {...|
00000170  73 20 3d 20 73 20 2a 20  36 33 36 34 31 33 36 32  |s = s * 63641362|
00000180  32 33 38 34 36 37 39 33  30 30 35 55 4c 4c 20 2b  |23846793005ULL +|
00000190  20 31 3b 0a 09 09 75 69  6e 74 33 32 5f 74 20 78  | 1;...uint32_t x|
000001a0  20 3d 20 28 28 73 20 3e  3e 20 31 38 29 20 5e 20  | = ((s >> 18) ^ |
000001b0  73 29 20 3e 3e 20 32 37  2c 20 72 20 3d 20 73 20  |s) >> 27, r = s |
000001c0  3e 3e 20 35 39 75 3b 0a  09 09 70 72 69 6e 74 66  |>> 59u;...printf|
000001d0  28 22 25 30 38 78 5c 6e  22 2c 20 28 78 20 3e 3e  |("%08x\n", (x >>|
000001e0  20 72 29 20 7c 20 28 78  20 3c 3c 20 28 28 2d 72  | r) | (x << ((-r|
000001f0  29 20 26 20 33 31 29 29  29 3b 0a 09 7d 0a 7d 0a  |) & 31)));..}.}.|

00000200  94 0a ec 8d 0c 01 30 8f  f7 8a ee 5c 7e c9 6a df  |......0....\~.j.|
00000210  6f 0c 9c c3 c1 c1 df b6  c6 ff 04 fd 42 94 fa 3a  |o...........B..:|
00000220  b7 99 34 3e 26 5a c6 1f  b0 7c 1c 45 50 14 ca b1  |..4>&Z...|.EP...|
00000230  9d 32 78 8d d9 f2 27 5e  db 1a dd c5 60 8c 41 a3  |.2x...'^....`.A.|
00000240  b1 6e 49 67 08 6a 8e b8  92 98 db 73 d3 76 f5 b0  |.nIg.j.....s.v..|
00000250  16 c7 8d b5 2d a3 c5 e7  3c 21 10 f8 61 c6 e1 89  |....-...<!..a...|
00000260  f2 7c 8e 83 dd 85 e7 5f  1a 2e c8 55 a5 72 bd 9b  |.|....._...U.r..|
00000270  af 2b 61 a6 f2 88 b3 73  98 ce c2 96 63 82 f0 d5  |.+a....s....c...|
00000280  54 e1 db c1 59 9e 4b 9c  76 69 80 3a 19 ea a4 6f  |T...Y.K.vi.:...o|
00000290  53 f4 ba 72 98 32 38 29  ba f5 13 11 1b f0 37 29  |S..r.28)......7)|
000002a0  75 f0 d3 a1 47 d2 b8 65  20 7c 07 5e c5 ff 2e 25  |u...G..e |.^...%|
000002b0  a5 0d 8b 36 87 0a 53 5b  da 11 a5 a3 4e 14 dd 9c  |...6..S[....N...|
000002c0  18 eb 9f 4d d4 13 e3 35  9b 96 d1 01 4a 63 26 46  |...M...5....Jc&F|
000002d0  83 35 36 73 4b 2b b8 f2  bf b7 58 6f 2a ea e7 f1  |.56sK+....Xo*...|
000002e0  b5 a8 ab 59 a4 ec 53 2d  62 e4 cd 1c d1 bd 22 0a  |...Y..S-b.....".|
000002f0  1d 94 6c 73 30 31 04 8d  6b 88 b6 fd 39 4b e4 5a  |..ls01..k...9K.Z|

Here, the middle tuple is this 256-byte C program:

// PCG, see pcg-random.org

#include <stdio.h>
#include <stdint.h>

int main() {
        uint64_t s = 42;
        for(;;) {
                s = s * 6364136223846793005ULL + 1;
                uint32_t x = ((s >> 18) ^ s) >> 27, r = s >> 59u;
                printf("%08x\n", (x >> r) | (x << ((-r) & 31)));
        }
}

which actually implements a program which outputs values from a pcg32 generator.

There is actually nothing very special about contriving the state of a k-dimensionally equidistributed generator to produce a specific output—we could, for example, do the same with the Mersenne Twister—but it's worth noticing that there is no connection between the 64-tuples. All the ones that precede our desired tuple and all the ones that follow it look completely random. The same can't be said for the Mersenne Twister. If we create a state that has a lot of zeros in it, it'll take a long time to recover from that state, so it's not as well suited for doing party tricks.

16384-Dimensional Party Tricks

We can do exactly the same thing to produce 64 KB files using pcg32_k16384 as our RNG. Here's a program that reads the internal state of the generator from standard input and an amount by which to advance the generator and then generates 64 KB of data from the RNG and outputs it to a file data.raw:

// Example of 16384-dimensional distribution party trick
// (c) 2014 M.E. O'Neill / Apache license / pcg-random.org

#include <cstdio>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <random>

#include "pcg_random.hpp"

constexpr size_t MAX_SIZE = 64 * 1024;

char buffer[MAX_SIZE];

int main(int argc, char** argv)
{
    pcg32_k16384 rng;
    std::cin >> rng;

    size_t magnifier = 1;
    for (size_t i = 1; i < argc; ++i) {
        uint64_t adv = strtoull(argv[i], nullptr, 0);
        std::cout << "Advancing by " << adv << " * " << magnifier << std::endl;
        for (size_t j = 0; j < magnifier; ++j)
            rng.advance(adv);
        magnifier *= 256;
    }

    // This way of converting to characters is a little clumsy, but it
    // is portable and doesn't depend on the endian of the machine.
    std::cout << "Generating " << MAX_SIZE/4 << " 'random' numbers\n";
    uint32_t randval;
    for (int i = 0; i < MAX_SIZE; ++i) {
        if (i % 4 == 0)
            randval = rng();
        else
            randval >>= 8;
        buffer[i] = char(randval);
    }

    std::cout << "Writing " << MAX_SIZE << " bytes to data.raw\n";
    std::ofstream partyFile ("data.raw", std::ios::out | std::ios::binary);
    partyFile.write(buffer, MAX_SIZE);

    return 0;
}

The generator states for doing these party tricks are, necessarily, large, but you can download a zip file with four party-trick generator states and the above program. (You'll also need to download the PCG generators themselves, if you haven't done so already.)

unix% ./use-64kb-trick 0 < much_ado.pcg32_k16384
Advancing by 0 * 1
Generating 16384 'random' numbers
Writing 65536 bytes to data.raw
unix% file data.raw
data.raw: data
unix% hexdump -C data.raw | head -8
00000000  8e ae 6f b6 03 52 03 0b  69 d7 04 6b 62 9a 99 60  |..o..R..i..kb..`|
00000010  5e c0 e2 24 15 ad 2d 9f  0d 4c ee de 37 d2 0d a9  |^..$..-..L..7...|
00000020  22 25 28 14 c2 55 94 a8  a6 f7 3f de e3 9e b8 29  |"%(..U....?....)|
00000030  f2 d5 19 bc 90 74 79 2c  af 4e 76 a0 62 11 8c 55  |.....ty,.Nv.b..U|
00000040  f0 cc 65 c7 44 2d 00 39  3c 2d 5b 50 0b b4 cf 1a  |..e.D-.9<-[P....|
00000050  01 72 e0 af 26 5b e0 15  81 63 51 c0 40 6c 48 5d  |.r..&[...cQ.@lH]|
00000060  dc f6 db a0 79 33 f2 18  ba 11 96 66 57 69 0d 76  |....y3.....fWi.v|
00000070  60 4b b4 f2 54 7d 8c c0  1e b1 96 5f 3d ce 52 e1  |`K..T}....._=.R.|
unix% xz -c < data.raw | wc -c
   65600

unix% ./use-64kb-trick 1234567890 < much_ado.pcg32_k16384
Advancing by 1234567890 * 1
Generating 16384 'random' numbers
Writing 65536 bytes to data.raw
unix% file data.raw
data.raw: data
unix% hexdump -C data.raw | head -8
00000000  6e ea f1 f3 17 2d 47 5f  6c 55 59 8e ae 77 af 8a  |n....-G_lUY..w..|
00000010  85 df 6b 85 9a 0b b4 3a  e7 27 82 e8 d6 19 4f b6  |..k....:.'....O.|
00000020  ae 42 ae 15 00 f9 9a 17  7c 14 8a cc 8a 7b 00 de  |.B......|....{..|
00000030  8d 6d aa c3 4b e4 83 32  d4 b3 8e 79 f5 53 f4 37  |.m..K..2...y.S.7|
00000040  2a 69 9f fc d5 39 78 8d  df 07 48 32 98 f7 b2 cd  |*i...9x...H2....|
00000050  e5 d8 a0 28 5e 51 84 8a  e8 a6 ff 4d 78 48 5e 33  |...(^Q.....MxH^3|
00000060  98 6a 94 f4 ee c1 e8 f6  eb 02 ef 97 64 2e c3 68  |.j..........d..h|
00000070  7f c1 28 0e e9 9a 4d b8  a4 fe cd fe 1d 24 d8 ce  |..(...M......$..|
unix% xz -c < data.raw | wc -c
   65600

unix% ./use-64kb-trick 3141592653589793238 < much_ado.pcg32_k16384
Advancing by 3141592653589793238 * 1
unix% file data.raw
data.raw: Zip archive data, at least v1.0 to extract
unix% unzip -l data.raw
Archive:  data.raw
  Length     Date   Time    Name
 --------    ----   ----    ----
        0  11-01-14 21:25   much_ado/
   132600  11-01-14 21:17   much_ado/much_ado.md
      175  11-01-14 21:25   much_ado/README.txt
 --------                   -------
   132775                   3 files

unix% ./use-64kb-trick 191 12271846303085129837 < hamlet.pcg32_k16384
Advancing by 191 * 1
Advancing by 12271846303085129837 * 256
Generating 16384 'random' numbers
Writing 65536 bytes to data.raw
unix% file data.raw
data.raw: Zip archive data, at least v1.0 to extract
unix% unzip -l data.raw
Archive:  data.raw
  Length     Date   Time    Name
 --------    ----   ----    ----
        0  11-01-14 21:19   hamlet/
    64864  11-01-14 20:43   hamlet/hamlet.md.xz
      221  11-01-14 21:08   hamlet/README.txt
 --------                   -------
    65085                   3 files