שיחה:מחולל מספרים פסאודו-אקראיים

התייעצות - שני המשפטים בסעיף מחזוריות:

1. "באלגוריתם המבוסס על LCG אפשר לחשב את אורך המחזור על ידי פירוק לגורמים."
2. "שילוב של שיטות שונות יכול להניב מחזוריות של $\ 2^{n/2}$ סיביות לכל היותר."

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

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

לגבי ההערה האחרונה, אני מוכרח להסביר, הנזק נגרם כתוצאה מישום "לא נכון" של האלגוריתם הספציפי במחשב דאז. כאן לא מדובר על מדובר על עצם השימוש במחולל. עושה רושם שלא הבנת את המשפט. --יוסי א. - שיחה 18:47, 20 באוגוסט 2008 (IDT)

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

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

-בנוסף, בסעיף מחוללים פסבדו אקראיים: "...בחירה לא טובה של פרמטרים הובילה בעבר ליישום לקוי של המחולל RANDU שהיה נפוץ בשנות השבעים." -> כאן אני מודה שלא ברורה לי בדיוק הכוונה המדוייקת במילים "יישום לקוי". לדעתי אלגוריתם RANDU יושם נכון ברוב רובם של המקרים. הבעיה הרי יורדת לשורשי הפרמטרים שלו ולכן גם היישום "הנכון ביותר" שיתרגם את נוסחת האלגוריתם לקוד מושלם בשפת תכנות לא יעזור כאן לחלצנו מהצרה. -- 84.108.254.66 00:18, 21 באוגוסט 2008 (IDT)

אלגוריתם RANDU עצמו הוא "יישום לקוי של LCG". כל האלגוריתמים המבוססים על LCG נבדלים ביניהם רק בפרמטרים. זו כוונת המשורר, בחירת הפרמטרים היא שהביאה ליישום לקוי של המחולל במחשב. ואכן לאחר שעיינתי שוב במקור מסתבר שהאלגוריתם גרוע ואפילו גרוע מאוד. קאנות' אף ציין לאחר שניתח את האלגוריתם שהוא אחד מהמחוללים הגרועים ביותר שאי פעם פותחו. הוא הוסיף ש"די בשמו של האלגוריתם כדי לגרום לחלחלה בליבם של מדענים רבים..." משהו כזה. אני לא יודע על מה אתה מבסס את טענותיך. ייתכן שצריך קצת לשנות את הניסוח פה ושם. אבל הרעיון הכללי נכון. --יוסי א. - שיחה 17:31, 21 באוגוסט 2008 (IDT)

יופי, אז מיקדנו את הנקודה. לדעתי (להדגיש, לדעתי, ייתכן שרק אני רואה זאת כך כקורא אקראי שנותן משוב) ישנו חוסר בהירות שקל לתקן בניסוח. לטעמי (ושוב, לטעמי) בד"כ שימוש במונח יישום לא נכון, מתאים יותר במקרה שאלגוריתם הוא נפלא והקידוד שלו פגום (פנטיוM אמרנו, הרבה פונ' מדעיות באקסל, לפחות עד גרסה 2003 ועוד). לפנינו שגיאה באלגוריתם מיישום "לא נכון" של מה שאפשר לכנות "אלגוריתם האב", שזה מקרה שצריך לציין מעט יותר מפורשות. במקרה מוכר לי הציטוט של קאנות' שציטט וצוטט בלי סוף (למשל ע"י מיודעינו park-miller), אבל בפועל לא ידוע לי על מחקר ש"נפל" בגלל שימוש באלגוריתם (למיטב ידיעתי הצנועה) - ואם היה, היו חוגגים על זה בספרות. יתרה מזאת, אם גרם האלגוריתם נזק הרי שזה למחקרים דווקא מתחילת שנות ה-60, שכן לקראת סוף שנות ה-60 כבר ידעה הקהילה על הבעייתיות, ואף הוצעו תיקונים שונים ומשונים (בינינו, כמה כבר סימולציות נומריות כבדות נערכו בתחילת שנות ה-60 שהסתמכו רק על RANDU?). אין חולק שהאלגוריתם רע, אך הבעייתיות היא בעיקר בסדרות שהוא מנפק במימדים 3 ו- 4 (ואולי 5). רוב השימושים (לא ערכתי סטטיסטיקה ממצה) הפיקו סדרות חד ודו מימדיות, כך שהבעיה לא רלבנטית לגביהם. וכאשר היו בעיות, עלו עליהן מיד החוקר (או המנחה שלו במקרה של חוקר זוטר). כאנקדוטה לסיום, שלחתי לקאנות' דוא"ל בתחילת שנות ה-90 (כשעוד הגיב) וביקשתי דוגמאות למאמרים שכאלה, לצרכים לימודיים, זה יכול להיות קוריוז מעניין להציג בהרצאה למשל. אך לצערי לא קיבלתי תגובה עניינית. לסיכום: אין חולק שמה שכתבת נכון ומקובל, אני עדיין מחזיק בדעה שיש לשנות את הניסוח מעט במינוח 'יישום' (לשיקולך כמובן). אני גם סבור שאפשר להיתלות בבמוצא פיו של קאנות' (גם כשהוא מפריז קמעא) ולו רק משום שכמעט כל ספר או מאמר בנושא מצטט אותו ללא הכרה. כהערת סיום ברשותך: לעניות דעתי הצנועה אתה עושה עבודה מצוינת בויקיפדיה בכל הנוגע לערכים הנוגעים בקריפטוגרפיה, יישר כוח.-- 84.108.254.66 20:17, 21 באוגוסט 2008 (IDT)

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

חייב?

"הגרעין ההתחלתי חייב להיות ממקור אקראי 'אמיתי'" - לאיזה צורך הוא "חייב" להיות כזה? האלגוריתם נשאר מחולל פסאודו-אקראי ללא קשר לגרעין, ולכל צורך מעשי יש "חיובים" משלו על מקור הרחש היסודי. עוזי ו. - שיחה 15:56, 20 באוגוסט 2008 (IDT)

די ברור. כשאומרים ממקור אמיתי מתכוונים לא בשיטה "דטרמיניסטית" כלשהי שידועה לכולם. כי אז אני יכול לשחזר את הגרעין ההתחלתי באותה הדרך שבה זה נעשה בתחילה ואז כל הרצף שבא לאחר מכן אינו אקראי כלל (וגם לא פסבדו אקראי). האלגוריתם אינו אלא "מכשיר מתיחה" (מהסוג שהיו משתמשים בסדום), הוא לוקח רצף אקראי קצר ומאריך אותו. אם הרצף המקורי אינו אקראי כל הרצף אינו כזה. זה טריוויאלי. טוב לא חייבים את המילה "חייב" אפשר להסתפק בכל מילה אחרת שמבטאת היטב את הרעיון הזה. את המשפט האחרון שלך אגב לא הבנתי. --יוסי א. - שיחה 18:44, 20 באוגוסט 2008 (IDT)

אני יודע שלפעמים רוצים שהגרעין ההתחלתי יבוא ממקור אקראי אמיתי. "חייב" (וגם "רצוי") אומרים משהו אחר לגמרי. עוזי ו. - שיחה 18:48, 20 באוגוסט 2008 (IDT)

אני חוזר. ברור שיש הבדל בין רצוי לחייב. לצערי "רצוי" לא מספיק כאן. אפשר לתקן לניסוח יותר עדין בלשון כזו בערך: "כדי להשיג תוצאה אקראית יש להשתמש בגרעין התחלתי ממקור אקראי אמיתי, אחרת תוצאת המחולל לא תהיה אקראית!". --יוסי א. - שיחה 17:37, 21 באוגוסט 2008 (IDT)

על העקרון אנחנו מסכימים: אי אפשר לומר שמשהו "חייב" לקרות (ללא ציון מטרה), אלא רק ש*כדי* לקבל תוצאה מסויימת, יש לעשות משהו מסויים. הבעיה היא שגם גרעין אקראי אמיתי לא יניב פלט אקראי; ומצד שני אפילו גרעין קבוע של אפסים יניב פלט פסבדו-אקראי. עוזי ו. - שיחה 18:31, 21 באוגוסט 2008 (IDT)

החלק הראשון מובן על זה אנחנו מסכימים. לגבי החלק השני ??? הרחקת לכת. כל גרעין שיוזן לאלגוריתם יפיק פלט שנראה על פניו כאקראי (רק נראה כזה, לא באמת). אלא שכאן הטעות שלך. נניח שפיתחתי לצורך העניין מחולל אקראי שמייצר פלט פסבדו אקראי ארוך, כאשר הקלט שלו הוא קבוע המורכב מ-10 אפסים. לכנות אלגוריתם כזה "מחולל אקראי" זה אפילו לא מצחיק בתור בדיחה. אין כאן שום דבר אקראי. לקחת פונקציה מורכבת ככל שתהיה שמייצרת מספר ארוך כלשהו מרצף קצר (קבוע) של אפסים זה לא מחולל אקראי זה סתם סדרה חשבונית. כך שהחלק הראשון של המשפט: "הבעיה היא שגם גרעין אקראי אמיתי לא יניב פלט אקראי;" ??? תמוה באותה מידה. גם אם הפונקציה הפנימית של המחולל אינה מוצלחת במיוחד (אפילו פונקציה מאוד פשוטה כמו כפל או חיבור), עדיין נצפה תוצאה די אקראית אם המקור אינו ידוע. --יוסי א. - שיחה 20:05, 21 באוגוסט 2008 (IDT)

גם כאשר הקלט אקראי, הפלט אינו אקראי ממש (אנטרופיה מקסימלית), אלא פסבדו-אקראי (הוכחה: האנטרופיה של 2n הסיביות הראשונות היא n, גודל הקלט, במקום 2n).

במקרה השני, כאשר הקלט קבוע, יתכן שיש כאן אי-הבנה. ראה למשל את ההגדרה בראש הערך: נדרש אלגוריתם, המייצר סדרה "המדמה בקירוב תכונות של רצף אקראי". לסדרה יש תכונות כאלה בין אם הקלט הוא 0000000, ובין אם הוא 0110110. חשוב להבהיר שלאחר שהוגרל, אף ערך אינו אקראי - ומחולל פסבדו אקראי (שגרתי) מייצר סדרות שנראות אקראיות *לכל ערך התחלתי*. עוזי ו. - שיחה 20:37, 21 באוגוסט 2008 (IDT)

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

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

שינוי שם

נימוקים:

1. זה מה שהוא מחולל, מספרים פסאודו-אקראיים
2. כמו במחולל מספרים אקראיים תומר א. - שיחה - _{משנה ויקיפדית} 20:04, 23 ביוני 2013 (IDT)

עקרונית בעד, אבל למה המקף? כלומר למה "פסאודו-אקראיים" ולא "פסאודו אקראיים"? קיפודנחש 20:24, 23 ביוני 2013 (IDT)

אני חושב שהמילה פסאודו משמשת תחילית עבור המילה אקראיים. תומר א. - שיחה - _{משנה ויקיפדית} 20:28, 23 ביוני 2013 (IDT)

אז איך אומרים פסאודו בעברית? מספרים דמה/דמי/דמוי/דמויי אקראיים? (בסמיכות אין מקף) מאור ש. - שיחה 00:47, 28 ביוני 2013 (IDT)

הסרתי. דיון ישן מאוד. בורה בורה - שיחה 12:10, 21 בדצמבר 2014 (IST)

שינוי שם 2

מציע להעביר למחולל מספרים פסאודו-אקראיים, דיון מרוכז בשיחה:מחולל מספרים פסידו-אקראיים קריפטוגרפי. Mbkv717 • שיחה • י"א באדר ב' ה'תשפ"ד • 13:54, 21 במרץ 2024 (IST)

בוצע, אביהו ⁃ שיחה 10:17, 29 במרץ 2024 (IDT)