diff options
| -rw-r--r-- | doc/fromDyalog.md | 2 | ||||
| -rw-r--r-- | doc/fromJ.md | 1 | ||||
| -rw-r--r-- | docs/doc/fromDyalog.html | 2 | ||||
| -rw-r--r-- | docs/doc/fromJ.html | 5 | ||||
| -rw-r--r-- | docs/spec/system.html | 28 | ||||
| -rw-r--r-- | spec/system.md | 18 |
6 files changed, 54 insertions, 2 deletions
diff --git a/doc/fromDyalog.md b/doc/fromDyalog.md index edc6a3d7..47bf2267 100644 --- a/doc/fromDyalog.md +++ b/doc/fromDyalog.md @@ -94,7 +94,7 @@ The form `F⍣G` (Power with a function right operand; Power limit) must be impl <tr><td> <code>!</code> </td><td><code>×´1+↕</code> </td><td> <code>-˜(+÷○(×´)⊢)1+↕∘⊣</code></td></tr> <tr><td> <code>○</code> </td><td> <code>π⊸×</code> </td><td> <code>•math</code></td> </tr> <tr><td> <code>~</code> </td><td> <code>¬</code> </td><td> <code>¬∘∊/⊣</code></td> </tr> -<tr><td> <code>?</code> </td><td colspan=2>Library?</td> </tr> +<tr><td> <code>?</code> </td><td> <code>r.Range⚇0</code> </td><td> <code>r.Deal</code> with <code>r←•MakeRand num</code></td></tr> <tr><td> <code>⍲</code> </td><td> </td><td> <code>¬∘∧</code></td> </tr> <tr><td> <code>⍱</code> </td><td> </td><td> <code>¬∘∨</code></td> </tr> <tr><td> <code>⍴</code> </td><td> <code>≢</code> </td><td> <code>⥊</code></td> </tr> diff --git a/doc/fromJ.md b/doc/fromJ.md index 6363420b..2168a168 100644 --- a/doc/fromJ.md +++ b/doc/fromJ.md @@ -140,6 +140,7 @@ The tables below give approximate implementations of J primitives. J has a whole | `}:` | `¯1⊸↓` | | `".` | `•Eval` | | `":` | `•Fmt` | +| `?` | `r.Range⚇0` | `r.Deal` with `r←•MakeRand num` | `e.` | `><∘∾∊¨⊢` | `∊` | `E.` | | `⍷` | `i.` | `↕` (`⥊⟜(↕×´)` for lists) | `⊐` diff --git a/docs/doc/fromDyalog.html b/docs/doc/fromDyalog.html index 84928cca..28b47fbb 100644 --- a/docs/doc/fromDyalog.html +++ b/docs/doc/fromDyalog.html @@ -283,7 +283,7 @@ <tr><td> <code><span class='Function'>!</span></code> </td><td><code><span class='Function'>×</span><span class='Modifier'>´</span><span class='Number'>1</span><span class='Function'>+↕</span></code> </td><td> <code><span class='Function'>-</span><span class='Modifier'>˜</span><span class='Paren'>(</span><span class='Function'>+÷</span><span class='Modifier2'>○</span><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>´</span><span class='Paren'>)</span><span class='Function'>⊢</span><span class='Paren'>)</span><span class='Number'>1</span><span class='Function'>+↕</span><span class='Modifier2'>∘</span><span class='Function'>⊣</span></code></td></tr> <tr><td> <code><span class='Modifier2'>○</span></code> </td><td> <code><span class='Number'>π</span><span class='Modifier2'>⊸</span><span class='Function'>×</span></code> </td><td> <code><span class='Value'>•math</span></code></td> </tr> <tr><td> <code><span class='Value'>~</span></code> </td><td> <code><span class='Function'>¬</span></code> </td><td> <code><span class='Function'>¬</span><span class='Modifier2'>∘</span><span class='Function'>∊/⊣</span></code></td> </tr> -<tr><td> <code><span class='Value'>?</span></code> </td><td colspan=2>Library?</td> </tr> +<tr><td> <code><span class='Value'>?</span></code> </td><td> <code><span class='Value'>r.</span><span class='Function'>Range</span><span class='Modifier2'>⚇</span><span class='Number'>0</span></code> </td><td> <code><span class='Value'>r.</span><span class='Function'>Deal</span></code> with <code><span class='Value'>r</span><span class='Gets'>←</span><span class='Function'>•MakeRand</span> <span class='Value'>num</span></code></td></tr> <tr><td> <code><span class='Value'>⍲</span></code> </td><td> </td><td> <code><span class='Function'>¬</span><span class='Modifier2'>∘</span><span class='Function'>∧</span></code></td> </tr> <tr><td> <code><span class='Value'>⍱</span></code> </td><td> </td><td> <code><span class='Function'>¬</span><span class='Modifier2'>∘</span><span class='Function'>∨</span></code></td> </tr> <tr><td> <code><span class='Value'>⍴</span></code> </td><td> <code><span class='Function'>≢</span></code> </td><td> <code><span class='Function'>⥊</span></code></td> </tr> diff --git a/docs/doc/fromJ.html b/docs/doc/fromJ.html index 10dff0d7..5a46cf90 100644 --- a/docs/doc/fromJ.html +++ b/docs/doc/fromJ.html @@ -579,6 +579,11 @@ <td></td> </tr> <tr> +<td><code><span class='Value'>?</span></code></td> +<td><code><span class='Value'>r.</span><span class='Function'>Range</span><span class='Modifier2'>⚇</span><span class='Number'>0</span></code></td> +<td><code><span class='Value'>r.</span><span class='Function'>Deal</span></code> with <code><span class='Value'>r</span><span class='Gets'>←</span><span class='Function'>•MakeRand</span> <span class='Value'>num</span></code></td> +</tr> +<tr> <td><code><span class='Value'>e.</span></code></td> <td><code><span class='Function'>><</span><span class='Modifier2'>∘</span><span class='Function'>∾∊</span><span class='Modifier'>¨</span><span class='Function'>⊢</span></code></td> <td><code><span class='Function'>∊</span></code></td> diff --git a/docs/spec/system.html b/docs/spec/system.html index 76d36a2f..477f32b4 100644 --- a/docs/spec/system.html +++ b/docs/spec/system.html @@ -446,3 +446,31 @@ <p>The <a href="https://en.wikipedia.org/wiki/Unix_time">Unix epoch</a> is 1970-01-01 00:00:00 UTC. <code><span class='Function'>•UnixTime</span></code> is intended for absolute time measurement and should be implemented with the method that gives the most accurate result at any given time. <code><span class='Function'>•MonoTime</span></code> is intended for relative measurement and should use the method that gives the most precise time differences over the course of the program. Its return value must never decrease between calls.</p> <p><code><span class='Modifier'>•_timed</span></code> returns the total time taken divided by the number of function calls (<code><span class='Value'>𝕨</span></code> if provided and 1 otherwise), including the overhead required for the outer loop that counts iterations (which will typically be negligible in comparison to the BQN code).</p> <p>More accurately the modifier <code><span class='Modifier2'>•_maxTime_</span></code> <em>may</em> fail if execution of <code><span class='Function'>𝔽</span></code> takes over <code><span class='Value'>𝕨</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span></code> seconds, and should fail as quickly as it is practically able to. The most likely way to implement this modifier is to interrupt execution at the given time. If <code><span class='Function'>𝔽</span></code> completes before the interrupt there is no need to measure the amount of time it actually took.</p> +<h2 id="random-generation"><a class="header" href="#random-generation">Random generation</a></h2> +<p><code><span class='Function'>•MakeRand</span></code> initializes a deterministic pseudorandom number generator with seed value <code><span class='Value'>𝕩</span></code>. <code><span class='Value'>•rand</span></code>, if it exists, is a globally accessible generator initialized at first use. A random generator has the following member functions:</p> +<table> +<thead> +<tr> +<th>Name</th> +<th>Summary</th> +</tr> +</thead> +<tbody> +<tr> +<td><code><span class='Function'>Range</span></code></td> +<td>An array of shape <code><span class='Value'>𝕨</span><span class='Function'>⊣</span><span class='Bracket'>⟨⟩</span></code> selected from <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code></td> +</tr> +<tr> +<td><code><span class='Function'>Deal</span></code></td> +<td>A simple random sample of <code><span class='Value'>𝕨</span><span class='Function'>⊣</span><span class='Value'>𝕩</span></code> elements of <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code></td> +</tr> +<tr> +<td><code><span class='Function'>Subset</span></code></td> +<td>A sorted SRS of <code><span class='Value'>𝕨</span></code> elements of <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code></td> +</tr> +</tbody> +</table> +<p>For each of these functions, <code><span class='Value'>𝕩</span></code> is a natural number. For <code><span class='Function'>Range</span></code>, <code><span class='Value'>𝕨</span></code> must be a valid shape if given, and for <code><span class='Function'>Deal</span></code> and <code><span class='Function'>Subset</span></code> it's a natural number less than or equal to <code><span class='Value'>𝕩</span></code>. All selections are made uniformly at random, that is, each possible result is equally likely. A simple random sample (SRS) of <code><span class='Value'>k</span></code> elements from list <code><span class='Value'>s</span></code> is a list of <code><span class='Value'>k</span></code> distinct elements of <code><span class='Value'>s</span></code> in any order. Both the choice of elements and their ordering must be uniformly random. <a href="../implementation/primitive/random.html#simple-random-sample">Recommended algorithms</a> for SRS selection are variants of a partial Knuth shuffle.</p> +<p>When <code><span class='Value'>𝕨</span></code> isn't given, <code><span class='Function'>Deal</span></code>'s result contains all elements of <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code>, making it a random shuffle of those values, or random permutation. In <code><span class='Function'>Subset</span></code>, setting <code><span class='Value'>𝕨</span></code> to <code><span class='Value'>𝕩</span></code> would instead always result in the list <code><span class='Function'>↕</span><span class='Value'>𝕩</span></code>; because this is not useful, <code><span class='Value'>𝕨</span></code> must be provided.</p> +<p>In <code><span class='Function'>Range</span></code>, <code><span class='Value'>𝕩</span></code> may be <code><span class='Number'>0</span></code>. In this case the result consists of floating-point numbers in the unit interval from 0 to 1. The numbers should have an overall uniform distribution, but their precision and whether the endpoints 0 and 1 are possible may depend on the implementation.</p> +<p>Ranges up to <code><span class='Number'>2</span><span class='Function'>⋆</span><span class='Number'>32</span></code> must be supported (that is, a maximum integer result of <code><span class='Paren'>(</span><span class='Number'>2</span><span class='Function'>⋆</span><span class='Number'>32</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Number'>1</span></code>) if the number system accommodates it. In implementations based on double-precision floats it's preferable but not required to support ranges up to <code><span class='Number'>2</span><span class='Function'>⋆</span><span class='Number'>53</span></code>.</p> diff --git a/spec/system.md b/spec/system.md index 041b4539..adfbcfd5 100644 --- a/spec/system.md +++ b/spec/system.md @@ -198,3 +198,21 @@ The [Unix epoch](https://en.wikipedia.org/wiki/Unix_time) is 1970-01-01 00:00:00 `•_timed` returns the total time taken divided by the number of function calls (`𝕨` if provided and 1 otherwise), including the overhead required for the outer loop that counts iterations (which will typically be negligible in comparison to the BQN code). More accurately the modifier `•_maxTime_` *may* fail if execution of `𝔽` takes over `𝕨𝔾𝕩` seconds, and should fail as quickly as it is practically able to. The most likely way to implement this modifier is to interrupt execution at the given time. If `𝔽` completes before the interrupt there is no need to measure the amount of time it actually took. + +## Random generation + +`•MakeRand` initializes a deterministic pseudorandom number generator with seed value `𝕩`. `•rand`, if it exists, is a globally accessible generator initialized at first use. A random generator has the following member functions: + +| Name | Summary +|-----------|------------------------------ +| `Range` | An array of shape `𝕨⊣⟨⟩` selected from `↕𝕩` +| `Deal` | A simple random sample of `𝕨⊣𝕩` elements of `↕𝕩` +| `Subset` | A sorted SRS of `𝕨` elements of `↕𝕩` + +For each of these functions, `𝕩` is a natural number. For `Range`, `𝕨` must be a valid shape if given, and for `Deal` and `Subset` it's a natural number less than or equal to `𝕩`. All selections are made uniformly at random, that is, each possible result is equally likely. A simple random sample (SRS) of `k` elements from list `s` is a list of `k` distinct elements of `s` in any order. Both the choice of elements and their ordering must be uniformly random. [Recommended algorithms](../implementation/primitive/random.md#simple-random-sample) for SRS selection are variants of a partial Knuth shuffle. + +When `𝕨` isn't given, `Deal`'s result contains all elements of `↕𝕩`, making it a random shuffle of those values, or random permutation. In `Subset`, setting `𝕨` to `𝕩` would instead always result in the list `↕𝕩`; because this is not useful, `𝕨` must be provided. + +In `Range`, `𝕩` may be `0`. In this case the result consists of floating-point numbers in the unit interval from 0 to 1. The numbers should have an overall uniform distribution, but their precision and whether the endpoints 0 and 1 are possible may depend on the implementation. + +Ranges up to `2⋆32` must be supported (that is, a maximum integer result of `(2⋆32)-1`) if the number system accommodates it. In implementations based on double-precision floats it's preferable but not required to support ranges up to `2⋆53`. |