Một cỗ máy làm sao "tung xúc xắc" khi bản chất nó tất định — cho cùng đầu vào luôn ra cùng đầu ra? Câu trả lời là một trò khéo léo được thiết kế sẵn: một PRNG (bộ sinh số giả ngẫu nhiên) là thuật toán tất định nhưng tuôn ra dãy trông như ngẫu nhiên. Cứ tưởng tượng một cỗ máy nhào bột: cho vào cùng cục bột, quay cùng số vòng, bạn luôn được đúng cái bánh đó — nhưng thớ bột sau khi nhào thì rối đến mức không ai lần ngược ra vòng quay ban đầu. Ở bài cấu trúc ngẫu nhiên hóa tôi đã dùng ngẫu nhiên để thuật toán nhanh và an toàn hơn — nhưng ngầm tin rằng nguồn ngẫu nhiên là tốt. Bài này mở nguồn ấy ra đo, và tìm thấy mấy vết nứt mà câu "cứ dùng rand()" khéo léo che đi.

Ba trục kéo nhau của một PRNG

Một PRNG nhận một hạt giống (seed) rồi biến đổi qua từng bước để nhả ra dãy số. Cùng seed luôn cho cùng dãy — đó chính là chữ "giả" trong "giả ngẫu nhiên": không có ngẫu nhiên thật, chỉ có một dãy tất định khó lần ra quy luật. Mà tính chất "cùng seed cùng dãy" ấy lại rất đáng quý: nó cho phép tái lập — một mô phỏng hay một test chạy lại y hệt, gỡ lỗi mới nổi.

Chọn PRNG là cân ba trục kéo ngược nhau: tốc độ (nhả một số nhanh cỡ nào), chất lượng (dãy có đều, có sạch mẫu lặp không), và tính không đoán được (nhìn các số đã ra có suy ra số kế không — điều bắt buộc cho mật mã). Không bộ sinh nào ăn trọn cả ba; bài này đo từng trục một.

Tốc độ: chênh nhau vài lần

Tôi đo thông lượng của ba nguồn: xorshift64* (một PRNG nhanh, chất lượng tốt), rand() của thư viện C, và đọc từ /dev/urandom (nguồn ngẫu nhiên mật mã của hệ điều hành, đọc theo lô lớn cho công bằng nhất):

Sinh số 64-bit, thông lượng (triệu số/giây):
  xorshift64*        : 717
  rand() thư viện    : 260
  /dev/urandom (mã)  : 101   (đọc lô, đã là trường hợp tốt nhất)

xorshift nhanh gấp 2,8 lần rand(), gấp 7 lần nguồn mật mã. Con số này còn ưu ái /dev/urandom (tôi đọc cả lô 40 MB một lần; lấy lẻ từng số qua lời gọi hệ thống còn chậm hơn nhiều). Bài học tốc độ đơn giản: nguồn mật mã đắt vì nó phải làm việc thật để không ai đoán được; một PRNG thường chỉ vài phép trộn bit. Nhưng tốc độ là trục dễ nhất. Hai trục kia mới là nơi rand() gài bẫy.

rand() % n không cho phân bố đều

Định kiến tôi mang vào rất phổ biến: "rand() đủ ngẫu nhiên rồi, cần số trong [0, n) thì rand() % n là xong". Cả hai vế đều có vấn đề đo được. Vế % n trước. Giả sử bộ sinh cho số đều trong [0, R), ta lấy % n. Nếu R không chia hết cho n, các giá trị nhỏ nhận nhiều lượt hơn. Tôi đo với R = 32768 (15 bit) và n = 20000:

Sinh 15-bit [0, 32768), lấy % 20000, 60 triệu lần:
  giá trị [0, 12768)      : trung bình 3.662 lần / giá trị
  giá trị [12768, 20000)  : trung bình 1.830 lần / giá trị
  -> lệch ĐÚNG 2,00 lần

Một số ở nửa dưới xuất hiện gấp đôi một số ở nửa trên. Lý do: 32768 = 20000 + 12768. Mỗi giá trị trong [0, 12768) nhận hai nguồn (từ x và từ x + 20000 khi cả hai < 32768), còn [12768, 20000) chỉ nhận một. Với xúc xắc trò chơi thì lệch này vô hại, nhưng với một mô phỏng thống kê, một phép rút thăm công bằng, hay bất cứ chỗ nào phân bố phải đều, đây là một lỗi âm thầm bẻ cong kết quả. Cách đúng là loại-bỏ-thử-lại (rejection): vứt những giá trị rơi vào phần "thừa" ở đuôi trên rồi rút lại, để mọi giá trị có xác suất bằng nhau — đúng cái mà các hàm như arc4random_uniform hay random.randint làm sẵn cho bạn, còn % n trần thì không.

Bit thấp của LCG gần như không ngẫu nhiên

Vế "rand() đủ ngẫu nhiên" cũng lung lay. Nhiều bộ sinh cũ (và rand() trên vài hệ) là LCG (bộ sinh đồng dư tuyến tính): x = (a·x + c) mod 2^k. LCG có một khuyết tật kinh điển: các bit thấp của nó có chu kỳ rất ngắn. Tôi đo bit 0 (bit thấp nhất) của một LCG kiểu glibc:

16 bit-0 đầu của LCG   : 0101010101010101   (chu kỳ 2!)
16 bit-0 đầu xorshift  : 1101110100101000   (không quy luật)
Bit 0 của LCG đổi trong 1000 bước: 1000/1000 lần

Bit thấp nhất của LCG chỉ đảo 0, 1, 0, 1 — chu kỳ đúng bằng 2, tất định hoàn toàn (đổi ở cả 1000/1000 bước). Nó không hề ngẫu nhiên. Đây là lý do một lời khuyên cổ: đừng lấy rand() % 2 để tung đồng xu, hay rand() % n với n nhỏ là lũy thừa của 2 — bạn đang đọc đúng những bit tệ nhất. (Muốn một bit ngẫu nhiên từ LCG, phải lấy bit cao, không lấy bit thấp.) xorshift thì bit nào cũng qua được — nó trộn bit kỹ, cùng tinh thần một hàm băm tốt. Vậy "rand() đủ ngẫu nhiên" sai có điều kiện: đủ cho việc xuề xòa, không đủ khi bạn chạm vào bit thấp hay cần phân bố chuẩn.

Về đến code hằng ngày

Điều đầu tiên, rất cụ thể: đừng viết rand() % n; dùng hàm sinh khoảng có sẵn. Mọi ngôn ngữ hiện đại đều có hàm cho số nguyên đều trong một khoảng, đã xử lý cả modulo bias lẫn chất lượng bit: random.randint (Python), rand::thread_rng().gen_range (Rust), arc4random_uniform (C/BSD). Chúng làm loại-bỏ-thử-lại giúp bạn. Tự gõ % n là tự chuốc cái lệch 2 lần mà bài này đo — một lỗi không bao giờ ném ngoại lệ, chỉ bẻ cong dữ liệu âm thầm.

Điều thứ hai: chọn bộ sinh theo mục đích, và biết trục nào bạn cần. Mô phỏng, game, xáo trộn dữ liệu, pivot ngẫu nhiên cho quicksort — cần nhanh và đủ chất lượng, dùng xorshift/PCG. Sinh khóa, token phiên, mật khẩu, muối mật mã — bắt buộc dùng nguồn mật mã (/dev/urandom, getrandom, secrets của Python), chịu chậm hơn, vì một PRNG nhanh để lộ trạng thái: thấy vài output là kẻ tấn công suy ra được toàn bộ dãy tương lai. Dùng nhầm xorshift để sinh token là một lỗ bảo mật, không phải chuyện hiệu năng.

Và đây là chỗ dân viết code cao cấp hay vấp, vì cùng cái bẫy đội tên khác nhau ở mỗi ngôn ngữ. Java có hai họ tách bạch rõ ràng: java.util.Random (một LCG — nhanh, tái lập được, nhưng chớ đụng vào token) và java.security.SecureRandom (cho khóa, phiên, muối); từ Java 17 còn có RandomGenerator với các thuật toán như L64X128MixRandom để chọn đúng chất lượng. Muốn số trong khoảng thì gọi nextInt(bound) — nó tự lo modulo bias, đừng tự % n. Go tương tự: math/rand cho mô phỏng, crypto/rand cho mật mã, và rand.Intn(n) xử lý bias giúp. Ngay cả cơ sở dữ liệu: ORDER BY random() trong Postgres tiện cho việc vặt nhưng không phải nguồn mật mã, còn khóa/UUID nên sinh từ nguồn an toàn (gen_random_uuid() dùng pgcrypto). Mẫu số chung ở mọi tầng: "ngẫu nhiên" là một tính chất phải đo và phải chọn nguồn, không phải mặc định của một hàm tình cờ tên là rand.

Muốn tự thấy thì trong Python đếm [random.randint(0,9)%3 for _ in range(300000)] bằng collections.Counter: vì 10 không chia hết cho 3, giá trị 0 và 1 sẽ ra nhiều hơn giá trị 2 một cách đo được. Rồi thử random.randint(0,2) thay cho %3 và đếm lại — lần này ba giá trị đều nhau, vì randint xử lý bias giúp bạn. Khoảng chênh giữa hai lần đếm chính là cái bẫy % n mà bài này đo — và là lý do câu "cứ rand() % n" nên được thay bằng "dùng hàm khoảng có sẵn".