Tại sao không lấy modulo 2^w (với w là số bit word của máy tính) trong phương pháp tạo số ngẫu nhiên LCG?

[newbie_lap_trinh (newbie lập trình)]

Mọi người có thể giải thích rõ hơn cho mình chỗ:
"The reason is that when m=w,the right-hand digits of Xn are much less random than the left-hand digits"

[rogp10]

Với dãy vô hạn tuần hoàn X(seed, f) = {X[0] = seed, X[i+1] = f(X[i])}, ta định nghĩa chu kì ω(X) = min(f ∈ N* : X[i] = X[i+f]). Một trong những đặc điểm ta mong muốn là ω(X(s, v => (a*v + b) mod m)) = ω(X => Y: v => v mod m’).

Đoạn này nói về nhược điểm cố hữu của LCG: chuỗi modulo m’ | m có chu kì là m’ < m, nhưng chưa phải là chí tử. Giữa các số liên tiếp mới là thốn.

[tntxtnt]

thì em cứ thử tính đi là thấy liền vấn đề nghiêm trọng:

ví dụ seed = 1, a = 3, b = 0:
r0 = 1
r1 = 3
r2 = 9
r4 = 27
r5 = 81
r6 = 243
r7 = 729
r8 = 2187
r9 = 6561
v.v…

bạn sẽ thấy số cuối cùng ko bao giờ là số chẵn. và nó theo chu kì đều đặn: 1-3-9-7 ko có ngẫu nhiên gì hết. Tương tự ở hàng chục, toàn là số chẵn. Trong khi các số ở hàng cao hơn thì khó đoán hơn, ví dụ ở hàng trăm đã thấy khó đoán: 0 0 0 0 0 2 7 1 5 6 0 1 4 3 9 v.v… Vì trong phép nhân, ví dụ abc*d = a’b’c’ thì
c’ = cd,
b’ = bd + c’ / 10 = bd + cd / 10,
a’ = ad + b’ / 10 = ad + (bd + cd / 10) / 10
thì bạn sẽ thấy ngoài d ra thì c’ chỉ lệ thuộc vào c, còn b’ lệ thuộc vào b và c, a’ lệ thuộc vào a, b, c, như vậy a’ sẽ ngẫu nhiên tốt hơn vì có nhiều “nguồn ngẫu nhiên” hơn.

còn b khác 0 thì cũng gặp vấn đề chẵn lẻ tương tự ở số cuối cùng, ví dụ nếu a lẻ b chẵn thì chữ số cuối cùng luôn là số lẻ, hoặc b lẻ thì nó chẵn lẻ đan xen. Nhân nhiều quá nó tràn số phải mod m nào đó thì có thêm được 1 tí ngẫu nhiên nhưng chữ số cuối cùng vẫn tương đối dễ đoán hơn những chữ số cao hơn như hàng triệu chẳng hạn.