Генерировать случайные числа без использования каких-либо внешних функций

Это были вопросы, заданные в одном из интервью, которые я недавно посетил.

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

public static int rand(int low, int high) {
    return low + (int)(Math.random() * (high - low + 1));
}

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

Ответы

Ответ 1

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

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

Реализация псевдокода может выглядеть следующим образом:

long a = 25214903917;   // These Values for a and c are the actual values found
long c = 11;            // in the implementation of java.util.Random(), see link
long previous = 0;

void rseed(long seed) {
    previous = seed;
}

long rand() {
    long r = a * previous + c;
    // Note: typically, one chooses only a couple of bits of this value, see link
    previous = r;
    return r;
}

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

Использование чего-то вроде текущего времени (хорошо в большинстве случаев, не связанных с безопасностью, таких как игры)
Использование аппаратного шума (полезно для критически важной для безопасности случайности)
Использование постоянного числа (полезно для отладки, поскольку вы получаете всегда одну и ту же последовательность)
Если вы не можете использовать какую-либо функцию и не хотите использовать постоянное семя, и если вы используете язык, который позволяет это, вы также можете использовать некоторую неинициализированную память. В C и С++, например, определите новую переменную, не присваивайте ей и не используйте ее значение для засеивания генератора. Но обратите внимание, что это далеко не "хорошее семя" и только хак для выполнения ваших требований. Никогда не используйте это в реальном коде.

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

Ответ 2

Здесь я предлагаю некоторые источники с комментариями, может быть, вы сочтете полезным:

Системное время: монотонный в день плохой случайный. Быстро, просто.
Точка мыши: случайная, но не полезная для автономной системы.
Raw Socket/Local Network (Информация о пакете): Хорошее Случайное Техническое и трудоемкое время - Возможность моделирования режима атаки для уменьшения случайности.
Некоторый ввод текста с перестановкой: быстрый, общий и хороший тоже (на мой взгляд).
Сроки прерывания из-за клавиатуры, дисковода и других событий: Обычный путь - склонность к ошибкам, если не используется осторожно.
Другой подход заключается в подаче аналогового шумового сигнала: например, temp.
/proc данные файла. В системе Linux. Я чувствую, что вы должны это использовать.

/proc/sys/kernel/random: Этот каталог содержит различные параметры, управляющие работой файла /dev/random.

Специальные файлы символов /dev/random и /dev/urandom (присутствующие с Linux 1.3.30) предоставляют интерфейс для генератора случайных чисел ядра.

попробуйте эти комбаты:
```
$cat /dev/urandom   
```
и
```
$cat /dev/random
```
Вы можете написать функцию чтения файла, которая читается из этого файла.

Прочитайте (также предлагает): Является ли rand из /dev/urandom безопасным для ключа входа?

Ответ 3

Учитывается ли System.currentTimeMillis() как внешний? Вы всегда можете получить это и вычислить mod на некоторое максимальное значение:

int rand = (int)(System.currentTimeMillis()%high)+low;

Ответ 4

Вы можете использовать адрес переменной или объединить адрес большего числа переменных, чтобы сделать более сложным...

Ответ 5

Вы можете получить почти случайность (фактически хаотичную и определенно не единообразную *) из логистической карты x = 4x(1-x), начиная с "нерационального" x между 0 и 1.

"Случайность" появляется из-за ошибок округления на краю точности представления с плавающей запятой.

(*) Вы можете отменить перекос, если знаете, что он есть.

Ответ 6

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

Ответ 7

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

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

Вы можете сделать это только с помощью обычных арифметических операций Java и/или побитовых операций, поэтому внешние функции не требуются.

Ответ 8

Пуассоновский случайный генератор

Предположим, что мы начинаем с ожидаемого значения "v" случайных чисел. Тогда, чтобы сказать, что последовательность неотрицательных целых чисел удовлетворяет распределению Пуассона с ожидаемым значением v, означает, что над подпоследовательностями среднее значение (среднее) значения будет отображаться "v". Распределение Пуассона является частью статистики, и подробности можно найти в википедии. Но здесь главное преимущество использования этой функции: 1. Генерируются только целые значения. 2. Среднее значение этих целых чисел будет равно значению, которое мы первоначально предоставили.

Это полезно в приложениях, где дробные значения не имеют смысла. Как и количество самолетов, прибывающих в аэропорт в 1 мин, составляет 2,5 (это не имеет смысла), но это означает, что через 2 минуты прибудет 5 планов.

int poissonRandom(double expectedValue) {
  int n = 0; //counter of iteration
  double limit; 
  double x;  //pseudo random number
  limit = exp(-expectedValue);
  x = rand() / INT_MAX; 
  while (x > limit) {
    n++;
    x *= rand() / INT_MAX;
  }
  return n;
}

Линия

rand() / INT_MAX

должно генерировать случайное число между 0 и 1. Таким образом, мы можем использовать время системы. Секунды /60 будут служить цели. Какая функция, которую мы должны использовать, полностью зависит от приложения.