139

Edit: So basically what I'm trying to write is a 1 bit hash for double.

I want to map a double to true or false with a 50/50 chance. For that I wrote code that picks some random numbers (just as an example, I want to use this on data with regularities and still get a 50/50 result), checks their last bit and increments y if it is 1, or n if it is 0.

However, this code constantly results in 25% y and 75% n. Why is it not 50/50? And why such a weird, but straight-forward (1/3) distribution?

public class DoubleToBoolean {
    @Test
    public void test() {

        int y = 0;
        int n = 0;
        Random r = new Random();
        for (int i = 0; i < 1000000; i++) {
            double randomValue = r.nextDouble();
            long lastBit = Double.doubleToLongBits(randomValue) & 1;
            if (lastBit == 1) {
                y++;
            } else {
                n++;
            }
        }
        System.out.println(y + " " + n);
    }
}

Example output:

250167 749833
numaroth
  • 1,295
  • 4
  • 25
  • 36
gvlasov
  • 18,638
  • 21
  • 74
  • 110
  • 43
    I'm really hoping the answer is something fascinating about random generation of floating-point variates, rather than "LCG has low entropy in the low bits". – Sneftel Dec 23 '14 at 18:00
  • 4
    I am very curious, what is the purpose of a "1 bit hash for double"? I seriously can't think of any legitimate application of such a requirement. – corsiKa Dec 23 '14 at 22:29
  • 3
    @corsiKa In geometry computations there are often two cases we're looking for to choose from two possible answers (e.g. is point to the left or to the right of the line?), and sometimes it introduces the third, degenerate case (point is right on the line), but you only have two available answers, so you have to pseudorandomly choose one of the available answers in that case. The best way I could think of is to take a 1 bit hash of one of the given double values (remember, those are geometry computations, so there are doubles all over the place). – gvlasov Dec 23 '14 at 22:47
  • 2
    @corsiKa (comment divided into two because it is too long) We could start at something simpler like `doubleValue % 1 > 0.5`, but that would be too coarse-grained since it can introduce visible regularities in some cases (all the values are within range of length 1). If that's too coarse-grained, then should we probably try smaller ranges, like `doubleValue % 1e-10 > 0.5e-10`? Well, yes. And taking just the last bit as a hash of a `double` is what happens when you follow this approach till the end, with the least possible modulo. – gvlasov Dec 23 '14 at 22:48
  • So if I understand @Harold's answer correctly, you could get the uniform hash that you want by simply changing the end of line 10 from `& 1;` to `& 3;`, correct? – kmote Dec 31 '14 at 00:07
  • @kmote: No, it wouldn't. As [suggested by rici](http://stackoverflow.com/posts/comments/43705716) and [proven by harold](http://stackoverflow.com/posts/comments/43705764), you'd have to multiply the number by 2^53 and then check whether the result is an even number. – Alex Essilfie Dec 31 '14 at 07:32
  • 1
    @kmote then you'd still have the heavily biased least significant bit, and the other bit doesn't compensate for it - in fact it is also biased towards zero (but less so), for exactly the same reason. So the distribution would be about 50, 12.5, 25, 12.5. `(lastbit & 3) == 0` would work though, odd as it is. – harold Dec 31 '14 at 10:35
  • @harold: my bad. I actually meant to say `& 2;` (or any other power of 2). Couldn't we expect all of the other bits (besides the final biased one) to be uniformly distributed? – kmote Dec 31 '14 at 15:18
  • 1
    @kmote no because the same effect applies to them - if you roll lower than a certain number for the 53bit random `long`, then that bit will be guaranteed 0 (and otherwise 50/50). So they're zero with probability 75%, 62.5%, 56.25%, 53.125% etc – harold Dec 31 '14 at 15:23

3 Answers3

164

Because nextDouble works like this: (source)

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x) makes x random bits.

Now why does this matter? Because about half the numbers generated by the first part (before the division) are less than 1L << 52, and therefore their significand doesn't entirely fill the 53 bits that it could fill, meaning the least significant bit of the significand is always zero for those.

Because of the amount of attention this is receiving, here's some extra explanation of what a double in Java (and many other languages) really looks like and why it mattered in this question.

Basically, a double looks like this: (source)

double layout

A very important detail not visible in this picture is that numbers are "normalized"1 such that the 53 bit fraction starts with a 1 (by choosing the exponent such that it is so), that 1 is then omitted. That is why the picture shows 52 bits for the fraction (significand) but there are effectively 53 bits in it.

The normalization means that if in the code for nextDouble the 53rd bit is set, that bit is the implicit leading 1 and it goes away, and the other 52 bits are copied literally to the significand of the resulting double. If that bit is not set however, the remaining bits must be shifted left until it becomes set.

On average, half the generated numbers fall into the case where the significand was not shifted left at all (and about half those have a 0 as their least significant bit), and the other half is shifted by at least 1 (or is just completely zero) so their least significant bit is always 0.

1: not always, clearly it cannot be done for zero, which has no highest 1. These numbers are called denormal or subnormal numbers, see wikipedia:denormal number.

harold
  • 61,398
  • 6
  • 86
  • 164
  • 16
    Hooray! Just what I was hoping for. – Sneftel Dec 23 '14 at 18:06
  • This is very cool. Just curious, how did you come by this knowledge? And would you happen to know why this is the best way to generate random doubles? Again, very cool +1 – Matt Dec 23 '14 at 18:07
  • 3
    @Matt Presumably it's a speed optimization. The alternative would be to generate the exponent with a geometric distribution, and then the mantissa separately. – Sneftel Dec 23 '14 at 18:09
  • Just where on earth do you learn all this : ( Totally off-topic but if you can share books where I can learn about this kind of specific, almost "trivia" topics, I'd appreciate any reference! –  Dec 23 '14 at 18:10
  • 7
    @Matt: Define "best." `random.nextDouble()` is typically the "best" way for what it's intended for, but most people are not trying to produce a 1-bit hash from their random double. Are you looking for uniform distribution, resistance to cryptanalysis, or what? – StriplingWarrior Dec 23 '14 at 18:10
  • @Sneftel Yeah, I guess that makes sense when I think about it. I just wouldn't have gotten there quickly without seeing the answer first. Thanks! – Matt Dec 23 '14 at 18:11
  • 1
    This answer suggests that if OP had multiplied the random number by 2^53 and checked whether the resulting integer was odd, there would have been a 50/50 distribution. – rici Dec 25 '14 at 01:21
  • 1
    @harold, yeah. I guess OP didn't ask "...and how do I fix it", but I can't help thinking that it would be a useful addition for anyone else with a similar need. – rici Dec 25 '14 at 01:41
  • 1
    Great answer! Sort of off-topic, is there a reason the first part of the division is not just `next(53)`? I'm guessing `next(x)` only works with values up to 48 or something, by glancing at the source, but that is not specified in the doc. – The111 Dec 25 '14 at 04:15
  • 4
    @The111 it says [here](http://docs.oracle.com/javase/7/docs/api/java/util/Random.html#next(int)) that `next` must return an `int`, so it can only have up to 32 bits anyway – harold Dec 25 '14 at 12:18
  • "What a `double` looks like in Java (and many other languages)": it's actually what a 64-bit float looks like in most processors these days. It's not really a "language" thing. – ajb Dec 26 '14 at 01:10
  • @ajb it *is* a language thing. Languages could easily specify a completely different format. That would be really inconvenient, but they totally could. What the processor supports doesn't matter to what you see happening at the language level. Some languages merely *allow* this format, and then it's an implementation thing (but still not a processor thing!) – harold Dec 26 '14 at 10:53
48

From the docs:

The method nextDouble is implemented by class Random as if by:

public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

But it also states the following (emphasis mine):

[In early versions of Java, the result was incorrectly calculated as:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

This might seem to be equivalent, if not better, but in fact it introduced a large nonuniformity because of the bias in the rounding of floating-point numbers: it was three times as likely that the low-order bit of the significand would be 0 than that it would be 1! This nonuniformity probably doesn't matter much in practice, but we strive for perfection.]

This note has been there since Java 5 at least (docs for Java <= 1.4 are behind a loginwall, too lazy to check). This is interesting, because the problem apparently still exists even in Java 8. Perhaps the "fixed" version was never tested?

Thomas
  • 174,939
  • 50
  • 355
  • 478
  • 4
    Strange. I just reproduced this on Java 8. – aioobe Dec 23 '14 at 18:11
  • I'm using Java 8 as well. – gvlasov Dec 23 '14 at 18:12
  • 1
    Now that's interesting, because I just argued that the bias still applies to the new method. Am I wrong? – harold Dec 23 '14 at 18:16
  • 3
    @harold: No, I think you're right and whoever tried to fix this bias might have made a mistake. – Thomas Dec 23 '14 at 18:18
  • 6
    @harold Time to send an email to the Java guys. – Daniel Dec 23 '14 at 18:26
  • 8
    "Perhaps the fixed version was never tested?" Actually, on rereading this, I think the doc was about a different problem. Note that it mentions **rounding**, which suggests that they didn't consider the "three times as likely" to be the problem, directly, but rather that this leads to a non-uniform distribution when the values are _rounded_. Note that in my answer, the values I list are uniformly distributed, but the low-order bit as represented in IEEE format are not uniform. I think the problem they fixed had to do with the overall uniformity, not the uniformity of the low bit. – ajb Dec 24 '14 at 05:29
  • 1
    In other words, the purpose of the fix was never to straighten out the distribution of the low-order bit. That would not have been a worthwhile goal, in my opinion. – ajb Dec 24 '14 at 05:31
33

This result doesn't surprise me given how floating-point numbers are represented. Let's suppose we had a very short floating-point type with only 4 bits of precision. If we were to generate a random number between 0 and 1, distributed uniformly, there would be 16 possible values:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

If that's how they looked in the machine, you could test the low-order bit to get a 50/50 distribution. However, IEEE floats are represented as a power of 2 times a mantissa; one field in the float is the power of 2 (plus a fixed offset). The power of 2 is selected so that the "mantissa" part is always a number >= 1.0 and < 2.0. This means that, in effect, the numbers other than 0.0000 would be represented like this:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(The 1 before the binary point is an implied value; for 32- and 64-bit floats, no bit is actually allocated to hold this 1.)

But looking at the above should demonstrate why, if you convert the representation to bits and look at the low bit, you will get zero 75% of the time. This is due to all values less than 0.5 (binary 0.1000), which is half the possible values, having their mantissas shifted over, causing 0 to appear in the low bit. The situation is essentially the same when the mantissa has 52 bits (not including the implied 1) as a double does.

(Actually, as @sneftel suggested in a comment, we could include more than 16 possible values in the distribution, by generating:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

But I'm not sure it's the kind of distribution most programmers would expect, so it probably isn't worthwhile. Plus it doesn't gain you much when the values are used to generate integers, as random floating-point values often are.)

ajb
  • 31,309
  • 3
  • 58
  • 84
  • 5
    Using floating point to get random bits/bytes/anything makes me shudder anyway. Even for random distributions between 0 and n, we have [better alternatives (look at arc4random_uniform)](https://www.mirbsd.org/man3/arc4random_uniform) than random*n… – mirabilos Dec 23 '14 at 18:56