Không, trên đời chẳng có gì là ngẫu nhiên cả!

Ta sẽ có 3 khái niệm chung trong PRNG:

• Seed: giá trị khởi tạo của PRNG.
• Internal State: trạng thái của PRNG, lưu trữ các biến số để có thể dự đoán được giá trị và trạng thái tiếp theo của PRNG.
• Period: chu kỳ của random, random sẽ lặp lại mỗi khi chu kỳ kết thúc.

2. Random Distribution Types

Tuỳ vào mục đích sử dụng, Random() trong các ngôn ngữ lập trình sẽ sinh ra các số ngẫu nhiên theo các phân phối khác nhau.

Thông thường nhất là phân phối đều (Uniform Distribution) với xác suất xuất hiện các số là gần như nhau, hoặc phân phối chuẩn (Normal Distribution) để sinh ra các giá trị xung quanh một giá trị nào đó.

Đó, rõ ràng Random() không phải là dùng tuỳ tiện được mà phải phụ thuộc vào việc vào chúng ta muốn dữ liệu như thế nào nữa.

3. PRNG Algorithms

Có rất nhiều thuật toán trong PRNG, các bạn có thể tham khảo thêm tại đây Trong bài này mình sẽ giới thiệu qua 3 thuật toán được sử dụng trong các ngôn ngữ lập trình.

3.1. Linear Congruential Generator (LCG)

Đây là thuật toán sinh ngẫu nhiên cổ điển nhất và phổ biến nhất được sử dụng trong PRNG. LCG là thuật toán built-in trong Pascal, C/C++, Java và C#.

LCG rất đơn giản, rất trực quan và dễ hiểu, sử dụng chỉ một hàm:

Xn+1=(aXn+c) mod mX_{n+1} = (aX_{n} + c)\ mod\ m Xn+1​=(aXn​+c) mod m

Trong đó:

• m, 0<mm,\ 0 < mm, 0<m: Mô đun, thường sẽ là một số đủ lớn, ví dụ 232,231−1,248,2642^{32}, 2^{31} - 1, 2^{48}, 2^{64}232,231−1,248,264
• a, 0<a<ma,\ 0 < a < ma, 0<a<m: Hằng số nhân mutiplier
• c, 0≤c<mc,\ 0 \leq c < mc, 0≤c<m: Hằng số cộng thêm increment
• X0, 0≤X0<mX_{0},\ 0 \leq X_{0} < mX0​, 0≤X0​<m: seed, giá trị khởi tạo

Chu kỳ của LCG lớn nhất là m, và để LCG sinh ra tất cả các giá trị trong chu kỳ với mọi giá trị khởi tạo (full-period) thì sẽ cần những điều kiện ràng buộc như sau (các bạn hãy thử tự chứng minh bằng toán học xem sao :

• mmm và ccc là nguyên tố cùng nhau.
• a−1a-1a−1 chia hết cho mọi thừa số nguyên tố của mmm.
• a−1a-1a−1 chia hết cho 4 nếu mmm chia hết cho 4.

Về giá trị mặc định của các hằng số với các ngôn ngữ lập trình khác nhau, các bạn có thể tham khảo thêm tại đây.

Dưới đây là vài ví dụ về LCG:

Ưu điểm: Rất nhanh và tốn ít bộ nhớ (32 hoặc 64 bits).

Nhược điểm: Tính chất ngẫu nhiên chưa cao, và do đó với những hệ thống thực sự cần độ ngẫu nhiên rất cao, người ta không khuyến khích sử dụng LCG. Và thay vào đó là sử dụng Mersenne Twister (sẽ được nói tới trong phần sau).

3.2. Multiply with Carry (MWC)

Để tạo ra chu kỳ random lớn hơn, George Marsaglia đã đề xuất một thuật toán PRNG khác với tên gọi Multiply with Carry (MWC). Trong MWC thì ta sẽ dùng một set gồm từ hai cho tới hàng ngàn giá trị cho seed.

Và chu kỳ của MWC cũng rất lớn, từ 2602^{60}260 cho tới 220000002^{2000000}22000000, nghĩa là lớn hơn rất rất nhiều so với LCG.

Trong MWC chúng ta sẽ có một giá trị r, gọi là lag của MWC. Và cũng giống như LCG, chúng ta cũng sẽ có mutiplier và mô đun, nhưng sẽ không còn increment, mà thay vào đó là một giá trị carry. Công thức sẽ như sau:

xn=(axn−r+cn−1) mod b, n≥rx_{n} = (ax_{n-r} + c_{n-1})\ \ mod \ \ b,\ n\geq r xn​=(axn−r​+cn−1​) mod b, n≥r

Trong đó, cũng giống như trên, a sẽ là mutiplier, và ở đây b sẽ là mô đun, thường là 2322^{32}232. Điểm khác biệt là giá trị carry c, giá trị này sẽ được dùng để tính toán giá trị x tiếp theo. Công thức của c là:

cn=⌊axn−r+cn−1b⌋, n≥rc_{n} = \left\lfloor \frac{ax_{n-r} + c_{n-1}}{b} \right\rfloor,\ n\geq r cn​=⌊baxn−r​+cn−1​​⌋, n≥r

người ta thường chọn giá trị của a sao cho ab−1ab-1ab−1 là Safe Prime, tức ab−1ab-1ab−1 và ab2−1\frac{ab}{2}-12ab​−1 đều là nguyên tố, khi đó chu kì của MWC sẽ là ab2−1\frac{ab}{2}-12ab​−1

Các bạn có thể tham khảo bảng giá trị chu kì của MWC như dưới đây:

3.3 Mersenne Twister

Mersenne Twister là một thuật toán PRNG được Makoto Matsumoto và Takuji Nishimura phát triển vào năm 1997. Đây là một thuật toán thực sự tuyệt vời. Rất nhanh và tạo ra được dãy số với chất lượng ngẫu nhiên rất cao.

Mersenne Twister được sử dụng như là built-in PRNG cho Python, Ruby, PHP và R.

Cái tên Mersenne Twister được chọn vì chu kì của số ngẫu nhiên tạo ra bởi thuật toán này luôn là một số nguyên tố Mersenne

FYI: Số nguyên tố Mersenne có dạng Mn=2n−1M_{n} = 2^{n} - 1Mn​=2n−1, ví dụ 31.

Số nguyên tố Mersenne thường được sử dụng trong thuật toán sinh random là 219937−12^{19937} - 1219937−1, đó cũng là nguồn gốc của cái tên MT19937 - standard implement của Mersene Twister. Kết quả đưa ra số tự nhiên 32 bits.

Ưu điểm:

• Đưa ra được dải số rất lớn 219937−12^{19937} - 1219937−1
• Pass rất nhiều các bài kiểm tra về tính ngẫu nhiên, có thể nói MT là một thuật toán vô cùng tốt.

Nhược điểm: MT có nhược điểm cơ bản về performance, có thể coi là chậm và tốn bộ nhớS

3.3a. Algorithm Overview

Một cách tổng quát, thuật toán Mersenne Twister được triển khai bằng đệ quy, biểu thức như sau:

xk+n:=xk+m ⊕ ((xkw−r ∣ xk+1r)A)\mathbf{x_{k+n}} := \mathbf{x_{k+m}} ~~ \oplus ~((\mathbf{x_{k}^{w-r}} \mid ~\mathbf{x_{k+1}^r})\mathbf{A}) xk+n​:=xk+m​ ⊕ ((xkw−r​ ∣ xk+1r​)A)

trong đó:

• www: word-length, độ dài của vector đầu ra x
• x\mathbf{x}x: là một vector www bits, chính là đầu ra của MT
• nnn: Độ dài dãy xi\mathbf{x_i}xi​
• rrr: điểm chia vector ra làm 2 phần, phần trái tương ứng với w−rw-rw−r bits (upper bits), và phần phải tương ứng với rrr bits (lower bits)
• mmm: một offset dùng cho tính toán
• AAA: ma trận vuông kích thước w×ww \times ww×w
• xkw−r\mathbf{x_k^{w-r}}xkw−r​: w-r bit bên trái của xk\mathbf{x_k}xk​
• xk+1r\mathbf{x_{k+1}^r}xk+1r​: r bit bên phải của xk+1\mathbf{x_{k+1}}xk+1​
• xkw−r ∣ xk+1r\mathbf{x_{k}^{w-r}}~ \mid ~\mathbf{x_{k+1}^r}xkw−r​ ∣ xk+1r​: phép toán OR, chính là ghép w-r bit bên trái của xk\mathbf{x_k}xk​ với r bit bên phải của xk+1\mathbf{x_{k+1}}xk+1​ để đưa ra một vector độ dài w
• ⊕\oplus⊕: phép toán XOR

Với điều kiện ràng buộc 2nw−r−12^{nw - r} - 12nw−r−1 là số nguyên tố Mersenne.

📌 Các bạn lưu ý là mình viết vector và ma trận bằng kí tự in đậm, còn số là ký tự in thường.

Biểu thức trên chính là biểu thức Twist trong MT, mình hay gọi nó là biểu thức xoắn quẩy =))

Ma trận A được chọn lựa sao cho phép nhân ma trận trở nên đơn giản và nhanh chóng:

A=010…0001…0………⋱…000…1aw−1aw−2aw−3…a0\mathbf{A} = \left\begin{matrix} 0 & 1 & 0 & \ldots & 0\\ 0 & 0 & 1 & \ldots & 0\\ \ldots & \ldots & \ldots & \ddots & \ldots \\ 0 & 0 & 0 & \ldots & 1\\ a_{w-1} & a_{w-2} & a_{w-3} & \ldots & a_{0}\\ \end{matrix} \right A=⎣⎡​00…0aw−1​​10…0aw−2​​01…0aw−3​​……⋱……​00…1a0​​⎦⎤​

Theo đó khi nhân một vector x=xw−1,xw−2,…,x0\mathbf{x} = x_{w-1}, x_{w-2},\ldots,x_{0}x=xw−1​,xw−2​,…,x0​ với AAA thì ta có thể tính toán đơn giản chỉ bằng XOR và dịch bit như sau:

xA={x ≫ 1x0=0 (x ≫ 1)⊕ax0=1 \mathbf{xA} = \left\{ \begin{matrix} \mathbf{x}\gg1 & x_0=0~~~ \\ (\mathbf{x}\gg1) \oplus \mathbf{a} & x_0=1~~~ \end{matrix} \right. xA={x ≫ 1(x ≫ 1)⊕a​x0​=0 x0​=1 ​

Trong đó a=aw−1,aw−2,…,a0\mathbf{a} = a_{w-1}, a_{w-2},\ldots,a_{0}a=aw−1​,aw−2​,…,a0​ chính là vector hàng cuối cùng của ma trận AAA. Trông có vẻ vi diệu nhưng thực chất vẫn là nhân ma trận mà thôi, các bạn có thể khai triển thử và kiểm chứng kết quả.

Sau khi đã xây dựng được dãy các vector x0,x1,…,xn−1\mathbf{x_0}, \mathbf{x_1}, \ldots, \mathbf{x_{n-1}}x0​,x1​,…,xn−1​, để điều chỉnh phân phối của kết quả, người ta chọn một ma trận TTT với kích thước w×ww \times ww×w và nhân tiếp vào để ra một vector z=xT\mathbf{z=xT}z=xT. Quá trình này gọi là tempering transform.

Tương tự như trên, để đơn giản hóa cho việc tính toán, người ta chọn T sao cho kết quả có thể nhận được chỉ bằng các phép XOR, AND và dịch bit thông thường

y:=x⊕((x≫u)&d)y:=y⊕((y≪s)&b)y:=y⊕((y≪t)&c)z:=y⊕(y≫l)\begin{matrix} \mathbf{y} := \mathbf{x} \oplus ((\mathbf{x} \gg u) \& \mathbf{d}) \\ \mathbf{y} := \mathbf{y} \oplus ((\mathbf{y} \ll s) \& \mathbf{b}) \\ \mathbf{y} := \mathbf{y} \oplus ((\mathbf{y} \ll t) \& \mathbf{c}) \\ \mathbf{z} := \mathbf{y} \oplus (\mathbf{y} \gg l) \end{matrix} y:=x⊕((x≫u)&d)y:=y⊕((y≪s)&b)y:=y⊕((y≪t)&c)z:=y⊕(y≫l)​

trong đó:

• l,s,t,ul, s, t, ul,s,t,u: bitshift, số nguyên, thể hiện số bit dịch đi
• d,b,c\mathbf{d, b, c}d,b,c: bitmask, là các vector độ dài www

Và cuối cùng là đưa www bit cuối cùng của z\mathbf{z}z ra làm kết quả.

Nếu thấy hơi xoắn não, các bạn có thể xem hình bên dưới để hiểu một cách trực quan hơn cách dịch trái-phải của quá trình trên:

Initialization

Ta cần bước khởi tạo các giá trị x\mathbf{x}x trước khi thuật toán bắt đầu. Với một giá trị đầu vào seed gán cho x0\mathbf{x_0}x0​.

xi=f×(xi−1⊕(xi−1≫(w−2)))+ix_i = f \times (x_{i-1} \oplus (x_{i-1} \gg (w-2))) + ixi​=f×(xi−1​⊕(xi−1​≫(w−2)))+i

f là một hằng số. Với MT19937 thì f=1812433253f=1812433253f=1812433253

💡 Vậy là ta có cái nhìn tổng quan về Mersenne Twister, hãy ngồi xuống, nghe một ca khúc và làm một ly cà phê trước khi đến với phần code

3.3b. MT19937

MT19937 là standard implement của Mersene Twister, sử dụng với các tham số như sau:

• (w,n,m,r)(w, n, m, r)(w,n,m,r) = (32, 624, 397, 31)
• a\mathbf{a}a = $ 9908B0DF_{16} $
• (u,d)(u, \mathbf{d})(u,d) = (11,FFFFFFFF16)(11, FFFFFFFF_{16})(11,FFFFFFFF16​)
• (s,b)(s, \mathbf{b})(s,b) = (7,9D2C568016)(7, 9D2C5680_{16})(7,9D2C568016​)
• (t,c)(t, \mathbf{c})(t,c) = (15,EFC6000016)(15, EFC60000_{16})(15,EFC6000016​)
• lll = 18
• fff = 1812433253

MT19937 implement code:

def_int32(x):# Get the 32 least significant bits.returnint(0xFFFFFFFF& x)classMT19937:def__init__(self, seed):# Initialize the index to 0 self.index =624 self.mt =0*624 self.mt0= seed # Initialize the initial state to the seedfor i inrange(1,624): self.mti= _int32(1812433253*(self.mti -1^ self.mti -1>>30)+ i)defextract_number(self):if self.index >=624: self.twist() y = self.mtself.index# Right shift by 11 bits y = y ^ y >>11# Shift y left by 7 and take the bitwise and of 2636928640 y = y ^ y <<7&2636928640# Shift y left by 15 and take the bitwise and of y and 4022730752 y = y ^ y <<15&4022730752# Right shift by 18 bits y = y ^ y >>18 self.index = self.index +1return _int32(y)deftwist(self):for i inrange(624):# Get the most significant bit and add it to the less significant# bits of the next number y = _int32((self.mti&0x80000000)+(self.mt(i +1)%624&0x7fffffff)) self.mti= self.mt(i +397)%624^ y >>1if y %2!=0: self.mti= self.mti^0x9908b0df self.index =0 a = MT19937(1000)print a.extract_number()print a.extract_number()print a.extract_number()print a.extract_number()

4. Conclusion

Vậy là rõ ràng random() không phải là ngẫu nhiên, đó đều là kết quả do máy tính (hay chính xác hơn là con người) tạo ra mà thôi.

Nếu biết được trạng thái hiện tại của thuật toán và seed, thì hoàn toàn chúng ta có thể tính toán được trạng thái tiếp theo, tức kết quả tiếp theo của random(). Tuy nhiên điều này đôi khi không dễ dàng và cần một số những điều kiện nhất định, đôi khi thấy xuất hiện trong các cuộc thi CTF.

Vậy nên, nếu bạn chưa có bạn gái, hay chưa giàu, hay chưa trúng Vietlot, hãy luôn tin rằng đó chỉ là do chưa tới lượt mà thôi, ngày ngày làm một tấm vé, dù sớm hay muộn thì may mắn cũng sẽ đến.

Good luck!

5. References

• Random numbers: generators and distributions
• Artificial intelligence for humans volume 1
• List of random number generators
• Linear Congruential Generator
• Multiply with Carry
• Mersenne Twister
• Mersenne Twister Random Number Generator

Vòng quay random số tương tự như vòng quay may mắn và vòng quay chữ cái A-Z nhưng với mục đích để chọn ra số ngẫu nhiên

Trang web này chỉ thu thập các bài viết liên quan. Để xem bản gốc, vui lòng sao chép và mở liên kết sau:Random() có thực sự ngẫu nhiên ?