Additional-mtwist-notes.html 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
  2. <html>
  3. <!-- Created on December 10, 2012 by texi2html 1.82
  4. texi2html was written by:
  5. Lionel Cons <[email protected]> (original author)
  6. Karl Berry <[email protected]>
  7. Olaf Bachmann <[email protected]>
  8. and many others.
  9. Maintained by: Many creative people.
  10. Send bugs and suggestions to <[email protected]>
  11. -->
  12. <head>
  13. <title>avram - a virtual machine code interpreter: D.12.3 Additional mtwist notes</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: D.12.3 Additional mtwist notes">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: D.12.3 Additional mtwist notes">
  16. <meta name="resource-type" content="document">
  17. <meta name="distribution" content="global">
  18. <meta name="Generator" content="texi2html 1.82">
  19. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  20. <style type="text/css">
  21. <!--
  22. a.summary-letter {text-decoration: none}
  23. blockquote.smallquotation {font-size: smaller}
  24. pre.display {font-family: serif}
  25. pre.format {font-family: serif}
  26. pre.menu-comment {font-family: serif}
  27. pre.menu-preformatted {font-family: serif}
  28. pre.smalldisplay {font-family: serif; font-size: smaller}
  29. pre.smallexample {font-size: smaller}
  30. pre.smallformat {font-family: serif; font-size: smaller}
  31. pre.smalllisp {font-size: smaller}
  32. span.roman {font-family:serif; font-weight:normal;}
  33. span.sansserif {font-family:sans-serif; font-weight:normal;}
  34. ul.toc {list-style: none}
  35. -->
  36. </style>
  37. </head>
  38. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  39. <a name="Additional-mtwist-notes"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="mtwist-exceptions.html#mtwist-exceptions" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="minpack.html#minpack" title="Next section in reading order"> &gt; </a>]</td>
  43. <td valign="middle" align="left"> &nbsp; </td>
  44. <td valign="middle" align="left">[<a href="External-Libraries.html#External-Libraries" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  45. <td valign="middle" align="left">[<a href="mtwist.html#mtwist" title="Up section"> Up </a>]</td>
  46. <td valign="middle" align="left">[<a href="Copying.html#Copying" title="Next chapter"> &gt;&gt; </a>]</td>
  47. <td valign="middle" align="left"> &nbsp; </td>
  48. <td valign="middle" align="left"> &nbsp; </td>
  49. <td valign="middle" align="left"> &nbsp; </td>
  50. <td valign="middle" align="left"> &nbsp; </td>
  51. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  52. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  53. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  54. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  55. </tr></table>
  56. <hr size="1">
  57. <a name="Additional-mtwist-notes-1"></a>
  58. <h3 class="subsection">D.12.3 Additional <code>mtwist</code> notes</h3>
  59. <p>Although the <code>mtwist</code> library is &ldquo;external&rdquo;, it requires no
  60. special configuration on the host because the uniform variate
  61. generator in the form developed by its original authors is short and
  62. elegant enough to be packaged easily within the <code>avram</code>
  63. distribution. All further embellishments are home grown despite the
  64. advice at the end of <a href="Implementing-new-library-functions.html#Implementing-new-library-functions">Implementing new library functions</a>.
  65. </p>
  66. <p>The <code>u_path</code> function is intended to allow sampling from a large
  67. population in logarithmic time when it is stored in a balanced tree. A
  68. left-heavy tree should be constructed initially with the data items
  69. all at the same level. Thereafter, a result returned by <code>u_path</code>
  70. with the appropriate dimensions can be used as an index into the tree
  71. for fast retrieval by the virtual machine&rsquo;s <code>field</code> combinator
  72. (<a href="Field.html#Field">Field</a>).
  73. </p>
  74. <p>The last three functions, <code>u_enum</code>, <code>w_disc</code>, and
  75. <code>w_enum</code> use an inversion method with a binary search. The first
  76. draw from a given list will take a time asymptotically proportional to
  77. the length of the list, but subsequent draws from the same list are
  78. considerably faster due to a persistent cache maintained transparently
  79. by <code>avram</code>. For lists whose length is up to 2^16, the time
  80. required for a subsequent draw consists mainly of constant overhead
  81. with a small logarithmic component in the length of the list. For
  82. longer lists, the time ramps up linearly by a small factor.
  83. </p>
  84. <p>Information allowing fast draws from up to sixteen lists can be cached
  85. simultaneously. If an application uses more than sixteen, the cached
  86. data are replaced in first-in first-out order. The size of the cache
  87. and the maximum list length for logarithmic time access can be
  88. adjusted easily by redefining constants in &lsquo;<tt>mtwist.c</tt>&rsquo; under the
  89. <code>avram</code> source tree, but will require recompilation.
  90. </p>
  91. <hr size="1">
  92. <table cellpadding="1" cellspacing="1" border="0">
  93. <tr><td valign="middle" align="left">[<a href="mtwist-exceptions.html#mtwist-exceptions" title="Previous section in reading order"> &lt; </a>]</td>
  94. <td valign="middle" align="left">[<a href="minpack.html#minpack" title="Next section in reading order"> &gt; </a>]</td>
  95. <td valign="middle" align="left"> &nbsp; </td>
  96. <td valign="middle" align="left">[<a href="External-Libraries.html#External-Libraries" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  97. <td valign="middle" align="left">[<a href="mtwist.html#mtwist" title="Up section"> Up </a>]</td>
  98. <td valign="middle" align="left">[<a href="Copying.html#Copying" title="Next chapter"> &gt;&gt; </a>]</td>
  99. <td valign="middle" align="left"> &nbsp; </td>
  100. <td valign="middle" align="left"> &nbsp; </td>
  101. <td valign="middle" align="left"> &nbsp; </td>
  102. <td valign="middle" align="left"> &nbsp; </td>
  103. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  104. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  105. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  106. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  107. </tr></table>
  108. <p>
  109. <font size="-1">
  110. This document was generated on <i>December 10, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  111. </font>
  112. <br>
  113. </p>
  114. </body>
  115. </html>