Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

RANDOM NUMBERS

Previous Up Next

ITEM 25 (Schroeppel):

Random number generators, such as Rollo Silver's favorite, which use SHIFTs and XORs, and give as values only some part of their internal state, can be inverted. Also, the outputs may often be used to obtain their total internal state. For example, 2 consecutive values from Rollo's suffice to allow prediction of its entire future. Rollo's is: 
RANDOM:  MOVE A,HI        ;register A gets loaded with "high" word
         MOVE B,LO        ;register B gets loaded with "low" word
         MOVEM A,LO       ;register A gets stored in "low" word
         LSHC A,35.       ;shift the 72-bit register AB left 35
         XORB A,HI        ;bitwise exclusive-or of A and HI replaces both
[PDP-10 Info]

This suggests a susceptibility to analysis of mechanical code machines.

See LOOP DETECTOR item in FLOWS AND ITERATED FUNCTIONS section.

ITEM 26 (? via Salamin):

A mathematically exact method of generating a Gaussian distribution from a uniform distribution: let x be uniform on [0,1] and y uniform on [0, 2 pi], x and y independent. Calculate r = sqrt(-log x). Then r cos y and r sin y are two independent Gaussian distributed random numbers.

ITEM 27 (Salamin):

PROBLEM: Generate random unit vectors in N-space uniform on the unit sphere. SOLUTION: Generate N Gaussian random numbers and normalize to unit length.

Previous Up Next