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

לפני כמה ימים פרסמתי בדף הפייסבוק שלי חידה לחובבי ארדואינו: אם מגרילים באמצעות הפונקציה random המון מספרים בטווח 0 עד 1,431,655,765 , איזה אחוז מתוכם יהיה מתחת ל-715,827,883 ? כדי להקל קצת (אבל ממש קצת) על הפותרים, הוספתי גם שהמספר השני הזה נמצא בדיוק באמצע הטווח.

כולם יודעים ש-random אמורה להפיק מספרים אקראיים, וכמעט כולם יודעים – או מניחים מראש וצודקים בלי כוונה – שהתפלגות המספרים האלה היא אחידה, כלומר שלכל המספרים יש סיכוי זהה לצאת בכל "הגרלה". אם זה נכון, נצפה ש-50% מהמספרים יהיו מתחת למספר שציינתי ו-50% מעליו, עד כדי סטייה סטטיסטית טבעית, שכמובן תלך ותקטן ככל שנצבור יותר מספרים. אבל אם תאמינו לי, או – עדיף – תכתבו את הקוד ותנסו בעצמכם, תגלו שהתשובה בפועל היא ש-66.67% (שני שליש) מהמספרים ה"אקראיים" יהיו נמוכים מ-715,827,883. איך זה יכול להיות?

בעקבות הפוסט שלי על מטבעות, ביטים והסתברויות, חשבתי עוד קצת על הנושא ונזכרתי פתאום בפונקציה random של ארדואינו ובאופן הפעולה שלה. היא מוגדרת בספריית הליבה WMath (שהמשתמש הרגיל לא מודע לה בכלל), ומתבססת על פונקציה סטנדרטית של שפת C שמחזירה מספרים אקראיים בטווח 0 עד 2,147,483,647 כולל (מספר בן 32 ביטים אך בהשמטת ביט הסימן). בארדואינו אנחנו יכולים לקבוע גבול עליון לתשובה (גם תחתון, אבל נתעלם ממנו כרגע), וזה מתקבל בעזרת פעולת השארית הפשוטה שבפקודה האחרונה כאן:

long random(long howbig) {
    if (howbig == 0) {
        return 0;
    }
    return random() % howbig;
}

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

כדי להבין את זה, נדמיין רגע שהפונקציה הבסיסית, הלא-מוגבלת, מחזירה לנו מספרים אקראיים בטווח 0-7 בלבד (כולל). ונניח שאנחנו מבקשים מהפונקציה "העוטפת" מספר אקראי מ-0 עד גבול עליון של 5. מה יקרה?

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

• 0 ––> 0
• 1 ––> 1
• 2 ––> 2
• 3 ––> 3
• 4 ––> 4
• 5 ––> 0
• 6 ––> 1
• 7 ––> 2

התשובה הסופית 4, למשל, מופיעה רק פעם אחת – סיכוי של 12.5%. התשובה 1, לעומת זאת, מופיעה פעמיים – סיכוי של 25%! התפלגות התשובות כבר לא אחידה כמו שחשבנו, ואותו הדבר בדיוק קורה במספרים גדולים יותר, אם כי שם הסטיות בדרך כלל פחות מודגשות.

כדי להשיג אפקט דרמטי עם הפונקציה של ארדואינו, ברור שהגבול העליון צריך להיות מספר ש"נכנס" פעם אחת בלבד בטווח המלא של הפונקציה הפנימית – אחרת כל השאריות יחזרו על עצמן לפחות פעמיים, וההתפלגות תהיה אחידה יותר. כשחשבתי על החידה שלי, בחרתי את הנקודה שבה בדיוק חצי מהשאריות מופיעות פעמיים: זה קורה כאשר הגבול העליון שאנחנו מגדירים הוא בשני-שליש הדרך לקצה הטווח של random הפנימית, ומכאן המספרים שהצגתי בהתחלה.

בבחירה הזו, חוסר-ההתאמה בין הקריטריון (סף שיושב בדיוק על חצי הגבול) לבין ההסתברויות בפועל (שני שליש ושליש במקום חצי וחצי) בולט מיד לעין וקל להבין אותו. אבל כפי שהבנתי וחישבתי מאוחר יותר, זו עדיין לא התוצאה הכי מוּטה שאפשר להשיג! את זה אני כבר אשאיר לכם כתרגיל…

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

הרעיון הראשון שקפץ לראש היה פשוט להגריל מספרים שוב ושוב עד שהתוצאה תיפול באזור שבו הבעיה עדיין לא באה לידי ביטוי (למשל, בדוגמה הפשטנית למעלה של 0-7, נגריל עוד ועוד מספרים עד שנקבל תשובה שהיא בעצמה קטנה מ-5, בלי שום חלוקה ושארית). זה יהיה תקין מבחינה הסתברותית, אבל ייצור בעיה חדשה: זמן הריצה של הפונקציה לא קבוע ולא ידוע מראש! תיאורטית, כמו בהטלת קוביה, יכול להיות מצב שבו הלולאה תרוץ שלוש, עשר או מאה פעמים עד שסוף כל סוף ייצא ערך מתאים.

מתוך סקרנות, חיפשתי מידע על האופן שבו הדבר נעשה בשפת פייתון, שם קיימת פונקציה דומה בשם randint. הצלחתי להגיע לקוד המקור שלה, שכתוב אף הוא בפייתון, ועקבתי אחרי הפונקציות שם עד ללב העניין. בקטע הקוד הבא, r הוא המספר האקראי שמתקבל מהגרלה של k ביטים (המינימום הדרוש כדי להכיל את הגבול העליון שהמשתמש ביקש), ו-n הוא הגבול העליון הזה:

k = n.bit_length()
r = getrandbits(k)          
while r >= n:
    r = getrandbits(k)
return r

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