Каково общее количество уникальных значений для двойника в диапазоне [0,0, 1,0)?

Question

Random.NextDouble () (Double из диапазона [0.0,1.0)) иногда умножается на большое значение Int64 (пусть Int64 большое = 9000000000L), и результат вычисляется для получения случайного значения Int64 больше, чем может бытьполученный из Random.Next () (Int32 из диапазона [0, Int32.MaxValue)).

Random r = new Random();
long big = 9000000000L;
long answer = (long) (r.NextDouble() * big);

Мне кажется, что общее количество уникальных значений для Double в диапазоне [0.0, 1.0) предоставляет верхнюю границу для числа уникальных Int64, которые он может генерировать.На самом деле, свободная верхняя граница, как много разных двойников, будет отображаться на один и тот же Int64.

Поэтому я хотел бы знать: каково общее количество уникальных значений для двойного в диапазоне [0.0, 1.0)?

Еще лучше, если вы скажете мне, какое наибольшее значение может принимать «большое», чтобы «ответ» мог быть значением из диапазона [0, большое), и является ли распределениеЗначения «answer» одинаковы, если предположить, что Random.NextDouble () одинаков.

Редактировать: Double (double) здесь относится к двойному значению IEEE 754 с плавающей точкой, в то время как Int64 (long) и Int32 (int) относятся к 64-битному и 32-битному дополнению со знаком 2 соответственно.

---

Вдохновленный этим вопросом: Генерация 10-значного уникального случайного числа в Java

Хотя я использовал C #, этот вопрос не зависит от языка и больше касается дискретной математики, чем программирования,но это беспокоит меня не столько из-за математического любопытства, сколько из-за того, что программист хочет использовать формулу только в том случае, если он делает то, что должен, и с точки зрения безопасности.

Answer 1

IEEE-754 имеет 11 битов экспоненты и 52 мантиссы.Предполагая, что бит знака равен 0 (положительный), если показатель степени находится в диапазоне от 0x001 до 0x3FE, значение является стандартным числом с плавающей запятой между 0 и 1. Мантисса интерпретируется с ведущей 1, которая не сохраняется.Для каждого из этих значений 0x3FE для показателя степени существует 2 ^ 52 значений мантиссы.Кроме того, если показатель степени равен 0x000, мантисса интерпретируется без этого начального значения, но, как если бы показатель степени был 0x001, в общей сложности 0x3FF = 1023 показателя, где все мантиссы действительны.Это всего 1023 * 2 ^ 52 значений.Кроме того, может учитываться отрицательный 0, что является еще одним значением.

Если бы случайные двойные числа были сгенерированы равномерно из всех значений, то это действительно привело бы к смещению при умножении для генерации Int64.Однако любая разумная случайная библиотека будет приближаться к равномерному распределению на [0, 1), и это не будет смещено при превращении ее в Int64.Наибольшее значение для «большого», которое позволит получить все целые числа в [0, большое), равно 2 ^ 53 - разрешение 2 ^ 52 чисел от 1/2 до 1 равно 2 ^ (- 53).Тем не менее, часто бывает, что эти числа создаются путем деления случайных целых чисел на диапазон целых чисел (обычно Int32), что означает, что вы не можете произвести больше чисел, чем этот источник.Вместо этого рассмотрим непосредственное объединение двух Int32, например, путем смещения одного на 32 бита и объединения их в Int64.(Хотя будьте осторожны - пространство состояний для генератора может быть только 32 бита.)

Answer 2

В качестве ответа на ваш вопрос я скажу вам, что генератор Random C # внутренне использует генератор, который «дает ему» числа между 0...Int32.MaxValue - 1.Затем он делит число на Int32.MaxValue (технически оно умножается на обратное значение этого числа), чтобы вернуть двойное число.Таким образом, в C # возвращаются только Int32.MaxValue возможных двойных значений (0...Int32.MaxValue - 1)

Answer 3

IEEE754 довольно четко показывает точность двойных чисел:

http://en.wikipedia.org/wiki/IEEE_754-2008

У вас есть 52 бита плюс дополнительный предполагаемый бит.

У вас есть экспонентыот -1022 до 1023, около 11 бит, включая знак.

64-й бит является общим знаком для числа.

Мы будем игнорировать субнормализованные числа.

Вы спрашиваете об показателях в диапазоне от -1022 до 0. Это означает, что у вас есть около 10 из доступных 11 битов экспоненты, доступных вам.

У вас есть 52 + 1 бит доступной мантиссы.

Это около 62 битов используемой точности для представления 2 ** 62 отличных значений от

Answer 4

@ wnoise в значительной степени прибил его, но вот мои два цента.

Поплавки IEEE можно сравнивать и увеличивать как целые числа с некоторыми ограничениями, см. этот вопрос для получения подробной информации.Итак, если мы приведем +0.0 и 1.0 к 64-битным целым числам, мы получим количество шагов от нуля до единицы:

#include <iostream>

int main()
{
        double zero = 0.0;
        double one = 1.0;
        unsigned long long z = *reinterpret_cast<unsigned long long*>(&zero);
        unsigned long long o = *reinterpret_cast<unsigned long long*>(&one);
        std::cout << z << std::endl;
        std::cout << o << std::endl;
}

Это даст мне 0 и 4607182418800017408 соответственно, то есть 4607182418800017408 уникальных двойных значенийв диапазоне [0,0, 1,0).

Answer 5

Это зависит от реализации double. Существуют реализации, которые не допускают денормализованные значения и опускают лидирующие; определить количество возможных значений здесь легко:

• есть несколько «специальных» значений (0, +0, -0, + ∞, -∞, тихий NaN, сигнальный NaN), которые обычно стоят вам одного возможного показателя
• нет способа, чтобы смещение мантиссы и изменение степени давало эквивалентное число

Если ваша реализация допускает денормализованные значения, определение этого числа становится немного сложнее, но я бы начал с сопоставления возможных значений в этом представлении с эквивалентным представлением с фиксированным начальным (которое будет использовать на один бит меньше мантисса); если вы нашли подходящее отображение, оно будет инъективным , и вы уменьшите проблему до более простого.

Answer 6

Общее количество уникальных значений для double в диапазоне [0.0, 1.0) зависит от представления double в конкретной среде.

Одним из наиболее распространенных представлений является то, которое указано IEEE 754 . Этот формат e. г. предписано Java и C # (см. 1.3 Типы и переменные для последних).