Máy tính là cỗ máy tất định — cho cùng đầu vào, luôn cho cùng đầu ra. Vậy làm sao nó "sinh số ngẫu nhiên"? Câu trả lời là một nghịch lý được thiết kế: một PRNG (bộ sinh số giả ngẫu nhiên) là thuật toán tất định sinh ra dãy trông như ngẫu nhiên. Ở bài cấu trúc ngẫu nhiên hóa ta đã dùng ngẫu nhiên để làm thuật toán nhanh và an toàn hơn — nhưng ngầm giả định nguồn ngẫu nhiên là tốt. Bài này mở nguồn đó ra đo, và tìm thấy vài khuyết tật mà "cứ dùng rand()" giấu đi.
Ba trục đối nghịch của một PRNG
Một PRNG nhận một hạt giống (seed) và biến đổi nó qua từng bước để tuôn ra dãy số. Cùng seed luôn cho cùng dãy — đó là chỗ "giả" trong "giả ngẫu nhiên": không hề có ngẫu nhiên thật, chỉ có một dãy tất định khó đoán ra quy luật. Tính chất "cùng seed cùng dãy" này thực ra rất 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).
Chọn một PRNG là cân ba trục đối nghịch nhau: tốc độ (sinh một số nhanh cỡ nào), chất lượng (dãy có đều và không có mẫu lặp không), và tính không đoán được (nhìn các số đã ra có suy được số kế tiếp không — điều bắt buộc cho mật mã). Không bộ sinh nào tối ưu cả ba; bài này đo từng trục.
Đo: 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(), và gấp 7 lần nguồn mật mã. Con số này đã ưu ái /dev/urandom (tôi đọc cả lô 40 MB một lần; lấy 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 độ: nguồn mật mã đắt vì nó phải làm việc thật để không đoán được; một PRNG thường chỉ vài phép trộn bit. Nhưng tốc độ mới là trục dễ nhất; hai trục kia mới là chỗ rand() gài bẫy.
Một lần tôi đo hớ: rand()%n không cho phân bố đều
Định kiến tôi mang vào: "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), và ta lấy % n. Nếu R không chia hết cho n, thì các giá trị nhỏ nhận được 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 được 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 làm sai kết quả. Cách đúng là loại-bỏ-thử-lại (rejection): vứt đi 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.
Đo hớ thứ hai: 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ỹ, giống tinh thần một hàm băm tốt. Vậy "rand() đủ ngẫu nhiên" là 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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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 có hàm cho số nguyên đều trong một khoảng mà đã 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 lấy 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ỉ làm dữ liệu của bạn sai lệch âm thầm.
Hệ quả 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ấp nhận 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 lỗi hiệu năng.
Hệ quả thứ ba là bài học đo lường bao trùm: "ngẫu nhiên" là một tính chất phải đo, không phải mặc định của hàm tên rand. Con số mang theo: rand() % 20000 đo ra phân bố lệch đúng 2 lần giữa hai vùng giá trị (do modulo bias khi 32768 không chia hết cho 20000); bit 0 của LCG chỉ đảo 0,1,0,1 (chu kỳ 2, tất định); và xorshift 717 triệu/giây nhanh hơn rand() và urandom nhưng không dùng được cho mật mã. Trước khi tin một dãy là ngẫu nhiên, hỏi: bộ sinh này chất lượng ra sao, tôi có đang lấy đúng bit tốt không, và mục đích của tôi cần chất lượng hay chỉ cần tốc độ? Ba câu đó tách một mô phỏng đúng khỏi một mô phỏng sai lệch, và một token an toàn khỏi một token đoán được.
Thử ba mươi giây
Trong Python, chạy thử độ lệch modulo bằng một bộ sinh cố tình nhỏ: import random; c=[0]*3; [c.__setitem__(random.randint(0,9)%3, c[random.randint(0,9)%3]+1) for _ in range(300000)] — hoặc đơn giản đế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".
