diff options
Diffstat (limited to 'docs/implementation/primitive')
| -rw-r--r-- | docs/implementation/primitive/index.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/random.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/replicate.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/sort.html | 2 |
4 files changed, 4 insertions, 4 deletions
diff --git a/docs/implementation/primitive/index.html b/docs/implementation/primitive/index.html index 25c831c3..b5256302 100644 --- a/docs/implementation/primitive/index.html +++ b/docs/implementation/primitive/index.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Primitive implementation notes</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a></div> <h1 id="primitive-implementation-notes">Primitive implementation notes</h1> <p>Commentary on the best methods I know for implementing various primitives. Often there are many algorithms that are viable in different situations, and in these cases I try to discuss the tradeoffs.</p> <ul> diff --git a/docs/implementation/primitive/random.html b/docs/implementation/primitive/random.html index 943fd955..7f660792 100644 --- a/docs/implementation/primitive/random.html +++ b/docs/implementation/primitive/random.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Implementation of random stuff</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> +<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">Implementation of random stuff</h1> <p>Not a primitive, but CBQN's <code><span class='Function'>•MakeRand</span></code> initializes a random number generator that has some built-in utilities. For clarity we'll call a result of this initialization <code><span class='Value'>rand</span></code> in the text below.</p> <h2 id="random-number-generation">Random number generation</h2> diff --git a/docs/implementation/primitive/replicate.html b/docs/implementation/primitive/replicate.html index 5b9cf07b..9d539d40 100644 --- a/docs/implementation/primitive/replicate.html +++ b/docs/implementation/primitive/replicate.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Implementation of Indices and Replicate</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> +<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-indices-and-replicate">Implementation of Indices and Replicate</h1> <p>The replicate family of functions contains not just primitives but powerful tools for implementing other functionality. The most important is converting <a href="#booleans-to-indices">bits to indices</a>: AVX-512 extensions implement this natively for various index sizes, and even with no SIMD support at all there are surprisingly fast table-based algorithms for it.</p> <p><a href="#replicate">General replication</a> is more complex. Branching will slow many useful cases down considerably when using the obvious solution. However, branch-free techniques introduce overhead for larger replication amounts. Hybridizing these seems to be the only way, but it's finicky.</p> diff --git a/docs/implementation/primitive/sort.html b/docs/implementation/primitive/sort.html index 86c36738..2a417770 100644 --- a/docs/implementation/primitive/sort.html +++ b/docs/implementation/primitive/sort.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Implementation of ordering functions</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> +<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-ordering-functions">Implementation of ordering functions</h1> <p>The <a href="../../doc/order.html">ordering functions</a> are Sort (<code><span class='Function'>∧∨</span></code>), Grade (<code><span class='Function'>⍋⍒</span></code>), and Bins (<code><span class='Function'>⍋⍒</span></code>). Although these are well-studied—particularly sorting, and then binary search or "predecessor search"—there are many recent developments, as well as techniques that I have not found in the literature. The three functions are closely related but have important differences in what algorithms are viable. Sorting is a remarkably deep problem with different algorithms able to do a wide range of amazing things, and sophisticated ways to combine those. It is by no means solved. In comparison, Bins is pretty tame.</p> <p>There's a large divide between ordering compound data and simple data. For compound data comparisons are expensive, and the best algorithm will generally be the one that uses the fewest comparisons. For simple data they fall somewhere between cheap and extremely cheap, and fancy branchless and vectorized algorithms are the best.</p> |