The Java Specialists' Newsletter
Issue 19820120213
Category:
Language
Java version: Java 7 Pushing the Limits in Java's Randomby Dr. Heinz M. Kabutz and Dr. Wolfgang LaunAbstract: What is the largest double that could in theory be produced by Math.random()? In this newsletter, we look at ways to calculate this based on the 48bit random generator available in standard Java. We also prove why in a singlethreaded program, (int)(Random.nextDouble() + 1) can never be rounded up to 2.
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.
If you are looking for a great Java book to read, try
preordering The WellGrounded Java
Developer, by Ben Evans and Martijn Verburg. A book
review will be published shortly.
We switched to a new email delivery system, which I believe
will have a better success rate at getting this newsletter into
your inbox. Our new system also allows new subscribers to
specify their country. It is with great pleasure that I
welcome: Djessy Menard from Haiti, Halle Johnson from
Antigua and Barbuda, and Shaik Abdul Gafoor from Qatar. This
brings the number of known subscriber
countries to 124.
NEW:
Please see our new "Extreme Java" course, combining
concurrency, a little bit of performance and Java 8.
Extreme Java  Concurrency & Performance for Java 8.
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:
public double nextDouble() {
return (((long)(next(26)) << 27) + next(27))
/ (double)(1L << 53);
}
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((((1L << 53)  1)) / (double) (1L << 53));
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:
public class CloseToOne {
public static double makeDouble(long first, long second) {
return ((first << 27) + second) / (double) (1L << 53);
}
public static void main(String[] args) {
long first = (1 << 26)  1;
long second = (1 << 27)  1;
System.out.println(makeDouble(first, second));
System.out.println((int)(makeDouble(first, second)+1));
second;
System.out.println(makeDouble(first, second));
System.out.println((int)(makeDouble(first, second)+1));
}
}
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.
public class CloseToOne2 {
public static void main(String[] args) {
double d = 0.999999993;
System.out.println("d = " + d);
int i = (int) (1 + d);
System.out.println("i = " + i);
int j = (int) (100_000_000 + d);
System.out.println("j = " + 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 48bit 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 48bit 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 48bit 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():
/**
* @author Wolfgang Laun
*/
public class FindRandom {
private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48)  1;
public static double makeDouble(long pre, long post) {
return ((pre << 27) + post) / (double) (1L << 53);
}
private static long setbits(int len, int off) {
long res = (1L << len)  1;
return res << off;
}
/**
* 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)) << 27 + (ms(ri2,27))
* This is divided by (double)(1L << 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
* 53bit integer used for a double random's mantissa.
*/
private static void findMaxDouble() {
long ones = setbits(26, 22);
System.out.println("ones: " + Long.toHexString(ones));
long maxpost = setbits(22, 0);
System.out.println("maxpost: " + Long.toHexString(maxpost));
long maxintw = 0;
for (long post = 0; post <= maxpost; post++) {
long oldseed = ones + post;
long nextseed = (oldseed * multiplier + addend) & mask;
long intw = nextseed >>> (48  27);
if (intw > maxintw) {
maxintw = intw;
}
}
System.out.println("maxintw: " + Long.toHexString(maxintw));
long b26 = setbits(26, 0);
System.out.println("b26: " + Long.toHexString(b26));
double d = makeDouble(b26, maxintw);
System.out.println("max. double: " +
Double.toHexString(d) + " = " + d);
}
private static void findMinDouble() {
long b26 = 0L;
long zeroes = 0L;
long maxpost = setbits(22, 0);
long minintw = 0x7fffffffffffffffL;
for (int post = 0; post < maxpost; post++) {
long oldseed = zeroes + post;
long nextseed = (oldseed * multiplier + addend) & mask;
long intw = nextseed >>> (48  27);
if (intw < minintw) {
minintw = intw;
}
}
System.out.println("minintw: " + minintw);
double d = makeDouble(b26, minintw);
System.out.println("min. double: " +
Double.toHexString(d) + " = " + d);
}
public static void main(String[] args) {
findMaxDouble();
double belowOne = Math.nextAfter(1.0, 0.0);
System.out.println("Biggest double below 1.0 is: " +
Double.toHexString(belowOne) + " = " + 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:
public double nextDouble() {
return (((long)(next(26)) << 27) + next(27))
/ (double)(1L << 53);
}
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.
import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.util.concurrent.*;
/**
* @author Heinz Kabutz
*/
public class Blinker extends JFrame {
public Blinker() {
setLayout(new GridLayout(0, 4));
}
private void addButtons(int buttons, final int blinks) {
final Phaser phaser = new Phaser(buttons) {
protected boolean onAdvance(int phase, int parties) {
return phase >= blinks  1  parties == 0;
}
};
for (int i = 0; i < buttons; i++) {
final JComponent comp = new JButton("Button " + i);
comp.setOpaque(true);
final Color defaultColor = comp.getBackground();
changeColor(comp, defaultColor);
add(comp);
new Thread() {
public void run() {
Random rand = ThreadLocalRandom.current();
try {
Thread.sleep(1000);
do {
Color newColor = new Color(rand.nextInt());
changeColor(comp, newColor);
Thread.sleep(500 + rand.nextInt(3000));
changeColor(comp, defaultColor);
Toolkit.getDefaultToolkit().beep();
Thread.sleep(2000);
phaser.arriveAndAwaitAdvance();
} while (!phaser.isTerminated());
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}.start();
}
}
private void changeColor(
final JComponent comp, final Color color) {
SwingUtilities.invokeLater(new Runnable() {
public void run() {
comp.setBackground(color);
invalidate();
repaint();
}
});
}
public static void main(String[] args) {
SwingUtilities.invokeLater(new Runnable() {
public void run() {
Blinker blinker = new Blinker();
blinker.addButtons(20, 3);
blinker.pack();
blinker.setVisible(true);
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:
public class MathTeaser {
public static void main(String[] args) {
final Random random = new Random();
Thread seeder = new Thread() {
public void run() {
while(true) {
random.setSeed(51102269); // causes 2^261 as next(26)
random.setSeed(223209395); // causes 2^271 as next(27)
}
}
};
seeder.setDaemon(true);
seeder.start();
while(true) {
double num = random.nextDouble();
if ((int)(num + 1) == 2) {
System.out.println("Yes, random.nextDouble() can: " + num);
break;
}
}
}
}
Thanks to Dr. Wolfgang Laun for the fascinating discussions
of how Random really works and for your contribution in this
newsletter.
Kind regards
Heinz
Language Articles
Related Java Course
