1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
<head>
<link href="../../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
<link href="../../style.css" rel="stylesheet"/>
<title>BQN: Implementation of random stuff</title>
</head>
<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div>
<h1 id="implementation-of-random-stuff"><a class="header" href="#implementation-of-random-stuff">Implementation of random stuff</a></h1>
<p>BQN's random number utilities are provided by <a href="../../spec/system.html#random-generation">system functions</a> and include some with non-obvious implementations. In the text below, <code><span class='Value'>rand</span></code> represents any random number generator: <code><span class='Value'>•rand</span></code>, or a result of <code><span class='Function'>•MakeRand</span></code>.</p>
<h2 id="random-number-generation"><a class="header" href="#random-number-generation">Random number generation</a></h2>
<p>CBQN is currently using wyrand, part of the <a href="https://github.com/wangyi-fudan/wyhash">wyhash</a> library. It's extremely fast, passes the expected test suites, and no one's raised any concerns about it yet (but it's very new). It uses only 64 bits of state and doesn't have extra features like jump ahead.</p>
<p>Other choices are <a href="https://prng.di.unimi.it/">xoshiro++</a> and <a href="https://www.pcg-random.org/">PCG</a>. The authors of these algorithms (co-author for xoshiro) hate each other very much and have spent quite some time slinging mud at each other. As far as I can tell they both have the normal small bias in favor of their own algorithms but are wildly unfair towards the other side, choosing misleading examples and inflating minor issues. I think both generators are good but find the case for xoshiro a little more convincing, and I think it's done better in third-party benchmarks.</p>
<h2 id="simple-random-sample"><a class="header" href="#simple-random-sample">Simple random sample</a></h2>
<p>A <a href="https://en.wikipedia.org/wiki/Simple_random_sample">simple random sample</a> from a set is a subset with a specified size, chosen so that each subset of that size has equal probability. <code><span class='Value'>rand.</span><span class='Function'>Deal</span></code> gets a sample of size <code><span class='Value'>𝕨</span></code> from the set <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code> with elements in a uniformly random order, and <code><span class='Value'>rand.</span><span class='Function'>Subset</span></code> does the same but sorts the elements.</p>
<p><code><span class='Function'>Deal</span></code> uses a <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Knuth shuffle</a>, stopping after the first <code><span class='Value'>𝕨</span></code> elements have been shuffled, as the algorithm won't touch them again. Usually it creates <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code> explicitly for this purpose, but if <code><span class='Value'>𝕨</span></code> is very small then initializing it is too slow. In this case we initialize <code><span class='Function'>↕</span><span class='Value'>𝕨</span></code>, but use a "hash" table with an identity hash—the numbers are already random—for <code><span class='Value'>𝕨</span><span class='Function'>↓↕</span><span class='Value'>𝕩</span></code>. The default is that every value in the table is equal to its key, so that only entries where a swap has happened need to be stored. The hash table is the same design as for self-search functions, with open addressing and linear probing.</p>
<p><code><span class='Function'>Subset</span></code> uses <a href="https://math.stackexchange.com/questions/178690/whats-the-proof-of-correctness-for-robert-floyds-algorithm-for-selecting-a-sin">Floyd's method</a>, which is sort of a modification of shuffling where only the selected elements need to be stored, not what they were swapped with. This requires a lookup structure that can be updated efficiently and output all elements in sorted order. The choices are a bitset for large <code><span class='Value'>𝕨</span></code> and another not-really-hash table for small <code><span class='Value'>𝕨</span></code>. The table uses a right shift—that is, division by a power of two—as a hash so that hashing preserves the ordering, and inserts like an insertion sort: any larger entries are pushed forward. Really this is an online sorting algorithm, that works because we know the input distribution is well-behaved (it degrades to quadratic performance only in very unlikely cases). When <code><span class='Value'>𝕨</span><span class='Function'>></span><span class='Value'>𝕩</span><span class='Function'>÷</span><span class='Number'>2</span></code>, we always use a bitset, but select <code><span class='Value'>𝕩</span><span class='Function'>-</span><span class='Value'>𝕨</span></code> elements and invert the selection.</p>
<p>I'm aware of <a href="https://richardstartin.github.io/posts/reservoir-sampling">algorithms</a> like Vitter's Method D that generate a sorted sample in order, using the statistics of samples. There are a few reasons why I prefer Floyd's method. It's faster, because it uses one random generation per element while Vitter requires several, and it does less branching. It's exact, in that if it's given uniformly random numbers then it makes a uniformly random choice of sample. Vitter's method depends on floating-point randomness and irrational functions, so it can't accomplish this with finite precision random inputs. And the pattern of requests for Floyd's method is simple and deterministic. The advantage of reservoir algorithms like Vitter is that they are able to generate samples one at a time using a small fixed amount of memory. <code><span class='Function'>•MakeRand</span></code> only allows the user to request a sample all at once, so this advantage doesn't matter as much. The CBQN algorithms are tuned to use much more temporary memory than the size of the final result. It could be lowered, but there's usually plenty of temporary memory available.</p>
|
