Pushing the Limits in Java's Random

Posted by kabutz on February 14, 2012 at 3:46 AM PST

Welcome to the 198th issue of The Java(tm) Specialists' Newsletter sent to you from Chania in Greece. My readers in colder climates frequently get annoyed when I tell them that "life's a beach". They imagine us having constant sun here. It's not true. We do sometimes have torrential rains and cold weather. It even snows here occasionally. In fact, the delivery truck for my heating oil arrived as I was writing this.

This article was originally published in The Java Specialists' Newsletter.

Pushing the Limits in Java's Random

My previous newsletter caused quite a stir. I saw lots of wrong answers and some excellent explanations. Quite a few thought that Math.random() did indeed sometimes return 1.0. It does not, but the value is sometimes close enough to 1.0 that we lose precision in the rounding.

Here is what the nextDouble() calculation looks like in java.util.Random:

<b><font color="#000080">public</font></b> <b><font color="#000080">double</font></b> nextDouble() {
  <b><font color="#000080">return</font></b> (((<b><font color="#000080">long</font></b>)(next(<font color="#0000ff">26</font>)) &lt;&lt; <font color="#0000ff">27</font>) + next(<font color="#0000ff">27</font>))
    / (<b><font color="#000080">double</font></b>)(<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">53</font>);
}

One of our most thorough readers, Dr. Wolfgang Laun, went on a voyage of discovery to find out what the highest number was that could possibly be returned by Math.random(). This newsletter is a summary of his findings, plus some other tidbits that I discovered. Dr. Laun lives in Vienna in Austria and works for Thales as their local software guru. I've had the pleasure of meeting him personally and been invited for dinner at his house. He is probably the most intelligent human being I have met. And he also has a great sense of humour and a keen curiosity of how the world works. I am honoured to count him as a friend.

The first question that Wolfgang tried to answer is: Can (int)(Math.random() + 1) ever return 2? I thought it could. The calculation for producing the double is to make up a 53 bit number and to then divide it by 2^53. This means that the maximum possible number would be ((2^53)-1)/(2^53), or 0.9999999999999999. You can calculate this easily:

System.out.println((((<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">53</font>) - <font color="#0000ff">1</font>)) / (<b><font color="#000080">double</font></b>) (<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">53</font>));

If we use the standard Random calculation as shown in makeDouble(), if we add 1 and cast it to an int, the result will be 2. For example:

<b><font color="#000080">public</font></b> <b><font color="#000080">class</font></b> CloseToOne {
  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">double</font></b> makeDouble(<b><font color="#000080">long</font></b> first, <b><font color="#000080">long</font></b> second) {
    <b><font color="#000080">return</font></b> ((first &lt;&lt; <font color="#0000ff">27</font>) + second) / (<b><font color="#000080">double</font></b>) (<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">53</font>);
  }

  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> main(String[] args) {
    <b><font color="#000080">long</font></b> first = (<font color="#0000ff">1</font> &lt;&lt; <font color="#0000ff">26</font>) - <font color="#0000ff">1</font>;
    <b><font color="#000080">long</font></b> second = (<font color="#0000ff">1</font> &lt;&lt; <font color="#0000ff">27</font>) - <font color="#0000ff">1</font>;

    System.out.println(makeDouble(first, second));
    System.out.println((int)(makeDouble(first, second)+<font color="#0000ff">1</font>));

    second--;
    System.out.println(makeDouble(first, second));
    System.out.println((int)(makeDouble(first, second)+<font color="#0000ff">1</font>));
  }
}

In our previous newsletter, "meaning" was sometimes incremented by two, when Math.random was close enough to 1 and "meaning" was large enough. For example, if "meaning" is 100_000_000, we don't need to be as close to 1 as if "meaning" is 1.

<b><font color="#000080">public</font></b> <b><font color="#000080">class</font></b> CloseToOne2 {
  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> main(String[] args) {
    <b><font color="#000080">double</font></b> d = <font color="#0000ff">0.999999993</font>;
    System.out.println(<b><font color="#E1691A">&quot;d = &quot;</font></b> + d);
    <b><font color="#000080">int</font></b> i = (int) (<font color="#0000ff">1</font> + d);
    System.out.println(<b><font color="#E1691A">&quot;i = &quot;</font></b> + i);
    <b><font color="#000080">int</font></b> j = (int) (<font color="#0000ff">100_000_000</font> + d);
    System.out.println(<b><font color="#E1691A">&quot;j = &quot;</font></b> + j);
  }
}

The question is, can Math.random() return a significantly large number that is less than 1.0, but that makes (int)(Math.random() + 1) return 2? I thought so, but Wolfgang proved me wrong.

Java's random calculation is based on the 48-bit seed, linear congruential formula described in The Art of Computer Programming, Volume 2 by Donald Knuth in Section 3.2.1. This is also described on Wikipedia.

The point to note is that it is based on a 48-bit seed. In order for (int)(Math.random() + 1) to be 2, all the bits would have to be set on the left. If it is just one less, then the double would equal 0.9999999999999998 and this would not round up to 2.

Since the next random value is based on the current value, all we would need to check is whether there exists a 48-bit number with the lower 26 bits set, such that the next number has the lower 27 bits set. If we find such a number, then we can conclude that at least in theory, it is possible for Math.random() to return 0.9999999999999999. We would still need to establish for what random seed we could get this number. If we did not find such a number, then we could conclude that it was not possible.

Wolfgang wrote the code to calculate the largest number that could be returned by Math.random():

<i><font color="808080">/**  * @author Wolfgang Laun  */</font></i>

<b><font color="#000080">public</font></b> <b><font color="#000080">class</font></b> FindRandom {
  <b><font color="#000080">private</font></b> <b><font color="#000080">final</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">long</font></b> multiplier = <font color="#0000ff">0x5DEECE66DL</font>;
  <b><font color="#000080">private</font></b> <b><font color="#000080">final</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">long</font></b> addend = <font color="#0000ff">0xBL</font>;
  <b><font color="#000080">private</font></b> <b><font color="#000080">final</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">long</font></b> mask = (<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">48</font>) - <font color="#0000ff">1</font>;

  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">double</font></b> makeDouble(<b><font color="#000080">long</font></b> pre, <b><font color="#000080">long</font></b> post) {
    <b><font color="#000080">return</font></b> ((pre &lt;&lt; <font color="#0000ff">27</font>) + post) / (<b><font color="#000080">double</font></b>) (<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">53</font>);
  }

  <b><font color="#000080">private</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">long</font></b> setbits(<b><font color="#000080">int</font></b> len, <b><font color="#000080">int</font></b> off) {
    <b><font color="#000080">long</font></b> res = (<font color="#0000ff">1L</font> &lt;&lt; len) - <font color="#0000ff">1</font>;
    <b><font color="#000080">return</font></b> res &lt;&lt; off;
  }

  <i><font color="808080">/**     * A random double is composed from two successive random     * integers.     * The most significant 26 bits of the first one are taken and     * concatenated with the most significant 27 bits of the second     * one.     * (ms(ri1,26)) &lt;&lt; 27 + (ms(ri2,27))     * This is divided by (double)(1L &lt;&lt; 53) to obtain a     * result in [0.0, 1.0).     * To find the maximum random double, we assume that     * (ms(ri1,m26))     * is a maximum (all 1b) and vary the remaining 22 bits from     * 0 to m22, inclusive. Assuming this to be ri1, we perform the     * calculation according to Random.next() to obtain is     * successor, our ri2. The maximum of the most significant 27     * bits of all ri2 would then be the second part of the maximum     * 53-bit integer used for a double random's mantissa.    */</font></i>
  <b><font color="#000080">private</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> findMaxDouble() {
    <b><font color="#000080">long</font></b> ones = setbits(<font color="#0000ff">26</font>, <font color="#0000ff">22</font>);
    System.out.println(<b><font color="#E1691A">&quot;ones: &quot;</font></b> + Long.toHexString(ones));
    <b><font color="#000080">long</font></b> maxpost = setbits(<font color="#0000ff">22</font>, <font color="#0000ff">0</font>);
    System.out.println(<b><font color="#E1691A">&quot;maxpost: &quot;</font></b> + Long.toHexString(maxpost));
    <b><font color="#000080">long</font></b> maxintw = <font color="#0000ff">0</font>;
    <b><font color="#000080">for</font></b> (<b><font color="#000080">long</font></b> post = <font color="#0000ff">0</font>; post &lt;= maxpost; post++) {
      <b><font color="#000080">long</font></b> oldseed = ones + post;
      <b><font color="#000080">long</font></b> nextseed = (oldseed * multiplier + addend) &amp; mask;
      <b><font color="#000080">long</font></b> intw = nextseed &gt;&gt;&gt; (<font color="#0000ff">48</font> - <font color="#0000ff">27</font>);
      <b><font color="#000080">if</font></b> (intw &gt; maxintw) {
        maxintw = intw;
      }
    }
    System.out.println(<b><font color="#E1691A">&quot;maxintw: &quot;</font></b> + Long.toHexString(maxintw));
    <b><font color="#000080">long</font></b> b26 = setbits(<font color="#0000ff">26</font>, <font color="#0000ff">0</font>);
    System.out.println(<b><font color="#E1691A">&quot;b26: &quot;</font></b> + Long.toHexString(b26));
    <b><font color="#000080">double</font></b> d = makeDouble(b26, maxintw);
    System.out.println(<b><font color="#E1691A">&quot;max. double: &quot;</font></b> +
        Double.toHexString(d) + <b><font color="#E1691A">&quot; = &quot;</font></b> + d);
  }

  <b><font color="#000080">private</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> findMinDouble() {
    <b><font color="#000080">long</font></b> b26 = <font color="#0000ff">0L</font>;
    <b><font color="#000080">long</font></b> zeroes = <font color="#0000ff">0L</font>;
    <b><font color="#000080">long</font></b> maxpost = setbits(<font color="#0000ff">22</font>, <font color="#0000ff">0</font>);
    <b><font color="#000080">long</font></b> minintw = <font color="#0000ff">0x7fffffffffffffffL</font>;
    <b><font color="#000080">for</font></b> (<b><font color="#000080">int</font></b> post = <font color="#0000ff">0</font>; post &lt; maxpost; post++) {
      <b><font color="#000080">long</font></b> oldseed = zeroes + post;
      <b><font color="#000080">long</font></b> nextseed = (oldseed * multiplier + addend) &amp; mask;
      <b><font color="#000080">long</font></b> intw = nextseed &gt;&gt;&gt; (<font color="#0000ff">48</font> - <font color="#0000ff">27</font>);
      <b><font color="#000080">if</font></b> (intw &lt; minintw) {
        minintw = intw;
      }
    }
    System.out.println(<b><font color="#E1691A">&quot;minintw: &quot;</font></b> + minintw);
    <b><font color="#000080">double</font></b> d = makeDouble(b26, minintw);
    System.out.println(<b><font color="#E1691A">&quot;min. double: &quot;</font></b> +
        Double.toHexString(d) + <b><font color="#E1691A">&quot; = &quot;</font></b> + d);
  }

  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> main(String[] args) {
    findMaxDouble();
    <b><font color="#000080">double</font></b> belowOne = Math.nextAfter(<font color="#0000ff">1.0</font>, <font color="#0000ff">0.0</font>);
    System.out.println(<b><font color="#E1691A">&quot;Biggest double below 1.0 is: &quot;</font></b> +
        Double.toHexString(belowOne) + <b><font color="#E1691A">&quot; = &quot;</font></b> + belowOne);
    findMinDouble();
  }
}

From this, we can calculate that the highest number that can be returned by Math.random() is 0.999999999999996, whereas the highest double less than 1.0 is 0.9999999999999999, a difference of .0000000000000039.

Concurrency

We could stop here, were it not for concurrency. However, the Math.random() method delegates to a shared mutable instance of Random. Since they use atomics, rather than locking, it is impossible for the compound nextDouble() method to be atomic. Thus it is possible that in between the two calls to next(27) and next(26), other threads call next(). Remember the code for Random.nextDouble() from earlier:

<b><font color="#000080">public</font></b> <b><font color="#000080">double</font></b> nextDouble() {
  <b><font color="#000080">return</font></b> (((<b><font color="#000080">long</font></b>)(next(<font color="#0000ff">26</font>)) &lt;&lt; <font color="#0000ff">27</font>) + next(<font color="#0000ff">27</font>))
    / (<b><font color="#000080">double</font></b>)(<font color="#0000ff">1L</font> &lt;&lt; <font color="#0000ff">53</font>);
}

In theory, if you had thousands of threads calling Math.random() at the same time, your thread could be swapped out for long enough, so that (int)(Math.random() + 1) could return 2. The probability of this happening might be greater than zero, but it is infinitesimally small. For example, in my experiments I did find a value of next(26) for which, if it was swapped out long enough and other threads had called next(27) 105 times, next(27) would return a number with all bits set. As Wolfgang told me, I'm rapidly entering into the realms of the metaphysical here.

Java 7 ThreadLocalRandom

As of Java 7, we should never again use Math.random(). Java 7 gives us a new ThreadLocalRandom class that has one unshared Random instance per thread. Since it is an unshared object, they do not need to have any synchronization to prevent data races. As a result it is blazingly fast.

We can use it like this: ThreadLocalRandom.current().nextInt(3000);

In this example, we construct 20 buttons and let them change color at a random interval using ThreadLocalRandom. I will go over this code again in another newsletter, as it also demonstrates the new Java 7 Phaser class.

<b><font color="#000080">import</font></b> javax.swing.*;
<b><font color="#000080">import</font></b> java.awt.*;
<b><font color="#000080">import</font></b> java.util.*;
<b><font color="#000080">import</font></b> java.util.concurrent.*;

<i><font color="808080">/**  * @author Heinz Kabutz  */</font></i>
<b><font color="#000080">public</font></b> <b><font color="#000080">class</font></b> Blinker <b><font color="#000080">extends</font></b> JFrame {
  <b><font color="#000080">public</font></b> Blinker() {
    setLayout(<b><font color="#000080">new</font></b> GridLayout(<font color="#0000ff">0</font>, <font color="#0000ff">4</font>));
  }

  <b><font color="#000080">private</font></b> <b><font color="#000080">void</font></b> addButtons(<b><font color="#000080">int</font></b> buttons, <b><font color="#000080">final</font></b> <b><font color="#000080">int</font></b> blinks) {
    <b><font color="#000080">final</font></b> Phaser phaser = <b><font color="#000080">new</font></b> Phaser(buttons) {
      <b><font color="#000080">protected</font></b> <b><font color="#000080">boolean</font></b> onAdvance(<b><font color="#000080">int</font></b> phase, <b><font color="#000080">int</font></b> parties) {
        <b><font color="#000080">return</font></b> phase &gt;= blinks - <font color="#0000ff">1</font> || parties == <font color="#0000ff">0</font>;
      }
    };
    <b><font color="#000080">for</font></b> (<b><font color="#000080">int</font></b> i = <font color="#0000ff">0</font>; i &lt; buttons; i++) {
      <b><font color="#000080">final</font></b> JComponent comp = <b><font color="#000080">new</font></b> JButton(<b><font color="#E1691A">&quot;Button &quot;</font></b> + i);
      comp.setOpaque(<b><font color="#000080">true</font></b>);
      <b><font color="#000080">final</font></b> Color defaultColor = comp.getBackground();
      changeColor(comp, defaultColor);
      add(comp);
      <b><font color="#000080">new</font></b> Thread() {
        <b><font color="#000080">public</font></b> <b><font color="#000080">void</font></b> run() {
          Random rand = ThreadLocalRandom.current();
          <b><font color="#000080">try</font></b> {
            Thread.sleep(<font color="#0000ff">1000</font>);
            <b><font color="#000080">do</font></b> {
              Color newColor = <b><font color="#000080">new</font></b> Color(rand.nextInt());
              changeColor(comp, newColor);
              Thread.sleep(<font color="#0000ff">500</font> + rand.nextInt(<font color="#0000ff">3000</font>));
              changeColor(comp, defaultColor);
              Toolkit.getDefaultToolkit().beep();
              Thread.sleep(<font color="#0000ff">2000</font>);
              phaser.arriveAndAwaitAdvance();
            } <b><font color="#000080">while</font></b> (!phaser.isTerminated());
          } <b><font color="#000080">catch</font></b> (InterruptedException e) {
            Thread.currentThread().interrupt();
          }
        }
      }.start();
    }
  }

  <b><font color="#000080">private</font></b> <b><font color="#000080">void</font></b> changeColor(
      <b><font color="#000080">final</font></b> JComponent comp, <b><font color="#000080">final</font></b> Color color) {
    SwingUtilities.invokeLater(<b><font color="#000080">new</font></b> Runnable() {
      <b><font color="#000080">public</font></b> <b><font color="#000080">void</font></b> run() {
        comp.setBackground(color);
        invalidate();
        repaint();
      }
    });
  }

  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> main(String[] args) {
    SwingUtilities.invokeLater(<b><font color="#000080">new</font></b> Runnable() {
      <b><font color="#000080">public</font></b> <b><font color="#000080">void</font></b> run() {
        Blinker blinker = <b><font color="#000080">new</font></b> Blinker();
        blinker.addButtons(<font color="#0000ff">20</font>, <font color="#0000ff">3</font>);
        blinker.pack();
        blinker.setVisible(<b><font color="#000080">true</font></b>);
        blinker.setDefaultCloseOperation(
            WindowConstants.EXIT_ON_CLOSE);
      }
    });
  }
}

If you run the Blinker with a version of Java 7 older than 1.7.0_02, you will notice that all the colors and delays are always the same. This is due to a bug in the constructor of java.util.Random, which failed to set the seed correctly on the subclass. Time to upgrade to the latest version of Java 7. Note that if you are using Mac OS X Snow Leopard or Leopard, the Mac OS X Port installer will tell you that you need to upgrade to Lion. Instead, I used Pacifist to extract the DMG file. I am not ready to install Lion on my work machines yet.

(int)(Math.random() * some_int)

A common code idiom is to multiply the result of Math.random() with some integer value. There are several reasons not to do that anymore. First off, Math.random() is using a shared mutable instance of Random, thus it needs to be synchronized. It does use atomics to eliminate locking, but with lots of threads calling Math.random(), you might still need to redo your work several times until you emerge as the winner.

The second reason is that Math.random() calls nextDouble(), which as we have seen, will call next(bits) twice.

The third reason is that nextDouble() * int is more biased. We will get a fairer distribution if we call nextInt(upto).

One Last Thing

Concurrency allows us to do some strange things. For example, we can set the seed on a shared mutable Random instance so that eventually, (int)(random.nextDouble() + 1) will return 2. Here is the code:

<b><font color="#000080">public</font></b> <b><font color="#000080">class</font></b> MathTeaser {
  <b><font color="#000080">public</font></b> <b><font color="#000080">static</font></b> <b><font color="#000080">void</font></b> main(String[] args) {
    <b><font color="#000080">final</font></b> Random random = <b><font color="#000080">new</font></b> Random();
    Thread seeder = <b><font color="#000080">new</font></b> Thread() {
      <b><font color="#000080">public</font></b> <b><font color="#000080">void</font></b> run() {
        <b><font color="#000080">while</font></b>(<b><font color="#000080">true</font></b>) {
          random.setSeed(<font color="#0000ff">51102269</font>); <i><font color="808080">// causes 2^26-1 as next(26)</font></i>
          random.setSeed(<font color="#0000ff">223209395</font>); <i><font color="808080">// causes 2^27-1 as next(27)</font></i>
        }
      }
    };
    seeder.setDaemon(<b><font color="#000080">true</font></b>);
    seeder.start();

    <b><font color="#000080">while</font></b>(<b><font color="#000080">true</font></b>) {
      <b><font color="#000080">double</font></b> num = random.nextDouble();
      <b><font color="#000080">if</font></b> ((<b><font color="#000080">int</font></b>)(num + <font color="#0000ff">1</font>) == <font color="#0000ff">2</font>) {
        System.out.println(<b><font color="#E1691A">&quot;Yes, random.nextDouble() can: &quot;</font></b> + num);
        <b><font color="#000080">break</font></b>;
      }
    }
  }
}

Thanks to Dr. Wolfgang Laun for the fascinating discussions of how Random really works and for your contribution in this newsletter.

Kind regards

Heinz

Main Menu

Heinz Kabutz

Pushing the Limits in Java's Random