Генератор случайных чисел на Prolog

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 10 мес. назад.

  • Автор
    Сообщения
  • #1980

    questioner
    Участник

    Здравствуйте, нужна программа на Turbo Prolog, реализующая генерацию псевдослучайных чисел (ГПСЧ) при помощи линейного конгруэнтного датчика. Числа задаются формулой:

    X{k+1} = (A * X{k} + C) mod M.
    Где А, С и M - константы.

    Для генерации последовательности нужно начальное значение X{0}, называемое затравкой.
    Нужно два варианта функции, первая принимает значение затравки, а вторая – берет в качестве него значение, зависящее от текущего момента времени.

  • #1981

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

    Кроме того, есть рекомендации на счет параметров генератора, я думаю их стоит фиксировать, как это делается в большинстве стандартных библиотек:

    linear_congruent(A, C, M, PrevX, X):-
      X is (A * PrevX + C) mod M.
    
    linear_congruent(PrevX, X):-
      linear_congruent(1664525, 1013904223, 2147483647, PrevX, X).

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

    Метод конгруэнтного датчика требует затравку, но это не означает, что предыдущее случайное число должно передаваться постоянно. Библиотеки других языков программирования используют для сохранения предыдущего сгенерированного значения статические переменные функции. Однако, на языке Prolog вместо этого используется база данных.

    Нужно соответствующим образом описать базу. В Turbo и Visual Prolog это должно быть сделано в разделе database, а в SWI и GNU – при помощи предиката dynamic:

    :- dynamic 
      linear_congruent_seed/1.

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

    remove_seeds:-
      retract(linear_congruent_seed(_)), !, remove_seeds;!.
      
    add_seed(Seed):-
      assert(linear_congruent_seed(Seed)).
      
    get_seed(Seed):-
      linear_congruent_seed(Seed).
      
    set_seed(Seed):-
      remove_seeds, add_seed(Seed).

    Функция удаления записи выполняет retract до тех пор, пока это возможно. Такое поведение реализовано на случай попадания нескольких затравок в базу, к которому могли привести повторные вызовы add_seed. Исключить возможность такой ошибки можно вынесением генерации в отдельный модуль, не экспортирующий функцию add_seed.

    При отладке возможность явного задания начального значения генератора может быть удобным, т.к. позволяет повторить эксперименты, ведь ГПСЧ является детерминированным. Ответственность за инициализацию генератора числом, зависящим от момента времени можно возложить на пользователя – ему достаточно передать соответствующий параметр в set_seed. Функции для работы со временем сильно отличаются в различных диалектах, например на SWI Prolog для этой цели используется get_time, возвращающая дробное число секунд, прошедших с 1970 года:

    set_time_as_seed:-
      get_time(FloatStamp), IntStamp is integer(FloatStamp),
      set_seed(IntStamp).

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

    Функции ГСПЧ:

    • если затравка есть в базе – выполняет генерацию и результат не только возвращается, но и заменяет старое значение в базе;
    • если затравки не было – она добавляется (вызывается set_time_as_seed, но мог бы выставляться, например, ноль) и функция вызывается рекурсивно

    linear_congruent(X):-
      get_seed(Seed), !,
      linear_congruent(Seed, X),
      set_seed(X).
    linear_congruent(X):-
      set_time_as_seed, 
      linear_congruent(X).

Для ответа в этой теме необходимо авторизоваться.