复旦大学：《Matlab Math》（双语版）CHAPTER 10 Pseudorandom Number

Matlab Math 随机数 Cleve morler著 陈文斌(wbchen@fudan.edu.cn) 复旦大学2002

Matlab Math Cleve Morler著 陈文斌（wbchen@fudan.edu.cn) 复旦大学2002 随机数

Pseudorandom number 0.95012928514718 MATLAB format long, rand pseudorandom number: 1951, D H Lehmer, Berkeley A random sequence is a vague notion.. in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians

Pseudorandom Number format long; rand 0.95012928514718 pseudorandom number: A random sequence is a vague notion …. in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians… 1951, D.H. Lehmer, Berkeley

An Extended Theory of Lucas Functions By D. H Lehmer Here is a page from Int roduction Lehmer's famous It is ore than half a century since the appearance of Lucas meso 7h;dF“ct。:r; QW.s SimpL票6nt dissertation on the functions named after 194239,289-821·(1878) recurring series of the second order is a study of the two the french sy血 metric functiong (141)7n(a-,”)/(e mathematician edouard of the roots of the quadratic equation; ',a"+, e-b) (1,2) x2. Lucas(1842-1891).It with constant relatively prime integral coefficients. The results of his investigations are partly algebraic and partly number. subsequently appeared thoorotio, The algebraic rosulta are unchanged if the restrictions in Annals of which he puts on P and o are renoved by letting these const ants be Mathematics and as a any real or complex numbers, The fundamental character of U and Pa is well portrayed in the numerous developments and rel ations monograph published that involve as special cages the trigonometric, hyperbolic, cyclo- tomic and logarit hnic funotions.. The algebraic theory is based on in Hamburg by lutcke the difference equations Wulff both in 1930 (1.2) Un.2 -PUn, 1-9Jn and n 2.PV.1-gFn From the algebraic theory Lucas builds up the number- t heoretic properties, of U and 7n by changing his equations to congruences In this part of the development it becomes necessary to consider the

Here is a page from Lehmer's famous dissertation on the functions named after the French mathematician Edouard Lucas (1842-1891). It subsequently appeared in Annals of Mathematics and as a monograph published in Hamburg by Lutcke & Wulff, both in 1930

Lehmer's algorithm Multiplicative congruential algorithm: HE& a, c,m 种子:x0 ki=axk +c mod m 例如:a=13,c=0,m=31,x0=1,输出 11314271061622729538 周期:m-1。可以通过除以m来得到[0,1的一致分布的数 0.03230.4194045160.87100.32260.19350.5161 最小值:1/31,最大值:30/31

Lehmer's Algorithm Multiplicative congruential algorithm: 整数 a,c,m 种子： 0 x xk 1  axk  c mod m 1 13 14 27 10 6 16 22 7 29 5 3 8 例如：a=13, c=0, m=31, x0=1，输出： 周期：m－1。可以通过除以m来得到[0,1]的一致分布的数 0.0323 0.4194 0.4516 0.8710 0.3226 0.1935 0.5161… 最小值：1/31,最大值：30/31

IBMS Algorithm 在1960年IBM主机系统的数学库包括随机数生成器: RND(RNDU:a=65539,c=0,m=231 用32位的整数字长,modm运算可以快速进行,同时由 于a=2^16+3,乘a也可以通过移位和加法进行 +2=(20+3)x1=(20+3)2x =(2+6*20+9)xk [6*(20+3)-9]x 6* 9x 从这里可以看出,由RNDU生成的三个随机数之间有很 强的相关性

IBM's Algorithm 在1960年IBM主机系统的数学库包括随机数生成器： RND(RNDU): 31 a  65539, c  0,m  2 用32位的整数字长，mod m运算可以快速进行，同时由 于a=2^16+3,乘a也可以通过移位和加法进行。 k k k k k x x x x x [6*(2 3) 9] (2 6*2 9) (2 3) (2 3) 16 32 16 16 2 1 16 2             k k k x 6* x 9x 2  1  从这里可以看出，由RNDU生成的三个随机数之间有很 强的相关性

IBMS Algorithm 0.5 MATLAB -0.5 randgui randutx

IBM's Algorithm -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 randgui randutx

Matlab's algorithm a=75=16807.c=0.m=23-1=2147483647 S.K. Park and K. W. Miller "Random number generators: Good ones are hard to find", Comm ACM 31(1988), issue 10 MATLAB randgui randt 早期 Matlab中的rand生成形似km的所有的实数,最小是: l/(2^31-1)最大是m-1)m=1-1/(2^31-1),大概2亿多个数

Matlab's Algorithm 7 16807, 0, 2 1 2147483647 5 31 a   c  m    S.K.Park and K.W.Miller "Random number generators: Good ones are hard to find" ,Comm ACM 31(1988),issue 10 randgui randtx 早期Matlab中的rand生成形似k/m的所有的实数，最小是： 1/(2^31-1),最大是(m-1)/m=1-1/(2^31-1)，大概2亿多个数

Matlab's algorithm 1995年, Matlab引入了一种完全不同的随机数生成器。 George Marsaglia, Florida State University, an author of the classic analysis of random number generators, Random numbers fall mainly in the planes", (Proc. Nat. Acad. Sci 61(1968) 这个算法是特别为浮点随机数设计的 新的生成器有35个字。其中32个字存 浮点数乙剩下3个包括一个整数指标i (1~32),一个随机整数j,和一个 orrow 标志b

Matlab's Algorithm 1995年，Matlab引入了一种完全不同的随机数生成器。 George Marsaglia, Florida State University, an author of the classic analysis of random number generators, "Random numbers fall mainly in the planes" ,(Proc. Nat.Acad.Sci. 61(1968) 这个算法是特别为浮点随机数设计的。 新的生成器有35个字。其中32个字存 浮点数z,剩下3个包括一个整数指标i, （1～32), 一个随机整数j, 和一个 "borrow"标志b

Matlab's Algorithm subtract with borrow +20 bi,计+5,计+20都是mod32 +5 如果zi是正的,b在下一步设为0;如果是负的,那么 z计+1变为正的,b在下一步设为2(-53)lp) MATLAB ulp unit in the last place for format hex: 1/2 floating point numbers slightly less then 1 1/2+eps 1/2+eps/2 将生成[/2,1中全部的数, Marsaglia: almost2140[1/4,1/2]一半 [l/8,1/4]:四分之

Matlab's Algorithm “subtract with borrow” z z z b i  i20  i5  i,i+5,i+20都是mod 32 如果z_i是正的, b在下一步设为0；如果是负的，那么 z_i+1变为正的，b在下一步设为2^(-53) (ulp) format hex; 1/2 1/2+eps 1/2+eps/2 ulp: unit in the last place for floating point numbers slightly less then 1 Marsaglia: 1430 almost 2 将生成[1/2,1]中全部的数， [1/4,1/2]:一半 [1/8,1/4]:四分之一