Сколько двойных чисел между 0,0 и 1,0?

Это то, о чем я думал в течение многих лет, но я никогда не находил времени, чтобы спросить раньше.

Многие (псевдо) генераторы случайных чисел генерируют случайное число от 0,0 до 1,0. Математически в этом диапазоне бесконечные числа, но doubleэто число с плавающей запятой и, следовательно, имеет конечную точность.

Итак, вопросы:

1. Сколько doubleчисел между 0,0 и 1,0?
2. Столько же чисел от 1 до 2? Между 100 и 101? Между 10 ^ 100 и 10 ^ 100 + 1?

Примечание: если это имеет значение, меня, doubleв частности, интересует определение Java .

Java doubleимеют формат IEEE-754 , поэтому они имеют 52-битную дробь; между любыми двумя соседними степенями двойки (включая одну и doubleисключая следующую), следовательно, будет от 2 до 52-й степени различных s (т. е. 4503599627370496 из них). Например, это количество различных doubles между 0,5 включенным и исключенным 1,0, и ровно столько же находится между 1,0 включенным и 2,0 исключенным и т. Д.

Подсчитать doublesмежду 0,0 и 1,0 труднее, чем между степенями двойки, потому что в этот диапазон входит много степеней двойки, и, кроме того, один попадает в острые проблемы денормализованных чисел. 10 из 11 разрядов экспоненты покрывают рассматриваемый диапазон, поэтому, включая денормализованные числа (и я думаю, несколько видов NaN), у вас будет в 1024 раза больше doubles, чем между степенями двойки - 2**62в любом случае не больше, чем всего . Не считая денормализованного и т. Д., Я считаю, что счет будет 1023 раза 2**52.

Для произвольного диапазона, такого как «от 100 до 100,1», это еще сложнее, потому что верхняя граница не может быть точно представлена ​​как double(не является точным кратным любой степени двойки). В качестве удобного приближения, поскольку прогрессия между степенями двойки линейна, вы могли бы сказать, что указанный диапазон является 0.1 / 64th от промежутка между окружающими степенями двойки (64 и 128), поэтому вы ожидаете около

(0.1 / 64) * 2**52

отличное doubles - которое сводится к 7036874417766.4004... плюс-минус один или два ;-).

Каждое doubleзначение, представление которого находится между 0x0000000000000000и 0x3ff0000000000000лежит в интервале [0.0, 1.0]. Это (2 ^ 62 - 2 ^ 52) различных значений (плюс или минус пара в зависимости от того, подсчитываете ли вы конечные точки).

Интервал [1.0, 2.0] соответствует представлениям между 0x3ff0000000000000и 0x400000000000000; это 2 ^ 52 различных значения.

Интервал [100.0, 101.0] соответствует представлениям между 0x4059000000000000и 0x4059400000000000; это 2 ^ 46 различных значений.

Между 10 ^ 100 и 10 ^ 100 + 1 нет удвоений . Ни одно из этих чисел не может быть представлено с двойной точностью, и между ними нет двойных чисел. Ближайшими двумя числами двойной точности являются:

99999999999999982163600188718701095...

а также

10000000000000000159028911097599180...

Другие уже объяснили, что в диапазоне [0.0, 1.0] есть около 2 ^ 62 двойников.
(Неудивительно: существует почти 2 ^ 64 различных конечных двойников; из них половина положительны, а примерно половина из них <1.0.)

Но вы упомянули генераторы случайных чисел: обратите внимание, что генератор случайных чисел, генерирующий числа от 0,0 до 1,0, в общем случае не может произвести все эти числа; обычно он будет выдавать только числа в форме n / 2 ^ 53 с целым числом n (см., например, документацию Java для nextDouble ). Таким образом, обычно существует только около 2 ^ 53 (+/- 1, в зависимости от того, какие конечные точки включены) возможных значений для random()вывода. Это означает, что большинство двойников в [0.0, 1.0] никогда не будут сгенерированы.

В статье «Новая математика Java, Часть 2: Числа с плавающей запятой» от IBM предлагается следующий фрагмент кода для решения этой проблемы (для чисел с плавающей запятой, но я подозреваю, что он работает и для чисел с двойной точностью):

public class FloatCounter {

    public static void main(String[] args) {
        float x = 1.0F;
        int numFloats = 0;
        while (x <= 2.0) {
            numFloats++;
            System.out.println(x);
            x = Math.nextUp(x);
        }
        System.out.println(numFloats);
    }
}

У них есть такой комментарий по этому поводу:

Оказывается, всего 8 388 609 чисел с плавающей запятой между 1.0 и 2.0 включительно; большое, но вряд ли бесчисленное множество действительных чисел, существующих в этом диапазоне. Между последовательными числами примерно 0,0000001. Это расстояние называется ULP для единицы наименьшей точности или последней единицы.

1. 2 ^ 53 - размер мантиссы / мантиссы 64-битного числа с плавающей запятой, включая скрытый бит.
2. Примерно да, так как sifnificand фиксируется, но показатель степени меняется.

См. Статью в Википедии для получения дополнительной информации.

Двойное число Java - это двоичное 64-разрядное число IEEE 754.

Это означает, что нам необходимо учитывать:

1. Мантисса 52 бит
2. Экспонента - это 11-битное число со смещением 1023 (т.е. с добавленным к нему 1023)
3. Если показатель степени равен 0, а мантисса не равна нулю, то число называется ненормализованным.

Это в основном означает, что существует всего 2 ^ 62-2 ^ 52 + 1 возможных двойных представлений, которые согласно стандарту находятся между 0 и 1. Обратите внимание, что 2 ^ 52 + 1 предназначено для удаления случаев ненормализованного числа.

Помните, что если мантисса положительна, а показатель степени отрицателен, число положительно, но меньше 1 :-)

Для других чисел это немного сложнее, потому что крайние целые числа не могут быть представлены точным образом в представлении IEEE 754, и потому что есть другие биты, используемые в экспоненте, чтобы иметь возможность представлять числа, поэтому чем больше число, тем меньше разные значения.