Skip to content

Latest commit

 

History

History
 
 

jump

readme.html

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE html
  PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html" />
    <meta name="keywords" content="tiny mt" />
    <title>TinyMT Jump Function</title>
    <style type="text/css">
      body {margin-right:10%;margin-left:10%}
    </style>
  </head>
  <body>
    <h2>TinyMT Jump Function</h2>
    <h2>READ ME FIRST</h2>

    <p>
      The jump function makes the internal state of TinyMT N-th forward
      state. When N is large, the jump calculation is much faster than
      generating N pseudorandom numbers. Users can get discrete sub
      sequences from pseudorandom number sequence.
    </p>
    <p>
      The jump function is written in standard C language, with
      standard library. But the function is written using
      stdint.h and inttypes.h, which are parts of C99 standard.
    </p>

    <h2>Three Methods of parallel generation of pseudorandom numbers
      using TinyMT</h2>

    <ol>
      <li>
	Getting multiple sequences of pseudorandom numbers by using
	one parameter set and changing seed of initialization.  The
	sequences obtained by this method are sub sequences of one
	long sequence, and it is difficult to know how far each sub
	sequences are from other ones. In the worst case, there may be
	a duplicated sub-sub sequence. Usually the probability of the
	worst case is negligible.  Merit of this method is saving
	memory in shared memory parallel programing models like
	multiple threads model, by setting the parameter set in shared
	constant memories.
      </li>
      <li>
	Getting multiple sequences of pseudorandom numbers by
	jump. The sequences obtained by this method are also sub
	sequences of one long sequence, but how far each sub sequences
	are from other ones are known, i.e. the number specified for
	jump. <!-- Each sub sequences are generated by the same parameter set,
	there may be a linear relation between particular bits.
	Such linear relation may influence the result of user's
	simulation, or may not.-->
	This method also has memory saving merit as above.
      </li>
      <li>
	Getting multiple sequences of pseudorandom numbers by
	using multiple parameter sets. The sequences obtained this
	method are regarded most independent each other.
	This method wastes memories than former methods.
      </li>
    </ol>

    <p>The jump function provides the second method. Our program does
    not save memories, users need to change the tinymt structure and
    to define parameters as constant to save memories.</p>

    <h2>Usage</h2>

    <h3>Compilation of test programs</h3>

    <p>Test program needs source programs of TinyMT to be compiled. And
    it needs the output parameter set of TinyMTDC for execution.
    </p>

    <ol>
      <li>Expand archive file</li>
      <li>Copy <b>jump</b> directory in TinyMTJump-src-xxxx to
	the directory of TinyMT.</li>
<pre>
TinyMT-src-xxx
   +---dc
   +---tinymt
   +---jump
</pre>
      <li>Change directory to copied jump directory</li>
      <li>Type <b>make all</b> to compile test program.</li>
      <li>Type <b>./jump_test32 d8524022ed8dff4a8dcc50c798faba43 8f7011ee fc78ff1f 3793fdff 1298</b></li>
      <li>Check if OK is showed and no NG</li>
    </ol>

    <h3>description of jump function</h3>
<pre>
void tinymt32_jump(tinymt32c_t *tiny,
                   uint64_t lower_step,
                   uint64_t upper_step,
                   const char * poly_str);
</pre>
    <dl>
      <dt>
	This function changes the internal state of tinymt32 to
	N (specified by lower_step and upper_step) steps forwards.
	N is between 0 and 2<sup>128</sup>-1.
      </dt>
      <dd><b>tiny</b> is a structure of type tinymt32_t.
	<b>tiny</b> must be initialized.
	<b>tiny</b> is overwritten by new jumped state.
      </dd>
      <dd><b>lower_step</b> and <b>upper_step</b>
	specifies how many steps tinymt jumps.
      Users can specify from zero to 2<sup>128</sup>-1 steps,
      using two 64-bit arguments.</dd>
      <dd><b>poly_str</b> is a string of characteristic polynomial,
	which is in the first column of outputs of tinymt32dc.
	</dd>
    </dl>
<pre>
void calculate_jump_polynomial(f2_polynomial *jump_poly,
                               uint64_t lower_step,
                               uint64_t upper_step,
                               const char * poly_str);
</pre>
    <dl>
      <dt>
	This function calculates <b>jump polynomial</b> from
	the characteristic polynomial, lower_step and upper_step.
	This function is time consuming.
      </dt>
      <dd><b>jump_polynomial</b> will be overwritten by a calculated
	jump polynomial.
      </dd>
      <dd><b>lower_step</b> and <b>upper_step</b>
	specifies how many steps tinymt jumps.
      Users can specify from zero to 2<sup>128</sup>-1 steps,
      using two 64-bit arguments.</dd>
      <dd><b>poly_str</b> is a string of characteristic polynomial,
	which is in the first column of outputs of tinymt32dc.
	</dd>
    </dl>
<pre>
void tinymt32_jump_by_polynomial(tinymt32_t *tiny,
				 f2_polynomial * jump_poly);
</pre>
    <dl>
      <dt>
	This function changes the internal state of tinymt32 to
	some steps froward using <b>jump_poly</b>.
	<b>jump_poly</b> must be calculated
	using the characteristic polynomial of <b>tiny</b>
	before this function is called.
	This function is faster than calculate_jump_polynomial.
      </dt>
      <dd><b>tiny</b> is a structure of type tinymt32_t.
	<b>tiny</b> must be initialized.
	<b>tiny</b> is overwritten by new jumped state.
      </dd>
    </dl>

    <h3>Sample program</h3>
    <p>Here is a sample program <a href="sample.c">sample.c</a></p>
  </body>
</html>