이 임의의 값에 50/50 대신 25/75 분포가있는 이유는 무엇입니까?

이 임의의 값에 50/50 대신 25/75 분포가있는 이유는 무엇입니까?

---

편집 : 기본적으로 내가 작성하려고하는 것은 1 비트 해시입니다 double.

double에 true또는 false50/50 기회 를 매핑하고 싶습니다 . 이를 위해 임의의 숫자를 선택하는 코드를 작성 했습니다 (예를 들어, 규칙이있는 데이터에 이것을 사용하고 여전히 50/50 결과를 얻고 싶습니다) . 마지막 비트를 확인하고 y1인지 아니면 증가 하는지 n확인하십시오. 0.

그러나이 코드는 지속적으로 25 % y및 75 % n입니다. 왜 50/50이 아닌가? 왜 그렇게 이상하지만 솔직한 (1/3) 분포입니까?

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);
    }
}

출력 예 :

250167 749833

---

nextDouble은 다음과 같이 작동하기 때문에 : ( source )

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

next(x)x임의의 비트를 만듭니다 .

왜 이것이 중요한가? 첫 번째 부분 (나눗셈 이전)에 의해 생성 된 숫자의 약 절반이보다 작기 1L << 52때문에 그 의미는 그것의 채울 수있는 53 비트를 완전히 채우지 않습니다. 즉, 그 의미의 최하위 비트는 항상 0입니다.

---

많은 관심을 받고 있기 때문에 doubleJava의 (및 다른 많은 언어)가 실제로 어떻게 보이는지 와이 질문에서 왜 중요한지에 대한 추가 설명 이 있습니다.

기본적으로 double다음과 같습니다 : ( source )

이 그림에서 볼 수없는 매우 중요한 세부 사항은 숫자가 "정규화"되어 ¹ 이므로 53 비트 분수는 1로 시작하고 (그런 지수를 선택하여) 1은 생략됩니다. 그렇기 때문에 그림에 분수 (유의)에 대해 52 비트가 표시되지만 실제로 53 비트가 있습니다.

정규화 nextDouble는 53 비트 에 대한 코드에서 설정되면 해당 비트는 암시 적 선행 1이며 사라지고 다른 52 비트는 문자 그대로 결과의 의미에 복사됨을 의미합니다 double. 그러나 해당 비트가 설정되지 않은 경우 나머지 비트는 설정 될 때까지 왼쪽으로 이동해야합니다.

평균적으로 생성 된 숫자의 절반은 유효 값이 전혀 왼쪽으로 이동 하지 않은 경우 (약 절반은 0을 최하위 비트로 표시)이고 나머지 절반은 1 이상 (또는 완전히 0) 따라서 최하위 비트는 항상 0입니다.

1 : 항상, 항상 그런 것은 아닙니다. 가장 높은 숫자는 0이 아닙니다.이 숫자는 비정규 또는 비정규 숫자라고 합니다. wikipedia : denormal number를 참조하십시오 .

---

로부터 문서 :

nextDouble 메소드는 다음과 같이 Random 클래스에 의해 구현됩니다.

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

그러나 그것은 또한 다음을 강조합니다 (강조 광산).

[이전 버전의 Java에서는 결과가 다음과 같이 잘못 계산되었습니다.

 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?

---

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

그러나 이것이 대부분의 프로그래머가 기대하는 분포인지 확실하지 않으므로 아마도 가치가 없을 것입니다. 또한 임의의 부동 소수점 값이 자주있는 것처럼 값을 사용하여 정수를 생성 할 때 많이 얻지 못합니다.)

참고 URL : https://stackoverflow.com/questions/27625611/why-does-this-random-value-have-a-25-75-distribution-instead-of-50-50