סיפורי אופטימיזציה: אקראיות יקרה

מתי שלושה תהליכים אקראיים נפרדים יכולים – וצריכים – להסתמך על מספר אקראי אחד? לקחים מפרויקט פשוט עם תופעת לוואי לא צפויה.

אבטיפוס המדורה החשמלית
אבטיפוס המדורה החשמלית

הרעיון

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

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

    1. עבור כל לד יוחזק משתנה מספרי בזיכרון, שיקבע את יחס ההדלקה/כיבוי שלו בכל מחזור (בדומה לערך PWM שנשלח לפקודת analogWrite בארדואינו)
    2. הקוד יריץ מספר לולאות ברצף, שכל אחת מהן תהווה מחזור של הדלקה/כיבוי של הלדים, כל אחד בהתאם לערך שבמשתנה שלו. מכיוון שכל זה יתרחש מהר מאד, התוצאה הסופית תהיה בהירות נתפסת שונה לכל לד.
    3. עבור כל לד "יוגרל" ערך אקראי, שיקבע אם ערך הבהירות שלו יגדל ב-1 (אלא אם הגיע לגבול המרבי), יקטן ב-1 (אלא אם הגיע לאפס) או יישאר כמות שהוא.
    4. וחוזר חלילה.

הבעיה

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

לפני שנמשיך, יש נקודה אחת שחשוב להבהיר למי שמגיע לכאן עם רקע בארדואינו בלבד: מיקרו-בקרים 8 ביט ממשפחת PIC הם איטיים יחסית. המתנד הפנימי של ה-PIC12F675, בו השתמשתי כאן, נותן קצב שעון של 4MHz (לעומת עד 16MHz ב-ATtiny85), וכל פעולה אטומית של הקוד נמשכת 4 מחזורי שעון, לא אחד. כלומר, קצב הפעולה המירבי של הג'וק במעגל שלי הוא 1MHz בלבד. אפשר אמנם לחבר לו מתנד חיצוני ולהעלות את הקצב הסופי עד 5MHz, אך אני העדפתי לחסוך ברכיבים.

אם כן, מה גורם להבהובים? ניסוי קצר בשינוי מספר הלולאות החוזרות (שלב 2 למעלה) הוכיח שהבעיה נמצאת בשלב 3: משהו לא טוב קורה במהלך בחירת ועיבוד המספרים האקראיים. אם מוותרים על השלב הזה, ההארה נראית לעין יציבה לגמרי.

פתרון מאולתר

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

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

פתרון חכם

חזרתי, אם כך, לשלב ההגרלה. במקור בוצעו בו שלוש קריאות ל-rand, אחת עבור כל לד. מהמספר האקראי שהתקבל בתשובה לקחתי את שני הביטים התחתונים, ולפיהם קבעתי מה יקרה: אם הערך היה הוא 0 או 3 לא עשיתי כלום, אם 1 אז הגדלתי את עוצמת התאורה ואם 2 אז החלשתי אותה.

אלא ש-rand מחזירה מספר עם הרבה יותר משני ביטים. אם אני צריך רק שניים, למה "לזרוק לפח" את האחרים? הרי גם הם אקראיים!

וכך, במקום שלוש קריאות ל-rand, ביצעתי קריאה אחת בלבד לתוך משתנה, וממנו לקחתי – שלוש פעמים – שני ביטים כל פעם. הדבר נעשה על ידי הסתכלות על התוצאה של פעולת & (אופרטור AND לוגי) של המשתנה עם 3, ולאחר מכן הזזה של שאר הביטים במשתנה ימינה (<<) שני צעדים.

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

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

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

להרשמה
הודע לי על
6 תגובות
מהכי חדשה
מהכי ישנה לפי הצבעות
Inline Feedbacks
הראה את כל התגובות

עד כמה שידוע לי rand מריץ כמה פעולות מאחורי הקלעים כדי לחשב את המספר הבא בסדרת המספרים הפסוודו אקראיים שלו.
מכיוון שלא קריטי לנו שהמספרים יהיו באמת אקראיים אתה יכול לממש בעצמך איזו פונקציה שלא תיקח הרבה זמן.
(עכשיו חפרתי בקוד של libc ובמקרים מסויימים הכל הסתכם בשורות האלו:
int32_t val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
state[0] = val;
*result = val;
לא משהו שקשה לממש כמוהו…)

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

אבל אני מבין שזה פיתרון "תלוי חומרה", ולכן מתכנתים יחשיבו אותו כפחות יפה.

יפה.

אולי גם תוסיף לרפויקט הזה "מטף" שיכול לכבות את האש.