[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

### D.12.3 Additional `mtwist` notes

Although the `mtwist` library is “external”, it requires no special configuration on the host because the uniform variate generator in the form developed by its original authors is short and elegant enough to be packaged easily within the `avram` distribution. All further embellishments are home grown despite the advice at the end of Implementing new library functions.

The `u_path` function is intended to allow sampling from a large population in logarithmic time when it is stored in a balanced tree. A left-heavy tree should be constructed initially with the data items all at the same level. Thereafter, a result returned by `u_path` with the appropriate dimensions can be used as an index into the tree for fast retrieval by the virtual machine’s `field` combinator (Field).

The last three functions, `u_enum`, `w_disc`, and `w_enum` use an inversion method with a binary search. The first draw from a given list will take a time asymptotically proportional to the length of the list, but subsequent draws from the same list are considerably faster due to a persistent cache maintained transparently by `avram`. For lists whose length is up to 2^16, the time required for a subsequent draw consists mainly of constant overhead with a small logarithmic component in the length of the list. For longer lists, the time ramps up linearly by a small factor.

Information allowing fast draws from up to sixteen lists can be cached simultaneously. If an application uses more than sixteen, the cached data are replaced in first-in first-out order. The size of the cache and the maximum list length for logarithmic time access can be adjusted easily by redefining constants in ‘`mtwist.c`’ under the `avram` source tree, but will require recompilation.

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

This document was generated on November 8, 2012 using texi2html 1.82.