title: Why 1103515245 is used in rand?
body: <p>I'm talking about <a href="http://pubs.opengroup.org/onlinepubs/009695399/functions/rand.html">this</a> surprisingly simple implementation of <code>rand()</code> from the C standard:  </p>
  
  <pre><code>static unsigned long int next = 1;
  
  int rand(void)  /* RAND_MAX assumed to be 32767. */
  {
      next = next * 1103515245 + 12345;
      return (unsigned)(next/65536) % 32768;
  }
  </code></pre>
  
  <p>From <a href="http://en.wikipedia.org/wiki/Linear_congruential_generator">this Wikipedia article</a> we know that the multiplier <code>a</code> (in above code <code>a = 1103515245</code>) should fulfill only 2 conditions:  </p>
  
  <ol>
  <li><code>a - 1</code> is divisible by all prime factors of <code>m</code>.<br>
  (In our case <code>m = 2^32</code>, size of the int, so <code>m</code> has only one prime factor = 2)   </li>
  <li><code>a - 1</code> is a multiple of 4 if <code>m</code> is a multiple of 4.<br>
  (32768 is multiple of 4, and 1103515244 too)</li>
  </ol>
  
  <p><strong>Why they have chosen such a strange, hard-to-remember, "man, I'm fed up with these random numbers, write whatever" number, like 1103515245?</strong>  </p>
  
  <p>Maybe there are some wise reasons, that this number is somehow better than the other?   </p>
  
  <p>For example, why don't set <code>a = 20000000001</code>? It's bigger, cool-looking and easier to remember.</p>