pasl1009.html

This is programing tutorial for people who wants to know programing in PASCAL.Pascal might be not th

   10, 11, 11, 11, 11, 11 ....<br>
   5, 2, 7, 4, 7, 4, 7, 4, 7, 4, ...<br>
   Well, needless to say, it's definitely not a random generator.</li>
<li>Incrementing sequence. It's known as Lattice problem, like this :<br>
   3, 4, 7, 6, 7, 10, 9, 10, 13, 12, 13, 16, ...<br>
   See ? It may seem random, but let's look at this arrangement :<br>
    3,  4,  7,<br>6,  7, 10,<br>9, 10, 13,<br>12, 13, 16, ...<br>
   Got what I mean ? It is the same sequence, but just adding all of them
   with three, then start over again. Again : It's not a random number !
</li></ol><p>
The  number of sequence before it started over again is called the <b>period</b>.</p>
<center><table border=2><tr><th>Sequence</th><th>Period</th></tr>
<tr><td>3, 4, 7, 3, 4, 7, 3, 4, 7, ...</td><td><center>3</center></td></tr>
<tr><td>10, 11, 11, 11, 11, ...</td><td><center>1</center></td></tr>
<tr><td>3, 9, 2, 6, 7, 3, 9, 2, 6, 7, ...</td><td><center>5</center></td></tr>
</table></center>
<p>To get a good random sequence is that it seems that the nevers reoccurs, it
is  simply generate new, erratic number. In order to make that 'illusion',
we must generate a sequence with a very very long period.</p><p>
The  period is closely related to m. The period never exceed m, so that  we
must give m a very big value, say 2,000,000,000. A good random number generator
has a random sequence with period of m.</p>
<p>Now, take a time, choose your a, c, and m. Here's a hint :<br>
let m be 2,147,483,647<br>
let c be 1<br>
let a be 16807<br>
This was from S.K. Park and L.W. Miller research in 1988.</p>
<p>It's quite good. Try it ! We've still get 2 problems more :</p><ol>
<li>Multiplication overflow.</li>
<li>Signed bit set.</li></ol><ol>
<li><b>Multiplication overflow.</b><br>
   We  could handle it by using mathematical method. Most of the times  you
   may  ignore the overflow. It will not have much effect on your  numbers.
   So, you may skip this if you want to. Yes, yes, I understand your reason
   why  we should care about this. But it seldom happens. The idea is  from
   multiplicative attitude :<br><pre>

             x * (a+b) = x * a + x * b
   </pre>
   Suppose n is a+b. You should divide n into 2 numbers right ? If you have
   a divisor (any number), called y, n could be easily divided into a and b
   which are :<br><pre>
             a = (n div y) * y
             b = n mod y
   </pre>
   Then we replace it with a and b :<br><pre>

             x * n = x * y * (n div y) + x * (n mod y)
   </pre>
   It's pretty tricky. You must choose y so that x * y * (n div y) will not
   overflow. So, what's the point ? We see that seed*a may cause  overflow.
   Hence, you must replace it into :<br><pre>

             seed * a = a * y * (seed div y) + a * (seed mod y)
   </pre>
   Yes,  but  you shall never implement this directly. We know that  it  is
   still cause an overflow. How can it be done ? We know that <tt>
   a * (seed mod y)</tt> will never cause overflow if <tt>a * y</tt> is always
   ways  less than maximum limit of the long integer. The maximum limit of
   long integer is 2,147,483,647, we call it <tt>MAX_LONGINT</tt>. To check whether
   the equation causes overflow, we do this :<br><pre>

             temp = MAX_LONGINT - a * (seed mod y)
   </pre>
   If temp is less than <tt>a * y * (seed div y)</tt> means that it WILL cause overflowing.
   So, you may wonder how it can be overcome. Suppose :<br><pre>

             z = a * (seed div y)
   </pre>
   Then, you may easily guess :<br><pre>

             (z - temp / y) * y
   </pre>
   Will not cause overflow. Yup, wait a minute Sherlock ! <tt>temp / y</tt>
   is a rational number, the compiler will complain ! How can we get rid of
   it ? We change the equation above to :<br><pre>

             (z - temp div y) * y - temp mod y
   </pre>
   Phew ! Pretty lengthy, huh ? So, how is the final equation like ?<br><pre>

      seed * a = (z - temp div y) * y - (temp mod y) + a * (seed mod y)
   </pre>
   OK  ! OK ! You are bored, so that how could we implement this into
   program ? Watch this :
<hr><pre>
function random (howbig : word) : word;
const
  a           = 16807;
  c           = 1;
  m           = 2147483647;
  y           = m div a;     { suppose to be 127773 }
  MAX_LONGINT = 2147483647;  { same as m }
var
  z, temp : longint;
begin
  z    := a * (seed div y);
  temp := MAX_LONGINT - a * (seed mod y);

  { seed := seed * a + c  }
  seed := (z - temp div y) * y - (temp mod y) + a * (seed mod y) + c;
  
  { set loopback for seed }
  if seed &lt; 0 then seed := seed + MAX_LONGINT;

  seed := seed mod m;

  myrandom := seed mod howbig;
end;
</pre><hr>
   That's it ! You may wonder what if for is. Well, it does tackle the second
   problem. Here is the explanation. You may just rip that  code  and
   never know what the inside.</li>
<li><b>Signed bit set.</b><br>
   In our talk just now, we assume that <tt>a * y * (seed div y)</tt> is always
   causing overflow. If it doesn't, means that :<br><pre>

              (z - temp div y) * y - (temp mod y)
   </pre>
   will always be negative. We don't want negative seed here since it  will
   be  catastrophic. Why is it called <b>SIGNED BIT SET</b> ? It is because to
   differ  a number from negative to positive, computer only use sign  bit.
   If  it is a negative, the sign bit set (on), when it is positive, it  is
   cleared (off).<br>
   So, how to cure this ? Easy, just add it with <tt>MAX_LONGINT</tt>, and we should
   have got rid of it. This will certainly clear off the sign bit.</li></ol>
<p>
This Lehmer's function is adequate for daily purposes. For scientific ones,
it  may  not be enough. Therefore, there is another method  called <b>Uniform
Random Deviates</b>, invented by Paul L'Ecuyer. We would not discuss it now,
since  it is quite complicated. But you know that the Lehmer's  above  will
have a period of 2,147,483,647. Uniform Random Deviates will create a period
of about 10<sup>8</sup> !! Quite a slam bang ! Even this period is not enough  for
scientific uses ! However, combining both will result a period about  2,3 x
10<sup>18</sup> ! It should be adequate for just any purposes.</p>
<p>How can we implement random numbers to generate :</p><ol>
<li><b>Fraction from 0 to 1 ?</b><br>
Suppose you have a function of <tt>srand</tt>, that generates such fraction :<hr><pre>
       function srand:real;
       { everything is just the same as myrandom function except
         myrandom := seed mod howbig; is changed into : }

       myrandom:= seed / MAX_LONGINT;
</pre><hr></li>
<li><b>Integers from a to b ?</b><br>
Suppose you have a function of <tt>rand</tt>, that generates such integer :<hr><pre>
       function rand(lower, upper : word): word;
       { everything is just the same as myrandom function except
         myrandom := seed mod howbig; is changed into : }

       myrandom:= lower + (seed mod (upper - lower + 1));
</pre><hr></li></ol><p>
Actually,  there  are a lot more to discuss : Random table,  Random  number
with no duplication, scrambling arrays, etc. But I think you had enough for
this time. So, adios amigos, my friend ! See ya on the <a href="pasq1009.html">
quiz</a> !</p>
<hr><p><B><H3>Where to go ?</H3></B><p>
<A HREF="../news.html">Back to main page</A><BR>
<A HREF="pasles01.html">Back to Pascal Tutorial Lesson 1 contents</A><BR>
<A HREF="pasq1009.html">To the quiz</A><BR>
<A HREF="pasl1008.html">Back to Chapter 9</A> about records<BR>
<A HREF="pasl1010.html">To Chapter 11</A> about sets<BR>
<A HREF="../mylink.html">My page of programming link</A><BR>
<A HREF="../faq.html">Contact me here</A>
<hr><P Class="cpy">By : Roby Joehanes, &copy; 1997, 2000</P>
</BODY></HTML>