Números pseudo-aleatórios em LISP

Implementação em LISP de um gerador de números pseudo-aleatórios

Uma das formas de gerar números com uma distribuição uniforme num intervalo é usando o método de congruências lineares1. Vejamos então como implementar um gerador de números pseudo-aleatórios que gera números inteiros entre 0 e m com uma distribuição uniforme latex2png equation.

A ideia é gerar uma sucessão de números com a forma latex2png equation onde2 latex2png equation Ao valor de latex2png equation dá-se o nome de semente porque é o primeiro termo da sucessão e é usado como input para o termo seguinte. Note-se que para um mesmo latex2png equation obtém-se sempre o mesmo latex2png equation.

A sucessão de números assim obtida tem período latex2png equation e o intervalo de variação dos valores da sucessão pode ser ajustado ao intervalo latex2png equation através de latex2png equation

A maneira mais directa é escrever

(defun rand (a c m x)
  (mod (+ (* a x) c) m))
e obtém-se
> (rand 24298 99991 199017 0)

99991

Esta não é a maneira preferível de obter um número aleatório. Queremos obter um número simplesmente fazendo (rand), mas para isso, temos de ter uma maneira de guardar os sucessivos termos da sucessão de modo a que sirvam de sementes para os termos seguintes. Assim vamos definir a variável

(defvar *r-seed* 0)
que inicializa a sucessão de sementes (ou dos próprios números pseudo-aleatórios). Esta é uma variável global e por isso está enquadrada por *. Definimos um substituto para a função anterior como
(defun rand1 ()
  (let ((a 24298)
        (c 99991)
        (m 199017))
    (cond ((<= *r-seed*  199017)
           (setf *r-seed* (mod (+ (* a *r-seed*) c) m)))
          (t
           (setf *r-seed* 0)))))
onde agora os parâmetros a, c e m são locais e estão definidos dentro da função. Assim
> (rand1)

99991

A função rand1 é simples de perceber. Depois de inicializar as quantidades a, c e m verifica se *r-seed* é menor ou igual a 199017, se sim altera o valor de *r-seed* para o novo termo da sucessão através de

(setf *r-seed* (mod (+ (* a *r-seed*) c) m))
se não
(setf *r-seed* 0)

De modo a gerar números aleatórios entre latex2png equation define-se a função

(defun rand (&optional alpha beta)
  (let ((m 199017))
    (cond ((not (and alpha beta))
           (float (/ (rand1) m)))
          (t
           (+ (* (float (/ (rand1) m)) (- beta alpha)) alpha)))))
com dois argumentos opcionais alpha e beta; se não forem dados (rand) gera números com uma distribuição uniforme no intervalo latex2png equation:
> (rand)

0.55237997

> (rand 0 2)

1.1378727

Ref:

1. D. Knuth, TAOCP

2. Master Library da TI Programable 58/59

Palavras chave/keywords: LISP, números pseudo-aleatórios

Última actualização/Last updated: 2014-02-20 [14:39]


1999-2014 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.