txlyre
/
avram


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
							<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
<html>
<!-- Created on November 8, 2012 by texi2html 1.82
texi2html was written by: 
            Lionel Cons <[email protected]> (original author)
            Karl Berry  <[email protected]>
            Olaf Bachmann <[email protected]>
            and many others.
Maintained by: Many creative people.
Send bugs and suggestions to <[email protected]>
-->
<head>
<title>avram - a virtual machine code interpreter: D.12.3 Additional mtwist notes</title>

<meta name="description" content="avram - a virtual machine code interpreter: D.12.3 Additional mtwist notes">
<meta name="keywords" content="avram - a virtual machine code interpreter: D.12.3 Additional mtwist notes">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="texi2html 1.82">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
pre.display {font-family: serif}
pre.format {font-family: serif}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: serif; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: serif; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.roman {font-family:serif; font-weight:normal;}
span.sansserif {font-family:sans-serif; font-weight:normal;}
ul.toc {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">

<a name="Additional-mtwist-notes"></a>
<table cellpadding="1" cellspacing="1" border="0">
<tr><td valign="middle" align="left">[<a href="mtwist-exceptions.html#mtwist-exceptions" title="Previous section in reading order"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="minpack.html#minpack" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="External-Libraries.html#External-Libraries" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
<td valign="middle" align="left">[<a href="mtwist.html#mtwist" title="Up section"> Up </a>]</td>
<td valign="middle" align="left">[<a href="Copying.html#Copying" title="Next chapter"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
<td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
<td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
<td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
</tr></table>
<hr size="1">
<a name="Additional-mtwist-notes-1"></a>
<h3 class="subsection">D.12.3 Additional <code>mtwist</code> notes</h3>

<p>Although the <code>mtwist</code> library is &ldquo;external&rdquo;, 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 <code>avram</code>
distribution. All further embellishments are home grown despite the
advice at the end of <a href="Implementing-new-library-functions.html#Implementing-new-library-functions">Implementing new library functions</a>.
</p>
<p>The <code>u_path</code> 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 <code>u_path</code>
with the appropriate dimensions can be used as an index into the tree
for fast retrieval by the virtual machine&rsquo;s <code>field</code> combinator
(<a href="Field.html#Field">Field</a>).
</p>
<p>The last three functions, <code>u_enum</code>, <code>w_disc</code>, and
<code>w_enum</code> 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 <code>avram</code>. 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.
</p>
<p>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 &lsquo;<tt>mtwist.c</tt>&rsquo; under the
<code>avram</code> source tree, but will require recompilation.
</p>
<hr size="1">
<table cellpadding="1" cellspacing="1" border="0">
<tr><td valign="middle" align="left">[<a href="mtwist-exceptions.html#mtwist-exceptions" title="Previous section in reading order"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="minpack.html#minpack" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="External-Libraries.html#External-Libraries" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
<td valign="middle" align="left">[<a href="mtwist.html#mtwist" title="Up section"> Up </a>]</td>
<td valign="middle" align="left">[<a href="Copying.html#Copying" title="Next chapter"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
<td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
<td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
<td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
</tr></table>
<p>
 <font size="-1">
  This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
 </font>
 <br>

</p>
</body>
</html>