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.

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