Эта функция чистая? (Случайное вычисление, детерминированный результат)

Question

A чистая функция определяется как функция, которая:

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

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

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

Answer 1

Нет, я так не думаю.

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

1. Это псевдо-RNG.Это означает, что оно имеет N-битное состояние, и каждый раз, когда генерируется новое случайное число, состояние обновляется.Таким образом, есть побочный эффект - изменение состояния ГСЧ.

2. Истинный генератор случайных чисел, который извлекает случайные биты из источника энтропии.Опять же, пул будет использован и может быть исчерпан - вот признак не чистой функции.

Answer 2

«Генератор случайных чисел» не может быть чистой функцией, пока вся информация, необходимая ему для генерации случайного числа, не будет передана ему заранее.Если генератор использует что-то еще (например, системные часы или файловую систему), генератор не будет чистым.Например, чистые функции включают в себя:

• хеш-функции.
• Функции, которые принимают начальное число и выводят случайное число и новое начальное число.
• Функции, которыевозьмите внутреннее состояние и выведите случайное число и новое внутреннее состояние.

См. мой раздел " Проекты для PRNG ".