בפוסט הקודם על "השעון הקוּקוּ", שמתקתק בקצב לא אחיד, הזכרתי שאפשר לגרום לו – למרות ההפרעות בקצב מחוג השניות – לשמור בסופו של דבר ולאורך זמן על השעה הנכונה. איך עושים את זה? בפוסט הנוכחי אציג מספר גישות לפתרון הבעיה.
השיטה הפרימיטיבית
כשבוחרים ערכי זמן אקראיים לתנועת מחוג השניות, כדי שהשעון יישאר בסופו של דבר קרוב לזמן האמתי, התוחלת (בשניות) של כל ערכי הזמן האלה צריכה להיות 1. כמה מהמייקרים שבנו שעונים כאלה בעבר השיגו את המטרה בשיטה פרימיטיבית למדי: הם יצרו, ידנית, סדרה של הפרשי זמנים (חיוביים ושליליים) שמסתכמים באפס. הסדרה נשמרה במלואה בזיכרון המיקרו-בקר, שפשוט הוסיף את הערכים בזה אחר זה לשניות של תקתוקי השעון. אם הסדרה ארוכה מספיק, המשתמש הטיפוסי לא יבחין במחזוריות. כדי להקשות עליו עוד יותר, אפשר להוסיף פה ושם באקראי תקתוקים של שניה אחת בדיוק, שלא משפיעים על התוחלת. מי צריך יותר מזה?
שתי שיטות אחרות
אבל נניח שאנחנו רוצים בכל זאת משהו, שגם המשתמש הכי אובססיבי לא יוכל לזהות בו חוקיות. כאן יש לנו שתי אפשרויות:
- להגדיר מראש טווח או אוסף של ערכים עם תוחלת 1, לבחור ערכים מתוך הטווח הזה באקראי ולתת לסטטיסטיקה לעשות את שלה.
- לבחור ערכים אקראיים באמת, אבל לכפות גבולות גזרה על הסטייה המצטברת מהזמן האמתי.
באפשרות הראשונה צריך לשים לב למגבלה מסוימת: אם לכל ערך יש אותו סיכוי להיבחר באקראי, אז הערך המקסימלי בטווח חייב להיות פחות מ-2 שניות – אחרת אין לנו שום דרך לקזז אותו. אם אנחנו בכל זאת מעוניינים בהשהיות של שתי שניות ומעלה, חובה לשנות את ההסתברות של כל ערך להיבחר באקראי, ולהפוך את הערכים הקצרים לסבירים יותר מאשר הערכים הארוכים מאוד. לדוגמה, יצרתי שתי סדרות של תזמונים (כל המספרים הם באלפיות שנייה): סדרה של מספרים קטנים מ-1000,
100, 200, 300, 400, 500, 600, 700, 800, 900
וסדרה של מספרים גדולים מ-1000,
1400, 1800, 2200, 2600, 3000, 3400, 3800, 4200, 4600
שימו לב שכל סדרה מכילה 9 מספרים, ושלמעשה לא צריך לשמור את כולם בזיכרון – אפשר לחשב אותם בקלות כערך התחלתי ועוד אינדקס-כפול-קבוע. הממוצע של הסדרה הראשונה הוא 500, ואילו הממוצע של הסדרה השנייה הוא 3000. קצת חשבון, ונגלה שאם נבחר מספרים מהסדרה הראשונה בסבירות גדולה פי ארבעה מהסדרה השנייה, התוחלת שלנו תהיה 1000 בדיוק.
באפשרות השנייה, של גבולות גזרה, אנחנו לא מבצעים חישובים ושקלולים מראש. במקום זה אנחנו פשוט בוחרים ערכים באקראיות מלאה – אבל לפני שאנחנו משתמשים בערך חדש, אנחנו בודקים אם הטעות המצטברת של השעון תעבור בגללו איזשהו סף שהגדרנו לעצמנו (למשל, פלוס/מינוס דקה אחת). אם כן, נגריל ערך חדש ונחזור על הבדיקה.
איזו מהאפשרויות עדיפה? כרגיל, לכל אחת יש יתרונות וחסרונות. באפשרות הראשונה אנחנו יודעים בדיוק כמה זמן יידרש כדי לבחור ערך חדש, אבל הסטייה מהשעון האמתי עלולה, לגמרי במקרה, להגיע לעתים לערכים גבוהים למדי. באפשרות השנייה המצב הפוך: אנחנו לא יודעים כמה זמן ייקח למיקרו-בקר למצוא ערך חדש לגיטימי, אבל אנחנו כן יודעים בוודאות* שהסטייה מהזמן האמתי לא תחרוג מהגבולות שהגדרנו.
* כמובן, בהנחה שהזמן לאיתור ערך חדש ומתאים לא יתמשך מעבר לזמן שהוקצב לתקתוק הקודם…
שפצורים
עבור השעון הקוקו שלי בחרתי את האפשרות הראשונה, אבל עם טריק נוסף שנועד לזרז קצת את החישובים על ה-ATtiny13A החלש.
בדוגמה שהבאתי למעלה, כל אחת מהסדרות כללה 9 מספרים. כדי לבחור באקראי מספר אחד מתוך תשעה, על סמך פלט של פונקציית rand טיפוסית, אני צריך למצוא את השארית מחלוקת פלט הפונקציה בתשע. זהו חישוב שה-ATtiny13A לא יודע לעשות בחומרה, והוא עולה לו ביוקר. כמו כן, כדי לתעדף את הסדרה הראשונה ביחס של 4:1, צריך לחשב שוב שארית מחלוקה ב-5.
לכן יצרתי שתי סדרות חלופיות, כל אחת מהן עם 8 מספרים, ועם יחס תעדוף של 3:1. חישוב של שארית מחלוקה ב-8 או ב-4 פשוט ומהיר הרבה יותר, כי אלו הם מספרים בינאריים עגולים, ופעולת AND בסיסית עם הערכים הנכונים תיתן תשובה נכונה במינימום זמן.
הנה קטע הקוד שבוחר בכל פעם את פרק הזמן, באלפיות השניה, עד התקתוק הבא. רוב התקתוקים (אחד מכל 16, בממוצע) הם של שנייה אחת בדיוק, והשאר מתחלקים בצורה מאוזנת בין קצרים לארוכים:
if (rand() & 0x0F) {
cycleMS = 1000;
} else {
if (rand() & 0x03) {
cycleMS = 150 +
((rand() & 0x07) * 100);
} else {
cycleMS = 1275 +
((rand() & 0x07) * 350);
}
}