Как работает генератор случайных чисел?

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

Есть простейшие методы, например:

Конгруэнтный метод

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

формула выглядит так: v_(i+1) = (v_(i) * a + c)mod(m) (нижнее подчеркивание обозначает индекс, символы a,c,m можно выбирать произвольно, но чем больше эти значения, тем больше элементов поля можно построить, соответственно. Для лучшего эффекта можно выбрать a,m - взаимнопростыми). Для перехода к равномерному случаю [0,1] - дели все выражение на m.

Есть и кое-что более сложное:

Метод инверсий

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

Метод смеси

Он основывается на утверждении, что

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

Несложный алгоритм, состоящий всего из 2х пунктов, в каждом из которых- генерация случайного значения из равномерного распределения на [0,1], это простая задача, это делать мы уже умеем(обрати внимание на первый метод ответа)

Сложность алгоритма, кстати O(1) - достаточно просто в плане вычислений.

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