Số ngẫu nhiên trong C: rand, srand và lấy số trong một khoảng

Số ngẫu nhiên trong C đến từ hai hàm trong <stdlib.h>: rand() sinh ra giá trị tiếp theo, còn srand() đặt điểm bắt đầu. Chúng không thật sự ngẫu nhiên: đó là một dãy giả ngẫu nhiên (pseudorandom), được tính một cách tất định từ một seed. Với mật mã học đây là hạn chế, còn với việc kiểm thử thì lại là một tính năng.

rand() và RAND_MAX

rand() trả về một int nằm đâu đó từ 0 đến RAND_MAX, tính cả hai đầu. RAND_MAX là một macro được đảm bảo ít nhất bằng 32767; trên Linux và macOS nó bằng 2147483647.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    printf("RAND_MAX = %d\n\n", RAND_MAX);

    for (int i = 0; i < 5; i++) {
        printf("rand() -> %d\n", rand());
    }
    return 0;
}

Chạy đoạn code trên hai lần. Các con số giống hệt nhau cả hai lần, và đó không phải là bug.

Khởi tạo seed bằng srand

Nếu không gọi srand, dãy số hoạt động như thể bạn đã gọi srand(1). Cùng seed thì cùng dãy, lần chạy nào cũng vậy. Muốn mỗi lần chạy ra số khác nhau, hãy dùng seed là một thứ luôn thay đổi, theo thông lệ là thời gian hiện tại:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    srand((unsigned int) time(NULL));

    for (int i = 0; i < 5; i++) {
        printf("%d\n", rand());
    }
    return 0;
}

time(NULL) trong <time.h> trả về số giây tính từ đầu năm 1970, nên mỗi lần chạy có một seed khác nhau. Phép ép kiểu sang unsigned int để tắt cảnh báo về việc thu hẹp time_t.

Ba quy tắc về seed mà ai cũng từng làm sai:

Chỉ khởi tạo seed đúng một lần, ở đầu main. Gọi srand trước mỗi lần rand() là lỗi kinh điển: trong một vòng lặp chạy xong chưa tới một giây, time(NULL) trả về cùng một giá trị ở mọi lần lặp, nên bạn khởi tạo lại với cùng một số và rand() lần nào cũng trả về cùng giá trị đầu tiên. Kết quả là một cột các số "ngẫu nhiên" giống hệt nhau.

Đừng khởi tạo lại seed để "tăng" độ ngẫu nhiên. Chất lượng của bộ sinh số đến từ trạng thái bên trong tiến dần lên; đặt lại trạng thái đó là vứt bỏ cả dãy số.

time(NULL) có độ phân giải một giây. Hai chương trình khởi chạy trong cùng một giây sẽ nhận cùng một dãy. Với trò chơi thì không sao, nhưng sai với bất cứ thứ gì cần tính độc lập.

Lấy số trong một khoảng

Cách viết chuẩn dùng toán tử chia lấy dư:

rand() % n            /* 0 to n-1 */
rand() % n + min      /* min to min+n-1 */

Để lấy từ min đến max, tính cả hai đầu, số lượng giá trị có thể có là max - min + 1:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int random_between(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main(void) {
    srand((unsigned int) time(NULL));

    printf("Dice roll (1-6):     %d\n", random_between(1, 6));
    printf("Percentage (0-100):  %d\n", random_between(0, 100));
    printf("Temperature (-10-40): %d\n", random_between(-10, 40));

    printf("\nTen coin flips: ");
    for (int i = 0; i < 10; i++) {
        printf("%s ", (rand() % 2) ? "H" : "T");
    }
    printf("\n");
    return 0;
}

+ 1 chính là chỗ hay sinh lỗi lệch một (off-by-one). rand() % 6 cho từ 0 đến 5, nên tung xúc xắc là rand() % 6 + 1. Viết rand() % 7 + 1 để "lấy cả số 6" thì bạn sẽ có một con xúc xắc bảy mặt.

Nói thẳng về modulo bias

rand() % n không phân bố đều hoàn hảo trừ khi n chia hết RAND_MAX + 1.

Hãy nghĩ với số nhỏ. Nếu RAND_MAX là 9, tức rand() trả về từ 0 đến 9 với mười giá trị có khả năng như nhau, thì rand() % 3 đưa 0,3,6,9 về 0; 1,4,7 về 1; và 2,5,8 về 2. Kết quả 0 có bốn cách xuất hiện trên mười, còn kết quả 1 và 2 mỗi cái ba cách. Số 0 có khả năng ra cao hơn 33%.

Độ lệch tương tự cũng tồn tại với RAND_MAX thật, chỉ nhỏ hơn rất nhiều: các giá trị dư ra là (RAND_MAX + 1) % n kết quả đầu tiên, mỗi kết quả được thêm một cơ hội trên khoảng 2,1 tỷ. Với tung xúc xắc, xáo bài hay mô phỏng, mức đó không thể đo được: cứ dùng % rồi làm tiếp.

Khi độ lệch thật sự quan trọng, như công việc thống kê hay bất cứ thứ gì liên quan đến bảo mật, hãy loại bỏ các giá trị dư ra thay vì gộp chúng vào:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Unbiased value in 0..n-1 by discarding the uneven tail */
int unbiased(int n) {
    int limit = RAND_MAX - (RAND_MAX % n);
    int r;
    do {
        r = rand();
    } while (r >= limit);
    return r % n;
}

int main(void) {
    srand((unsigned int) time(NULL));

    int counts[6] = {0};
    for (int i = 0; i < 60000; i++) {
        counts[unbiased(6)]++;
    }

    for (int face = 0; face < 6; face++) {
        printf("%d appeared %d times\n", face + 1, counts[face]);
    }
    return 0;
}

Vòng lặp vứt bỏ khoảng giá trị nhỏ gây ra độ lệch và rút lại số khác. Nó kết thúc rất nhanh vì phần bị loại chỉ là một phần cực nhỏ của toàn bộ.

Với tính ngẫu nhiên thật sự nhạy cảm về bảo mật, rand() là công cụ sai dù bạn cẩn thận đến đâu: hãy dùng arc4random_buf trên macOS và BSD, getrandom() trên Linux, hoặc BCryptGenRandom trên Windows.

Số thực ngẫu nhiên

Chia cho RAND_MAX để nằm trong [0.0, 1.0], rồi co giãn theo ý muốn:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double random_unit(void) {
    return (double) rand() / RAND_MAX;      /* 0.0 to 1.0 */
}

double random_range(double min, double max) {
    return min + random_unit() * (max - min);
}

int main(void) {
    srand((unsigned int) time(NULL));

    for (int i = 0; i < 5; i++) {
        printf("unit: %.6f   range(-1, 1): %+.6f   price: %.2f\n",
               random_unit(),
               random_range(-1.0, 1.0),
               random_range(9.99, 99.99));
    }
    return 0;
}

Phép ép kiểu ở (double) rand() là bắt buộc. Thiếu nó, rand() / RAND_MAX là phép chia số nguyên và gần như luôn bằng 0, chỉ bằng 1 khi may mắn trúng giá trị lớn nhất với xác suất một trên hai tỷ. Đó là bug kiểu "số thực ngẫu nhiên toàn ra 0". Xem ép kiểu để hiểu vì sao.

Dãy số lặp lại được

Một seed cố định cho ra cùng một dãy ở mọi lần chạy, đúng thứ bạn cần cho kiểm thử, một buổi gỡ lỗi, hay một trò chơi có mã màn chơi để chia sẻ:

#include <stdio.h>
#include <stdlib.h>

void print_five(unsigned int seed) {
    srand(seed);
    printf("seed %-6u:", seed);
    for (int i = 0; i < 5; i++) {
        printf(" %4d", rand() % 100);
    }
    printf("\n");
}

int main(void) {
    print_five(42);
    print_five(42);      /* identical to the line above */
    print_five(2026);
    print_five(42);      /* identical again */
    return 0;
}

Seed 42 lần nào cũng sinh ra đúng năm số ấy, trong lần chạy này và mọi lần chạy khác trên cùng thư viện. Chính khả năng lặp lại đó là lý do một chương trình mô phỏng nên cho phép chọn seed: bình thường chạy theo đồng hồ, còn khi tái hiện bug thì truyền vào một seed cố định.

Một lưu ý: dãy số của một seed không khả chuyển. Các thư viện C khác nhau dùng các bộ sinh số khác nhau, nên seed 42 trên glibc và seed 42 trên Windows cho ra các số khác nhau. Lặp lại được trên một máy, nhưng không giữa các máy.

Trò chơi xúc xắc

Gộp tất cả lại: khởi tạo seed một lần, một hàm phụ để lấy số trong khoảng, và một mảng đếm kết quả:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ROLLS 1000

int roll_die(void) {
    return rand() % 6 + 1;
}

int main(void) {
    srand((unsigned int) time(NULL));

    printf("Five rolls of two dice:\n");
    for (int i = 0; i < 5; i++) {
        int a = roll_die(), b = roll_die();
        printf("  %d + %d = %d%s\n", a, b, a + b,
               (a + b == 7) ? "  <- seven!" : "");
    }

    /* Distribution of the sum of two dice over many rolls */
    int totals[13] = {0};
    for (int i = 0; i < ROLLS; i++) {
        totals[roll_die() + roll_die()]++;
    }

    printf("\nSum distribution over %d rolls:\n", ROLLS);
    for (int sum = 2; sum <= 12; sum++) {
        printf("%3d: ", sum);
        for (int bar = 0; bar < totals[sum] / 4; bar++) {
            printf("#");
        }
        printf(" (%d)\n", totals[sum]);
    }
    return 0;
}

Biểu đồ tần suất nên cao nhất ở 7 và thấp dần về phía 2 và 12: có sáu cách để ra 7 và chỉ một cách để ra 2 hoặc 12. Một bộ sinh số cho ra phân bố phẳng ở đây là bộ sinh số hỏng.

Hai trang liên quan: thư viện chuẩn giới thiệu phần còn lại của <stdlib.h>, còn các hàm toán học nói về <math.h>, thứ bạn sẽ cần ngay khi giá trị ngẫu nhiên đi vào các phép tính thật.