Введение в PRNG с Python и R

Самые важные жизненные вопросы, по большей части, не что иное, как проблемы вероятности.

Пьер-Симон де Лаплас

Представьте себе такой сценарий: вы с братом хотите пойти в кино. Проигрываются два фильма: «Интерстеллар» (тот, который хотите посмотреть вы) и «Заводной апельсин» (который хочет посмотреть ваш брат).

Классическим решением этой проблемы является подбрасывание монеты, но, поскольку мы не лишены воображения (или у нас нет монеты), мы можем найти более элегантное решение.

Итак, давайте определим программу, которая решает, что видеть в R и Python. Программа сгенерирует число от 0 до 1. Если это число ближе к 0, смотрим Interstellar. В противном случае выбирается «Заводной апельсин».

import random as rd

x = rd.uniform(0, 1)

if x < .5:
    print("Interstellar")
else:
    print("A Clockwork Orange")

Теперь делаем то же самое в R:

x <- runif(1)

ifelse(x < .5, "Interstellar", "A Clockwork Orange")

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

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

В этой статье я хочу познакомить вас с генераторами псевдослучайных чисел и их применением.

Детерминизм против случайности

Выше я написал «компьютер, совершенно детерминированная машина», но что значит быть детерминированной?

Короче говоря, компьютеры детерминированы, потому что они следуют набору инструкций или программе предсказуемым образом, то есть при некоторых входных данных они всегда возвращают один и тот же результат. Парадокс заключается в том, что в приведенном выше примере x = rd.uniform(0, 1) и x <- runif(1) каждый раз при компиляции строки возвращают разные значения.

Являются ли x = rd.uniform(0, 1) и x <- runif(1) исключениями из детерминированного свойства компьютеров?

Ответ — нет, и через минуту я объясню причины этого.

Что такое случайность

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

• отсутствие шаблона: случайная последовательность не должна иметь какой-либо различимой структуры;
• независимость: числа в случайной последовательности не должны влиять друг на друга;
• непредсказуемость: случайную последовательность чисел нельзя предсказать или восстановить.

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

Генераторы случайных чисел — это математические алгоритмы или механические устройства, которые создают последовательность, соответствующую вышеуказанным свойствам.

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

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

Как следует из названия, генераторы псевдослучайных чисел — это тип программного обеспечения, используемого для создания последовательности чисел, которые имитируют свойства действительно случайных чисел. Алгоритм принимает исходные данные (начальное число), которые создают последовательность. начальное число — это то, что определяет последовательность чисел, например, если мы устанавливаем исходное число 1234, многократно компилируя следующие строки кода, x остается неизменным. В Питоне это:

import random as rd

rd.seed(1234)

x = rd.uniform(0, 1)

print(x)

То же самое верно для следующего кода R:

set.seed(1234)

x <- runif(1)

print(x)

Характеристики

Достоинство PRNG определяется его свойствами. Наиболее важными свойствами являются:

• периодичность: ГПСЧ будут генерировать последовательность чисел, которая повторяется после определенного количества итераций, известного как период. ГПСЧ с длинным периодом более желателен, чем с более коротким периодом;
• однородность: PRNG генерирует числа, которые равномерно распределяются в диапазоне возможных значений;
• независимость: числа, сгенерированные ГПСЧ, должны быть независимы друг от друга;
• случайность: числа, сгенерированные ГПСЧ, не должны иметь каких-либо различимых шаблонов;
• seed-ability: PRNG должны иметь возможность задавать начальное значение, чтобы получить другую последовательность.

Два алгоритма PRNG

В этом разделе я хочу представить самые известные алгоритмы ГПСЧ, чтобы на практике показать, как выглядят ГПСЧ. Я представлю алгоритм среднего квадрата и алгоритмы линейного конгруэнтного генератора.

Алгоритм среднего квадрата

Алгоритм среднего квадрата, предложенный фон Нейманом, использует начальное число, которое возводится в квадрат, а его среднее значение извлекается как случайное число. Давайте обсудим пример, а затем реализуем его на Python и R.

Обычно алгоритм повторяется более одного раза, т. е. случайное число становится новым начальным числом, а затем возводится в квадрат, а его среднее значение становится случайным числом и так далее.

Вот реализация на Python:

import numpy as np

def middle_square_algo(seed):

    # first of all we square the seed
    square = str(np.square(seed))

    # then we need to take the mid-term, we have two possibilities
    # the square may have an even number of digits:
    if len(square) % 2 == 0:
        half_str = int(len(square) / 2)

    # the number has an odd number of digits:
    else:
        half_str = int(len(square) / 2 - .5)


    mid = square[half_str - 1 : half_str + 1]
    return int(mid)

# finally the testing:

print(middle_square_algo(12))

#> 14

А вот код R:

middle_square_algo <- function(seed){

  # first of all we square the seed
  square <- seed^2

  # we now need to get the number of digits of square
  len <- nchar(square)

  # we have two possible scenarios
  # len is even:
  if(len %% 2 == 0){

    half_square <- len / 2

  # len is odd:  
  } else{

    half_square <- len / 2 + .5

  }
  square <- as.character(square)
  mid <- substr(square, half_square, half_square + 1)

  return(as.double(mid))
}

# finally the testing:
print(middle_square_algo(33))

#> 8

Предполагая, что мы хотим зациклить алгоритм более одного раза, код Python выглядит так:

def middle_square_algo_deep(seed, deep):

    # we just need to repeat what we did before but more than one time

    for rep in range(deep):
        seed = int(middle_square_algo(seed))
    return seed

# finally the testing:      
middle_square_algo_deep(33, 3)

#> 9

Аналогично, код R:

middle_square_algo_deep <- function(seed, deep=2){

  # we just need to repeat what we did before but more than one time

  for( rep in 1:deep){
    seed <- middle_square_algo(seed)
  }

  return(seed)
}

# finally the testing:
middle_square_algo_deep(33, 3)

#> 9

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

Например, начальное число 50 имеет очень короткий период (1), как показано в следующих строках кода:

middle_square_algo_deep(50, 1)
#> 50

middle_square_algo_deep(50, 2)
#> 50

middle_square_algo_deep(50, 3)
#> 50

middle_square_algo_deep(50, 4)
#> 50

Линейные конгруэнтные генераторы

Линейные конгруэнтные генераторы (LCG) представляют собой семейство PRNG и, вероятно, являются наиболее часто используемым подходом к генерации псевдослучайных чисел. Алгоритмы определяются линейным конгруэнтным уравнением следующего вида:

где a, b и c — положительные целые числа, и нам также нужно начальное число.

Теперь давайте рассмотрим (а затем реализуем) конкретный LCG: Запаздывающий генератор Фибоначчи (LFG).

Нам просто нужно предоставить LFG от x_1 до x_{max(i, j)+1}, и он сгенерирует псевдослучайную последовательность чисел.

Позвольте мне привести пример, чтобы прояснить ваш разум. Пусть следующее уравнение будет нашим LFG:

и допустим, мы хотим сгенерировать последовательность случайных чисел от 1 до 9 из начального начального числа [4, 2, 9, 5, 5].

Последовательность начинается с x_6 (можно легко доказать, что значений до x_6 не существует, поскольку max(i, j) = 5).

Таким образом, последовательность такова:

и так далее.

Теперь мы реализуем LFG на Python и R. В Python алгоритм выглядит примерно так:

def lagged_fib_gen(seed, i, j, mod, length, a_1 = 1, a_2 = 1, c = 0):
    l_f = seed

        # we suppose that i < j

    for rep in range(max([i, j]) + 1, length + 1):

        x = (a_1 * l_f[rep - i - 1] + a_2 * l_f[rep - j - 1]) % 10
        l_f.append(x)

    return l_f

# finally the testing:
lagged_fib_gen([4, 2, 9, 5, 5], 3, 5, 10, 10)

#> [4, 2, 9, 5, 5, 3, 7, 4, 8, 2]

В R алгоритм такой:

lagged_fib_gen <- function(seed, i, j, mod, length, a_1 = 1, a_2 = 1, c = 0){

  l_f <- seed

  for(rep in (max(c(i, j))+1):length){

    x <- (a_1 * l_f[rep - i] + a_2 * l_f[rep - j]) %% mod
    l_f[rep] <- x
  }
  return(l_f)
}

# finally the testing:
lagged_fib_gen(c(4, 2, 9, 5, 5), 3, 5, 10, 10)

#> 4 2 9 5 5 3 7 4 8 2

Что касается алгоритма среднего квадрата, эффективность LGC зависит от выбранных параметров.

Теперь мы знаем, что такое PRNG, но для чего они используются? Ну, у них много приложений, некоторые примеры включают:

• криптография: случайные числа используются для генерации ключей шифрования (ГПСЧ, используемые в криптографии, намного сложнее, чем два, которые я показал ранее);
• моделирование: во многих научных симуляциях для представления неопределенности используются случайные числа;
• игры: случайные числа используются, чтобы сделать игры менее предсказуемыми и сложными (например, генерация биомов в Minecraft);
• рандомизированные алгоритмы: некоторые алгоритмы используют случайность для более эффективного решения задач (например, знаменитый алгоритм рандомизированного восхождения на холм).

Как вы можете себе представить, мир ГПСЧ довольно обширен и сложен и находит применение практически во всех областях науки. Эта статья не претендует на исчерпывающую полноту темы и является не более чем кратким введением в PRNG. Чтобы пойти дальше, есть много ресурсов в Интернете, но Искусство компьютерного программирования — получисловые алгоритмы Д. Кнута и эта виньетка CRAN — отличные отправные точки.

Спасибо за прочтение.

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

Первоначально опубликовано на https://zanotp.com.