 |
|
 |
||
|
||||
 |
כדי להגריל מספר אקראי בטווח מסוים, לא כדאי להשתמש בשארית כי השארית בחלוקה במספר שאינו חזקה של 2 אינה מתפלגת באופן שווה (מיודענו ד"ר אור דונקלמן הקדיש לנושא רבע שעה באחת ההרצאות שלו). עדיף לחלק בערך המקסימלי של המחולל ולכפול בערך המקסימלי שרוצים לקבל, כמובן תוך שימת לב לבעיות של איבוד סיביות בחלוקה, מספר הסיביות המקסימלי וכו'. |  |
 |
 |
|
|
|
||
|
||||
|
החכמתי (ומצד שני, לצרכים לא קריפטוגרפיים/קריטיים דומים נראה לי שגם שיטת החלוקה מספיק טובה). | |
|
|
|
|
|
||
|
||||
|
חישוב שאריות זאת עבודה לא נעימה. פעם הייתי צריך לפזר מספרים למספר תאים, ובניתי טבלה של סימני התחלקות בבסיס בינארי (משהו כמו שמתואר כאן תגובה 216062). אחרי שטרחתי להסביר למהנדס איך לממש את העסק, נפל לי האסימון שאני יכול פשוט להגדיר לו ספים, כמספר התאים (פחות 1) ושיבדוק אם המספר נופל בין הספים. כמו כן, התברר לי בדרך הקשה, שאם תיקח מספרים עוקבים ותעשה עליהם CRC16, הביטים הנמוכים מאוד לא אקראיים. |
|
|
|
|
|
|
||
|
||||
|
אפשר הסבר קצר ממה זה נובע? | |
|
|
|
|
|
||
|
||||
|
עכשיו אני רוצה להגריל מספר בין 1 ל-6, ולכן אני לוקח את תוצאת ההגרלה x, ובודק את התוצאה של (x mod 6) + 1, שמתפלגת בין 1 ל-6 כמבוקש. אבל נניח, לצורך הדיון, שיש לי מחולל מספרים אקראי חד-ספרתי, המגריל מספרים בין 0 ל-9 בלבד. מהמחולל הזה אני אקבל את המספרים 5 ו-6 בסבירות של 10%, ואת שאר המספרים בסבירות של 20%, כי יש להם שני מקורות בטווח המספרים של המחולל האקראי, בעוד ל-5 ו-6 יש מקור יחיד. |
|
|
|
|
|
|
||
|
||||
|
ואיך נראים האחוזים אם המחולל עובד על טווח ריאליסטי יותר, וההגרלה היא עדיין של מספר בין 1 ל-6? | |
|
|
|
|
|
||
|
||||
|
יותר טוב, כמובן. אם הטווח של המחולל הוא 0 עד ℕ–1, יש תוצאות שמופיעות n פעמים בטווח, ויש תוצאות שמופיעות n+1 פעמים בטווח, כאשר n = ⌊ℕ/6⌋. הסיכוי לקבל את ההתוצאות הראשונות הוא n/ℕ, ואת התוצאות האחרות (n+1)/ℕ. לכן היחס בין התפלגות התוצאות שמופיעות n+1 פעמים והתוצאות שמופיעות n פעמים הוא (⌊ℕ/6⌋+1)/(⌊ℕ/6⌋) = 1 + 1/(⌊ℕ/6⌋) אם ℕ=10, אזי ⌊ℕ/6⌋ = ⌊10/6⌋ = 1, והיחס יוצא 1:2.. |
|
|
|
|
|
|
||
|
||||
|
וזה נראה לי יחסית זניח ולכן הרשתי לעצמי להציע את זה במאמר. כמובן, אחרי שראיתי משהו כמו Bug attacks, לא אופתע לגלות שגם את זה אפשר לנצל איכשהו.... | |
|
|
|
|
|
||
|
||||
|
>>perl -le 'print 0xffff_ffff % 6 ' במילים אחרות, אם המחולל מייצר מספרים של 32 ביט, יש למספרים 1-3 סיכוי גדול יותר להיבחר. (גדול בערך ב- 1/715827882 ).3 >>perl -le 'print int 0xffff_ffff / 6 ' 715827882 וקטנוניות אחרת: האם המחוללים המקובלים חייב לעבור על כל המספרים האפשריים לפני שהוא חוזר למספר הגרעין? (אני לא יודע את התשובה, אבל ליתר ביטחון אני מוסיף אינדקס (או סדרה אחרת) למספרים אקראים כדי להימנע מפיזור אחיד) |
|
|
|
|
|
|
||
|
||||
|
נדמה לי שהתייחסתי לזה במאמר - מכיוון שהמחולל הוא דטרמיניסטי, אז אם הגענו פעמיים לאותו ערך x, אז כל מה שיקרה מעתה והלאה יהיה זהה למה שקרה אחרי הפעם הראשונה שבה היינו ב-x - כלומר, "המשחק נגמר" ולא נקבל עוד ערכים חדשים שטרם הוגרלו. | |
|
|
|
|
|
||
|
||||
|
אם ככה, אז הסיכוי לקבל אפס במחולל מקובל עם גרעין אפס תוך פחות מ-N פעולות הוא אפס. נראה לי קצת בעייתי, אבל מה אני מבין. |
|
|
|
|
|
|
||
|
||||
|
באופן כללי מחולל פסאודו־אקראי טוב הוא כזה שיהיה לנו סיכוי נמוך להבדיל בינו לבין מקור אקראי באמת. בפועל מדברים על טווחי מספרים קצת יותר גדולים. אחרת באמת אפשר להשתמש בשיטות ספירה פשוטות. אבל כשטווחי המספרים גדולים מאוד, גם במחולל אקראי באמת הסיכוי שלך לקבל חזרה על ערך די זניח. |
|
|
|
|
|
|
||
|
||||
|
דווקא להיפך. במחולל מספרים אקראי באמת, בהנחה שטווח המספרים הוא 2^32, הגרלת 2^16 ערכים ברצף צריכה לספק בהסתברות של 50% זוג אחד לפחות (אם אני זוכר נכון את פרדוקס יום ההולדת). | |
|
|
|
|
|
||
|
||||
|
אתה זוכר נכון, אבל זה עדיין ''זניח'' (אקספוננציאלי, אם כי עם בסיס קטן יותר). | |
|
|
|
|
|
||
|
||||
|
נניח ℕ=2 (מחולל בינארי) | |
|
|
|
|
|
||
|
||||
|
במחולל שכזה אני מניח שהקלטים והפלטים הם סדרה של אפסים ואחדים, ולא רק ''אפס'' או ''אחד'' בודד. | |
|
|
|
|
|
||
|
||||
|
מכיוון שאתה מזכיר מספרים, שווה לראות מהו חישוב מעשי. אפשר לקנות היום במחיר סביר מחשב עם דיסק של 250GB, וזכרון של 4GB. נתעלם לרגע מריבוי הליבות (לעניין המקבול נתייחס בהמשך). היצרץ מצהיר בהמעבד עובד בקצב של משהו כמו "2.5GHz", כלומר: 2.5 מליארד מחזורי שעון בשניה. נניח שהמעבד מבצע מליארד פעולות בשניה. (באופן כללי: יש הרבה סיבות שיכולות לגרום למעבד לא לעבוד "במלוא הקצב". גם ההגדרה של "פעולה" היא הגדרה מאוד עמומה). כידוע 2^10 זה בקירוב1 10^3. כלומר מיליון זה 2^20 ומיליארד הם 2^30. כמוכן צריך לזכור שנוהגים לזכור נפח זכרון בבייטים ולצורך חישובינו מעניינים דווקא הביטים - כלומר: מספר הבייטים כפול 8 (או תוספת 3 למעריך - הכפלה של מספרים היא חיבור המעריכים). לכן מבחינת נפח אחסון, הזכרון מספק לנו נפח של 2^35 והדיסק: נפח של 2^41. ביממה יש 86,400 שניות, כלומר: בערך 2^16. בשנה יש בערך 30 מליון שניות, כלומר בערך 2^25 . לכן אם ניקח ברצינות את ההנחה שלנו על מליארד (כלומר 2^30) פעולות בשניה, נקבל חישוב של 2^46 פעולות ביממה או 2^55 פעולות בשנה. יש חישובים שאפשר לחלק לכמה חלקים לא תלויים. לדוגמה: "לנסות את כל האפשרויות" - פשוט מקצים לכל מחשב טווח אפשרויות לנסות. במקרה הזה אפשר להשתמש בכל הליבות של המעבד. אפשר גם לקנות עוד כמה מחשבים ולחלק את העבודה. כמובן שיש גבול לכמה שמשיגים מזה. חוות מחשבים עם 64 מחשבים מרובעי ליבות מקדמת אותנו פי 256, כלומר תוספת של 2^8 למאמץ המלחמתי. עד עכשיו דיברנו על מחשבים צנועים במחיר מתאים לכל כיס (ושעוד עשר שנים יכנסו לכל כיס?). בתקציבים קצת יותר רציניים אפשר לבנות או לקנות מחשבים קצת יותר חזקים. 1 בתחום נפחי הדיסקים מדובר על שיוויון ממש: http://xkcd.com/394/ |
|
|
|
|
|
|
||
|
||||
|
אם מייצרים סדרה מספיק גדולה של מספרים אקראיים, ההסתברות שאחד מהם יחזור על עצמו לא זניחה. ----- ובלי קשר, כדאי לקרות חלק מתגובות הקוראים לספר הבא: בעיקר אהבתי את: The book is a promising reference concept, but the execution is somewhat sloppy. Whatever algorithm they used was not fully tested. The bulk of each page seems random enough. However at the lower left and lower right of alternate pages, the number is found to increment directly
|
|
|
|
|
|
|
||
|
||||
|
למה לדעתך זה בעייתי? (בלי קשר, זכור שאם באמת נוקטים בשיטה של צמצום התחום, נניח על ידי חלוקה ולקיחת השארית, אז אפס יתקבל הרבה מאוד פעמים). |
|
|
|
|
|
|
||
|
||||
|
נניח בדיקה של פונקציה המקבלת שלם ומחזירה משהו הקשור אליו. נניח שהמתכנת החרוץ מצא לנכון לשמור במטמון את X התוצאות האחרונות. החלק המשתמש בזכרון המטמון לא יבדק. וניטפוק עצמי: המחולל שבדקתי משתמש ברגיסטרים של נקודה צפה (המכילים בד"כ יותר סיביות מרגיסטרים של שלמים), ולכן הבעיה לעיל לא תתקים בו. (אוף, מחשבים עברית קשה שפה) |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח שהבנתי. למה לא ייבדק? | |
|
|
|
|
|
||
|
||||
|
כי אין ערך ב-CACHE עבור הקלט X. (קצת נמאס לי מהקטנוניות, ומצידי אפשר להפסיק.1) --- 1. כאמור - במקרה הבודד שזה הפריע לי2, פשוט הוספתי אינדקס לתוצאה. 2. זאת היתה מערכת משובצת בלי FLOATING REGISTERS. המחולל הועתק מאיזשהו מאמר, ועבר על כל הערכים האפשריים ל-INTEGER לפני שחזר על עצמו. |
|
|
|
|
|
|
||
|
||||
|
עדיין לא הבנתי מה זה בדיוק X (קלט או גודל של מקום שלוקחים ב-cache?) אבל זה לא משנה - כאמור, אם מפריע לך שיש מספרים שלא מופיעים, צמצם את הטווח ואז מובטח לך שכל המספרים יופיעו, וההתפלגות תהיה פחות-או-יותר אחידה. | |
|
|
|
|
|
||
|
||||
|
אם כבר, המספרים 1, 2 ו-6 מחוללים אקראיים לא חייבים לעבור על כל המספרים האפשריים בטווח לפני סגירת מעגל, אבל הפונקציה חייבת להיות חח"ע ועל, כי אחרת יש ערכים (או שרשראות של ערכים) בעלי סיכוי גבוה יותר מאחרים. |
|
|
|
|
|
|
||
|
||||
|
אההם, הקטנוניות הורגת אותי. צ"ל: המספרים 1, 2, 3 ו-4, ועם הקוראים סליחה. |
|
|
|
|
|
|
||
|
||||
|
אמנם 1-4, ועם הקוראים הסליחה. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |