Как создать число в произвольном диапазоне, используя random () = {0..1}, сохраняя однородность и плотность?

Question

Генерирует случайное число в диапазоне [x..y], где x и y - любые произвольные числа с плавающей запятой. Используйте функцию random (), которая возвращает случайное число с плавающей точкой в ​​диапазоне [0..1] из P равномерно распределенных чисел (назовите это «плотность»). Равномерное распределение должно быть сохранено, а P также масштабироваться.

Я думаю, что для такой проблемы нет простого решения. Чтобы немного упростить это, я спрашиваю вас, как сгенерировать число в интервале [-0,5 .. 0,5], затем в [0 .. 2], затем в [-2 .. 0], сохраняя однородность и плотность? Таким образом, для [0 .. 2] он должен генерировать случайное число из P * 2 равномерно распределенных чисел.

Очевидное простое решение random() * (x - y) + y сгенерирует не все возможные числа из-за меньшей плотности для всех abs(x-y)>1.0 случаев. Многие возможные значения будут пропущены. Помните, что random () возвращает только число из P возможных чисел. Затем, если вы умножите такое число на Q, это даст вам только одно из возможных значений P, масштабированное на Q, но вам также придется масштабировать плотность P на Q.

Answer 1

Если я хорошо понимаю вашу проблему, я предоставлю вам решение, но я бы исключил 1 из диапазона.

N = numbers_in_your_random // [0, 0.2, 0.4, 0.6, 0.8] will be 5

// This turns your random number generator to return integer values between [0..N[;
function randomInt()
{
    return random()*N;
}

// This turns the integer random number generator to return arbitrary
// integer
function getRandomInt(maxValue)
{
    if (maxValue < N)
    {
        return randomInt() % maxValue;
    }
    else
    {
        baseValue = randomInt();
        bRate = maxValue DIV N;
        bMod = maxValue % N;
        if (baseValue < bMod)
        {
            bRate++;
        }
        return N*getRandomInt(bRate) + baseValue;
    }
}

// This will return random number in range [lower, upper[ with the same density as random()
function extendedRandom(lower, upper)
{
    diff = upper - lower;
    ndiff = diff * N;
    baseValue = getRandomInt(ndiff);
    baseValue/=N;
    return lower + baseValue;
}

Answer 2

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

Самым сложным случаем является любой интервал с нулем.В этом случае, чтобы получить ровное распределение, вам нужно обработать каждый показатель степени до самого низкого плюс денормализованные числа.В качестве особого случая вам нужно будет разделить ноль на два случая: +0 и -0.

Кроме того, если вы так пристально следите за результатом, вам необходимо убедиться, что выиспользуя хороший генератор псевдослучайных чисел с достаточно большим пространством состояний, чтобы можно было ожидать, что оно поразит каждое значение с почти равномерной вероятностью.Это дисквалифицирует функции библиотеки C / Unix rand() и, возможно, *rand48();вместо этого вы должны использовать что-то вроде Mersenne Twister .

---

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

Первый шаг - выбрать подходящий подинтервал с вероятностью, пропорциональной его размеру.Если интервал содержит 0 или иным образом покрывает большой динамический диапазон, это может потенциально потребовать количество случайных битов вплоть до полного диапазона доступного показателя степени.

В частности, для 32-разрядного числа IEEE-754 существует 256 возможных значений экспоненты.Каждый показатель определяет диапазон, равный половине размера следующего большего показателя, за исключением денормализованного случая, который равен размеру наименьшей области нормального показателя.Ноль можно считать наименьшим денормализованным числом;как упомянуто выше, если целевой интервал колеблется от нуля, вероятность каждого из +0 и -0, возможно, следует сократить вдвое, чтобы избежать удвоения его веса.

Если выбранный подинтервал охватывает всю область, определяемуюконкретный показатель, все, что необходимо, это заполнить мантиссу случайными битами (23 бита, для 32-битных операций с плавающей запятой IEEE-754).Однако, если подинтервал не покрывает весь регион, вам нужно будет сгенерировать случайную мантиссу, которая охватывает только этот подинтервал.

Самый простой способ обработки начальных и вторичных случайных шагов может заключаться в округлении целиВыделите интервал, чтобы включить все частично показанные области экспоненты, затем отклоните и повторите числа, которые выходят за его пределы.Это позволяет сгенерировать показатель степени с простыми вероятностями степени 2 (например, путем подсчета числа ведущих нулей в вашем случайном битовом потоке), а также обеспечивает простой и точный способ генерации мантиссы, которая охватывает только частьинтервал экспоненты.(Это также хороший способ обработки особого случая +/- 0.)

В качестве другого особого случая: чтобы избежать неэффективной генерации для целевых интервалов, которые намного меньше областей экспоненты, в которых они находятся, "Очевидное простое «решение» на самом деле будет генерировать довольно равномерные числа для таких интервалов.Если вы хотите точно равномерное распределение, вы можете сгенерировать мантиссу под-интервала, используя только случайные биты, достаточные для покрытия этого под-интервала, и в то же время использовать вышеупомянутый метод отклонения для исключения значений за пределами целевого интервала.

Answer 3

Рассмотрим этот подход:

Я предполагаю, что базовый генератор случайных чисел в диапазоне [0..1] генерирует среди чисел

0, 1/(p-1), 2/(p-1), ..., (p-2)/(p-1), (p-1)/(p-1)

Если цельдлина интервала меньше или равна 1, возвращает random()*(y-x) + x.

В противном случае сопоставьте каждое число r из базового ГСЧ с интервалом в целевом диапазоне:

[r*(p-1)*(y-x)/p, (r+1/(p-1))*(p-1)*(y-x)/p]

(то есть для каждого из чисел P назначьте один из интервалов P длиной (y-x)/p)

Затем рекурсивно сгенерируйте другое случайное число в этом интервале и добавьте его в начало интервала.

Псевдокод:

const p;

function rand(x, y)
  r = random()
  if y-x <= 1
    return x + r*(y-x)
  else
    low = r*(p-1)*(y-x)/p
    high = low + (y-x)/p
    return x + low + rand(low, high)

Answer 4

Позвольте мне перефразировать ваш вопрос:

Пусть random() - генератор случайных чисел с дискретным равномерным распределением по [0,1). Пусть D будет числом возможных значений, возвращаемых random(), каждое из которых точно на 1/D больше предыдущего. Создайте генератор случайных чисел rand(L, U) с дискретным равномерным распределением по [L, U), чтобы каждое возможное значение было точно на 1/D больше предыдущего.

-

Пара быстрых заметок.

1. Проблема в этой форме, и, как вы ее сформулировали, она неразрешима. Тот если N = 1, мы ничего не можем сделать.
2. Мне не требуется, чтобы 0.0 было одним из возможных значений для random(). Если это не так, то возможно, что приведенное ниже решение потерпит неудачу, когда U - L < 1 / D. Меня это не особо беспокоит.
3. Я использую все полуоткрытые диапазоны, потому что это упрощает анализ. Использовать закрытые диапазоны было бы просто, но утомительно.

Наконец, хорошие вещи. Ключевым моментом здесь является то, что плотность можно поддерживать, независимо выбирая целые и дробные части результата.

Во-первых, обратите внимание, что с учетом random() создать randomBit() тривиально. То есть

randomBit() { return random() >= 0.5; }

Затем, если мы хотим выбрать один из {0, 1, 2, ..., 2^N - 1} равномерно случайным образом, то есть просто с помощью randomBit(), просто сгенерировать каждый из битов. Назовите это random2(N).

Используя random2(), мы можем выбрать один из {0, 1, 2, ..., N - 1}:

randomInt(N) { while ((val = random2(ceil(log2(N)))) >= N); return val; }

Теперь, если известно D, то проблема тривиальна, поскольку мы можем сократить ее до простого простого выбора одного из floor((U - L) * D) значений равномерно случайным образом, и мы можем сделать это с помощью randomInt().

Итак, давайте предположим, что D неизвестно. Теперь давайте сначала создадим функцию для генерации случайных значений в диапазоне [0, 2^N) с правильной плотностью. Это просто.

rand2D(N) { return random2(N) + random(); }

rand2D() - это то место, где мы требуем, чтобы разница между последовательными возможными значениями для random() была точно 1/D. Если нет, то возможные значения здесь не будут иметь равномерную плотность.

Далее нам нужна функция, которая выбирает значение в диапазоне [0, V) с правильной плотностью. Это похоже на randomInt() выше.

randD(V) { while ((val = rand2D(ceil(log2(V)))) >= V); return val; }

И наконец ...

rand(L, U) { return L + randD(U - L); }

Теперь мы можем сместить дискретные позиции, если L / D не является целым числом, но это неважно.

-

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

Answer 5

хорошо, [0..1] * 2 == [0..2] (все еще в форме)

[0..1] - 0.5 == [-0.5..0.5] и т. Д.

Интересно, где вы проходили такое интервью?

Обновление: Хорошо, если мы хотим начать заботиться о потере точности при умножении (что странно, потому что почему-то вас это не заботило в исходной задаче, и притворимся, что мы заботимся о "количестве значений"), мы можем начать итерацию.Для этого нам понадобится еще одна функция, которая будет возвращать равномерно распределенные случайные значения в [0..1) - это можно сделать, отбросив значение 1.0, если оно когда-либо появится. После этого мы можем нарезать весь диапазон вравные части достаточно малы, чтобы не заботиться о потере точности, выберите одну случайно (у нас достаточно случайности, чтобы сделать это) и выберите число в этом сегменте, используя функцию [0..1) для всех частей, кроме последней.

Или вы можете придумать способ кодирования достаточного количества значений, чтобы заботиться о них, - и просто сгенерировать случайные биты для этого кода, и в этом случае вам все равно, будет ли это[0..1] или просто {0, 1}.

Answer 6

Если я правильно понимаю вашу проблему, это то, что rand () генерирует точно разнесенные, но в конечном итоге дискретные случайные числа.И если мы умножим его на (yx), что является большим, то эти значения с плавающей запятой распределяются точно так, что пропускаются многие значения с плавающей запятой в диапазоне [x, y].Это нормально?

Если так, я думаю, у нас уже есть решение, данное Диалектиком.Позвольте мне объяснить, почему он прав.

Сначала мы знаем, как сгенерировать случайное число с плавающей точкой, а затем добавить к нему другое значение с плавающей запятой.Это может привести к ошибке округления из-за сложения, но это будет только в последнем десятичном знаке.Используйте удвоения или что-то с более точным числовым разрешением, если вы хотите большей точности.Таким образом, с этим предупреждением проблема не сложнее, чем найти случайное число с плавающей точкой в ​​диапазоне [0, yx] с равномерной плотностью.Допустим, yx = z.Очевидно, что, поскольку z является плавающей точкой, она не может быть целым числом.Мы решаем проблему в два этапа: сначала мы генерируем случайные цифры слева от десятичной точки, а затем генерируем случайные цифры справа от нее.Выполнение обоих одинаково означает, что их сумма также равномерно распределена по диапазону [0, z].Пусть w будет наибольшим целым числом <= z.Чтобы ответить на нашу упрощенную задачу, мы можем сначала выбрать случайное целое число из диапазона {0,1, ..., w}.Затем шаг № 2 заключается в добавлении случайного числа с плавающей точкой к этому случайному числу.Это не умножается на какие-либо большие значения, поэтому имеет такое же высокое разрешение, как и числовой тип.(Предполагая, что вы используете идеальный генератор случайных чисел с плавающей запятой.) </p>

Так что насчет углового случая, когда случайное целое число было наибольшим (т.е. w), а случайное число с плавающей точкой, которое мы добавили к нему, было большеz - w, чтобы случайное число превышало допустимый максимум?Ответ прост: сделайте все это снова и проверьте новый результат.Повторяйте, пока не получите цифру в допустимом диапазоне.Это простое доказательство того, что равномерно сгенерированное случайное число, которое отбрасывается и генерируется снова, если оно находится за пределами допустимого диапазона, приводит к равномерно сгенерированному случайному числу в допустимом диапазоне.Как только вы сделаете это ключевое наблюдение, вы увидите, что Диалектик соответствует всем вашим критериям.

Answer 7

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

И когда вы умножаете его на число (NUM), вы теряете эту точность на lg (NUM) (логарифм на основе 10). Поэтому, если вы умножите на 1000 (NUM = 1000), вы потеряете последние 3 цифры (lg (1000) = 3).

Вы можете исправить это, добавив меньшее случайное число к оригиналу, в котором пропущено 3 цифры. Но вы не знаете точности, поэтому не можете определить, где именно они.

Я могу представить два сценария:

(X = начало диапазона, Y = конец диапазона)

1: вы определяете точность (PREC, например, 20 цифр, поэтому PREC = 20) и считаете ее достаточной для генерации случайного числа, поэтому выражение будет:

( random() * (Y-X) + X ) + ( random() / 10 ^ (PREC-trunc(lg(Y-X))) )

с номерами: (X = 500, Y = 1500, PREC = 20)

( random() * (1500-500) + 500 ) + ( random() / 10 ^ (20-trunc(lg(1000))) )
( random() * 1000 + 500 ) + ( random() / 10 ^ (17) )

Есть некоторые проблемы с этим:

• 2-фазная случайная генерация (сколько она будет случайной?)
• первое случайное возвращение 1 -> результат может быть вне диапазона

2: угадать точность по случайным числам

вы определяете несколько попыток (например, 4) для вычисления точности путем генерации случайных чисел и подсчета точности каждый раз:

- 0.4663164 -> PREC=7
- 0.2581916 -> PREC=7
- 0.9147385 -> PREC=7
- 0.129141  -> PREC=6 -> 7, correcting by the average of the other tries

Это моя идея.

Answer 8

Вы должны учитывать количество энтропии, которое возникает при каждом обращении к вашему ГСЧ. Вот код C #, который я только что написал, который демонстрирует, как вы можете накапливать энтропию из источников с низкой энтропией и получать случайное значение с высокой энтропией.

using System;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace SO_8019589
{
  class LowEntropyRandom
  {
    public readonly double EffectiveEntropyBits;
    public readonly int PossibleOutcomeCount;
    private readonly double interval;
    private readonly Random random = new Random();
    public LowEntropyRandom(int possibleOutcomeCount)
    {
      PossibleOutcomeCount = possibleOutcomeCount;
      EffectiveEntropyBits = Math.Log(PossibleOutcomeCount, 2);
      interval = 1.0 / PossibleOutcomeCount;
    }
    public LowEntropyRandom(int possibleOutcomeCount, int seed)
      : this(possibleOutcomeCount)
    {
      random = new Random(seed);
    }
    public int Next()
    {
      return random.Next(PossibleOutcomeCount);
    }
    public double NextDouble()
    {
      return interval * Next();
    }
  }

  class EntropyAccumulator
  {
    private List<byte> currentEntropy = new List<byte>();
    public double CurrentEntropyBits { get; private set; }
    public void Clear()
    {
      currentEntropy.Clear();
      CurrentEntropyBits = 0;
    }
    public void Add(byte[] entropy, double effectiveBits)
    {
      currentEntropy.AddRange(entropy);
      CurrentEntropyBits += effectiveBits;
    }
    public byte[] GetBytes(int count)
    {
      using (var hasher = new SHA512Managed())
      {
        count = Math.Min(count, hasher.HashSize / 8);
        var bytes = new byte[count];
        var hash = hasher.ComputeHash(currentEntropy.ToArray());
        Array.Copy(hash, bytes, count);
        return bytes;
      }
    }
    public byte[] GetPackagedEntropy()
    {
      // Returns a compact byte array that represents almost all of the entropy.
      return GetBytes((int)(CurrentEntropyBits / 8));
    }
    public double GetDouble()
    {
      // returns a uniformly distributed number on [0-1)
      return (double)BitConverter.ToUInt64(GetBytes(8), 0) / ((double)UInt64.MaxValue + 1);
    }
    public double GetInt(int maxValue)
    {
      // returns a uniformly distributed integer on [0-maxValue)
      return (int)(maxValue * GetDouble());
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var random = new LowEntropyRandom(2);  // this only provides 1 bit of entropy per call
      var desiredEntropyBits = 64; // enough for a double
      while (true)
      {
        var adder = new EntropyAccumulator();
        while (adder.CurrentEntropyBits < desiredEntropyBits)
        {
          adder.Add(BitConverter.GetBytes(random.Next()), random.EffectiveEntropyBits);
        }
        Console.WriteLine(adder.GetDouble());
        Console.ReadLine();
      }
    }

  }
}

Поскольку я использую 512-битную хеш-функцию, это максимальное количество энтропии, которое вы можете получить из EntropyAccumulator. Это может быть исправлено, если обязательно.

Answer 9

В реальной математике: решение только при условии:

return random() * (upper - lower) + lower

Проблема в том, что, даже если у вас есть числа с плавающей запятой, имеют только определенное разрешение.Итак, вы можете применить вышеуказанную функцию и добавить другое значение random (), масштабированное к отсутствующей части.

Если я приведу практический пример, станет ясно, что я имею в виду:

Например, взять случайное() возвращаемое значение от 0..1 с точностью до 2 цифр, то есть 0.XY, и ниже с 100 и выше с 1100.

Таким образом, с приведенным выше алгоритмом вы получите в результате 0.XY * (1100-100) + 100 = XY0.0 + 100. Вы никогда не увидите 201 как результат, так как конечная цифра должна быть 0.

Решением здесь было бы снова сгенерировать случайное значение и добавить его * 10, поэтомуу вас есть точность в одну цифру (здесь вы должны позаботиться о том, чтобы не превысить заданный диапазон, что может произойти, в этом случае вам придется отбросить результат и сгенерировать новое число).

Возможно, у вас естьповторяем, как часто зависит от того, сколько мест доставляет функция random () и сколько вы ожидаете в конечном результате.

В стандартном формате IEEE точность ограничена (т. е. двойными 53 битами).Поэтому, когда вы генерируете число таким образом, вам никогда не нужно генерировать более одного дополнительного числа.

Но вы должны быть осторожны, что при добавлении нового номера вы не превысите заданный вами верхний предел.Существует несколько решений: во-первых, если вы превысите свой лимит, вы начнете с нового, генерируя новый номер (не обрезайте или не похожий, так как это меняет распределение).

Вторая возможность - проверитьвведите интервал недостающего нижнего битового диапазона, найдите среднее значение и сгенерируйте подходящее значение, которое гарантирует соответствие результата.