Блог

Мое понимание генерации псевдослучайных чисел Common Lisp заключается в том, что (random 1.0) они будут генерировать долю строго меньше 1. Я хотел бы получить цифры до 1.0 включительно. Возможно ли это? Я предполагаю, что я мог бы определить степень точности, сгенерировать целые числа и разделить их на диапазон, но я хотел бы знать, существует ли более широко распространенный способ сделать это. Спасибо.

Как вы говорите, random по умолчанию будут генерироваться числа в [0,1), и в целом (random x) будут генерироваться случайные числа в [0,x). Если бы это были реальные числа и если распределение действительно случайное, то вероятность получения любого числа равна нулю, так что фактически это ничем не отличается от [0,1]. Но это не реальные числа: они являются поплавками, поэтому вероятность получения какого-либо конкретного значения выше, поскольку в [0,1] имеется только конечное число поплавков.

К счастью, вы можете выразить именно то, что хотите: в CL есть множество констант с именами типа* -epsilon , которые определены так, чтобы, например

 (/= (  1.0f0 single-float-epsilon) 1.0f0)  

и single-float-epsilon является самым маленьким single-float , для которого это верно.

Таким образом (random ( 1.0f0 single-float-epsilon)) , будут создаваться случайные одиночные поплавки в диапазоне [0,1], и в конечном итоге, вероятно, получится 1.0f0 . Вы можете проверить это:

 (defun tsit ()  (let ((f (  1.0f0 single-float-epsilon)))  (assert (/= f 1.0f0) (f) "oops")  (loop for i upfrom 1  for v = (random f)  when (= v 1.0f0)  return (values i v))))  

И для меня

 gt; (tsit) 12839205 1.0  

Если вы используете двойные поплавки, это займет … гораздо дольше … чтобы получить 1.0d0 (и не забыть использовать double-float-epsilon ).

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

 (defun make-random-gen (range)  (let ((victim nil)  (count 1))  (lambda ()  (when (zerop (decf count))  (setf count 10000  victim (random range)))  (let ((out (random range)))  (if (eql out victim) range out)))))   (defun testit ()  (loop with r = (make-random-gen 1.0)  for x = (funcall r)  until (eql x 1.0)  counting t))  

На слушателя:

 [5]gt; (testit)  23030093  

Здесь есть небольшое предубеждение в том, что victim это никогда не равно range . Таким образом, это означает, range что значение, такое как 1.0, никогда victim не существует и, следовательно, всегда имеет определенную вероятность возникновения. В то время как любая другая ценность потенциально может превратиться в бытие victim , вероятность ее возникновения временно сведена к нулю. Это должно быть слабо заметно при статистическом анализе выходных данных в том смысле, что range значение будет встречаться немного чаще, чем любое другое значение.

Было бы интересно обновить этот подход с поправкой на это, попыткой сделать это:

 (defun make-random-gen (range)  (let ((victim nil)  (count 1))  (labels ((gen ()  (when (zerop (decf count))  (setf count 10000  victim (gen)))  (let ((out (random range)))  (if (eql out victim) range out))))  #'gen)))  

Теперь , когда мы выбираем victim , мы рекурсируем нашу собственную функцию, которая потенциально может выбирать range . Всякий range раз , когда выбрано как victim , это значение правильно подавляется: range не будет отображаться в выводе, потому out что никогда не будет eql range .

Мы можем обосновать это следующим аргументом, размахивающим рукой:

Давайте предположим, что рекурсивный вызов to gen имеет небольшой уклон в пользу range вывода. Но всякий раз, когда это происходит , range выбирается как victim , что предотвращает его появление в выводе gen .

Существует своего рода отрицательная обратная связь, которая должна почти полностью исправить предвзятость.

Примечание: наша генерация случайных чисел lambda была бы лучше разработана, если бы она также захватила объект случайного состояния и использовала его. Тогда последовательность, которую он выдает, не будет нарушена другими способами использования генератора псевдослучайных чисел. Это уже другая тема.

В теоретическом плане обратите внимание, что ни [0, 1), ни [0, 1] не дают строго правильных распределений. Если бы у нас был математически идеальный PRNG, он давал бы реальные реальные числа в этих диапазонах. Поскольку этот диапазон содержит бесчисленное множество реальных значений, каждое из них будет происходить с нулевой вероятностью: 1/алеф-нуль, который, я предполагаю, настолько мал, что его невозможно отличить от реального нуля.

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

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

Чтобы создать PRNG, который имитирует равномерное распределение значений в интервале от 0,0 до 1,0, мы должны включить значения 0,0 и 1,0 с половинной вероятностью. Таким образом, когда мы собираем большое количество значений из PRNG, столбики 0.0 и 1.0 графика должны быть примерно в два раза выше, чем все остальные столбики.

В этих условиях мы не можем отличить интервал [0, 1,0) от интервала [0, 1,0], потому что они точно такие же большие. Мы должны включить значение 1,0, примерно в половину обычной вероятности, чтобы учесть вышеупомянутую проблему однородности. Если мы просто исключим это значение, мы создадим смещение в неправильном направлении, потому что полоса 1.0 на гистограмме теперь имеет нулевое значение.

Один из способов, которым мы могли бы спасти ситуацию, может заключаться в том, чтобы взять 1,0-эпсилон-полосу гистограммы и сделать это значение на 50% более вероятным, чтобы полоса была на 50% выше среднего. В принципе, мы перегружаем это последнее значение диапазона непосредственно перед 1.0, чтобы представить все до 1.0 и не включая его, требуя, чтобы это значение было более вероятным. А затем мы исключаем значение 1.0 из выходных данных. Все значения, приближающиеся к 1,0 слева, сопоставляются с дополнительной 50% — ной вероятностью 1,0-эпсилон.