בתשובה ליוסי, 09/06/09 22:22
רק כדי להיות יותר קטנוני... 513149
באופן כללי מחולל פסאודו־אקראי טוב הוא כזה שיהיה לנו סיכוי נמוך להבדיל בינו לבין מקור אקראי באמת.

בפועל מדברים על טווחי מספרים קצת יותר גדולים. אחרת באמת אפשר להשתמש בשיטות ספירה פשוטות. אבל כשטווחי המספרים גדולים מאוד, גם במחולל אקראי באמת הסיכוי שלך לקבל חזרה על ערך די זניח.
רק כדי להיות יותר קטנוני... 513151
דווקא להיפך. במחולל מספרים אקראי באמת, בהנחה שטווח המספרים הוא 2^32, הגרלת 2^16 ערכים ברצף צריכה לספק בהסתברות של 50% זוג אחד לפחות (אם אני זוכר נכון את פרדוקס יום ההולדת).
רק כדי להיות יותר קטנוני... 513154
אתה זוכר נכון, אבל זה עדיין ''זניח'' (אקספוננציאלי, אם כי עם בסיס קטן יותר).
רק כדי להיות יותר קטנוני... 513155
נניח ℕ=2 (מחולל בינארי)
רק כדי להיות יותר קטנוני... 513160
במחולל שכזה אני מניח שהקלטים והפלטים הם סדרה של אפסים ואחדים, ולא רק ''אפס'' או ''אחד'' בודד.
רק כדי להיות יותר קטנוני... 513194
מכיוון שאתה מזכיר מספרים, שווה לראות מהו חישוב מעשי.

אפשר לקנות היום במחיר סביר מחשב עם דיסק של 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/
רק כדי להיות יותר קטנוני... 513152
אם מייצרים סדרה מספיק גדולה של מספרים אקראיים, ההסתברות שאחד מהם יחזור על עצמו לא זניחה.

-----
ובלי קשר, כדאי לקרות חלק מתגובות הקוראים לספר הבא:
בעיקר אהבתי את:

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים