[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Random Numbers in Franz



Original-Date: 29-Nov-82 15:56:09-PST (Mon)
Date: Sun, 29 Nov 82 23:56:09 GMT
From: alice!sola!mitch
Subject: Random Numbers in Franz
To: alice!ucbvax!franz-friends@Berkeley

In general, it is very bad practice to compute a random number between 0
and n by any expression such as (mod (random) n).  In fact, Franz's
random function does exactly that, returning the number generated by the
C function rand(3) modulo n.  This technique uses only the rightmost 
bits of successive calls to rand, and the righmost n bits of congruential
sequences (like that returned by rand(3)) have a period of AT MOST 2**n
(See Knuth vol.2 p. 12).  So using the rightmost two bits will indeed give
you sequences of at most period 4.  (If your lisp doesn't have this 
behavior, you're not using the standard rand.)

A better way to do it is to use the high order bits, by dividing the entire
range up into n pieces and then seeing where you fall.  (This method is
biased if n is of the same order as the range, though.)

The code I use is:


(or (getd '$old-random) (putd '$old-random (getd 'random)))

(defun random n
  (cond ((eq n 0) ($old-random))
	((fix (quotient (boole 1 ($old-random) #o 7777777777)
			(quotient #o 7777777777 (arg 1)))))))

		Mitch Marcus