מספרים אקראיים ב-C: rand, srand ומספר בטווח

המספרים האקראיים של C מגיעים משתי פונקציות ב-<stdlib.h>: rand(), שמפיקה את הערך הבא, ו-srand(), שקובעת את נקודת ההתחלה. הם לא באמת אקראיים: זה רצף פסאודו־אקראי שמחושב באופן דטרמיניסטי מתוך seed. זו מגבלה בקריפטוגרפיה ויתרון בבדיקות.

rand() ו-RAND_MAX

rand() מחזירה int כלשהו בין 0 ל-RAND_MAX, כולל. RAND_MAX הוא מאקרו שמובטח שיהיה לפחות 32767, וב-Linux וב-macOS הוא 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;
}

הריצו את זה פעמיים. המספרים זהים בשתי הפעמים, וזה לא באג.

אתחול עם srand

בלי קריאה ל-srand, הרצף מתנהג כאילו קראתם ל-srand(1). אותו seed, אותו רצף, בכל הרצה. כדי לקבל מספרים שונים בכל הרצה, אתחלו עם משהו שמשתנה, ולפי המוסכמה עם השעה הנוכחית:

#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) מ-<time.h> מחזירה את מספר השניות מתחילת 1970, כך שכל הרצה מקבלת seed שונה. ה-cast ל-unsigned int משתיק אזהרה על צמצום של time_t.

שלושה כללים לגבי אתחול, ואנשים טועים בכולם:

אתחלו פעם אחת בדיוק, בתחילת main. קריאה ל-srand לפני כל rand() היא ה-anti-pattern הקלאסי: בתוך לולאה שמסתיימת בפחות משנייה, time(NULL) מחזירה את אותו ערך בכל איטרציה, כך שאתם מאתחלים שוב עם אותו מספר, ו-rand() מחזירה בכל פעם את אותו ערך ראשון. הפלט הוא עמודה של מספרים "אקראיים" זהים.

אל תאתחלו מחדש כדי "לשפר" את האקראיות. האיכות של המחולל נובעת מהמצב הפנימי שלו שמתקדם, ואיפוס המצב הזה זורק את הרצף.

ל-time(NULL) יש רזולוציה של שנייה אחת. שתי תוכניות שהופעלו באותה שנייה מקבלות את אותו רצף. זה בסדר למשחק, ושגוי לכל דבר שבו חשובה עצמאות.

מספר בטווח

הניב הסטנדרטי משתמש באופרטור השארית:

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

כדי לקבל ערכים מ-min עד max כולל, מספר הערכים האפשריים הוא 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 הוא המקום שבו גרות שגיאות off-by-one. rand() % 6 נותן 0 עד 5, ולכן הטלת קובייה היא rand() % 6 + 1. כתיבת rand() % 7 + 1 כדי "לכלול את 6" נותנת לכם קובייה עם שבע פאות.

הערה כנה על modulo bias

rand() % n אינו אחיד לחלוטין, אלא אם n מחלק את RAND_MAX + 1 בדיוק.

חשבו על זה עם מספרים קטנים. אם RAND_MAX היה 9, כלומר rand() מחזירה 0 עד 9, עשרה ערכים בסיכוי שווה, אז rand() % 3 ממפה את 0,3,6,9 ל-0, את 1,4,7 ל-1, ואת 2,5,8 ל-2. התוצאה 0 מתקבלת בארבע דרכים מתוך עשר, והתוצאות 1 ו-2 בשלוש דרכים כל אחת. לאפס יש סיכוי גבוה ב-33%.

אותה הטיה קיימת גם עם ה-RAND_MAX האמיתי, רק קטנה בהרבה: הערכים העודפים הם (RAND_MAX + 1) % n התוצאות הראשונות, וכל אחת מהן מקבלת הזדמנות נוספת אחת מתוך כ-2.1 מיליארד. להטלת קובייה, לחפיסת קלפים מעורבבת או לסימולציה, זה בלתי מדיד: השתמשו ב-% והמשיכו הלאה.

כשזה כן חשוב, בעבודה סטטיסטית או בכל דבר שקשור לאבטחה, דחו את הערכים העודפים במקום לקפל אותם פנימה:

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

/* ערך בלי הטיה בטווח 0..n-1, על ידי השלכת הזנב הלא אחיד */
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;
}

הלולאה זורקת את הטווח הקטן של ערכים שהיה גורם להטיה, ומגרילה שוב. היא מסתיימת מהר, כי הפרוסה הנדחית היא חלק זעיר מהשלם.

לאקראיות שבאמת רגישה לאבטחה, rand() הוא הכלי הלא נכון בכל רמת זהירות: השתמשו ב-arc4random_buf ב-macOS וב-BSD, ב-getrandom() ב-Linux, או ב-BCryptGenRandom ב-Windows.

מספרי double אקראיים

חלקו ב-RAND_MAX כדי לנחות בטווח [0.0, 1.0], ואז שנו את קנה המידה:

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

double random_unit(void) {
    return (double) rand() / RAND_MAX;      /* 0.0 עד 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;
}

ה-cast ב-(double) rand() הוא הכרחי. בלעדיו, rand() / RAND_MAX הוא חילוק של מספרים שלמים ומחושב ל-0 כמעט תמיד, ול-1 בסיכוי של אחד לשני מיליארד לפגוע במקסימום. זה באג שנראה כמו "כל ה-double האקראיים שלי הם אפס". ראו המרת טיפוסים כדי להבין למה.

רצפים שחוזרים על עצמם

seed קבוע נותן את אותו רצף בדיוק בכל הרצה, וזה בדיוק מה שרוצים בבדיקה, בסשן דיבוג או במשחק עם קודי שלבים שאפשר לשתף:

#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);      /* זהה לשורה הקודמת */
    print_five(2026);
    print_five(42);      /* שוב זהה */
    return 0;
}

seed 42 מפיק את אותם חמישה מספרים בכל פעם שמשתמשים בו, בהרצה הזו ובכל הרצה אחרת עם אותה ספרייה. בזכות היכולת הזו לשחזר, סימולציה צריכה לאפשר לבחור את ה-seed: הריצו עם השעון בדרך כלל, והעבירו seed קבוע כשמשחזרים באג.

הסתייגות אחת: הרצף של seed מסוים אינו נייד. ספריות C שונות משתמשות במחוללים שונים, כך ש-seed 42 ב-glibc ו-seed 42 ב-Windows נותנים מספרים שונים. ניתן לשחזור על מכונה אחת, לא בין מכונות.

משחק קוביות

הכול ביחד: אתחול פעם אחת, פונקציית עזר לטווח, ומערך שסופר את התוצאות:

#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!" : "");
    }

    /* התפלגות הסכום של שתי קוביות על פני הטלות רבות */
    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;
}

ההיסטוגרמה צריכה להגיע לשיא ב-7 ולרדת לכיוון 2 ו-12: יש שש דרכים לקבל 7 ודרך אחת בלבד לקבל 2 או 12. מחולל שהיה מפיק כאן התפלגות שטוחה היה שבור.

שני עמודים קשורים: עמוד הספרייה הסטנדרטית ממפה את שאר <stdlib.h>, ועמוד פונקציות המתמטיקה עוסק ב-<math.h>, שתצטרכו ברגע שערכים אקראיים ייכנסו לחישובים אמיתיים.