בתשובה לeasy, 30/05/04 23:29
מאחורי כל זה מסתתר O של גדול 222389
אה, אם זה מה שאנחנו סופרים (Overflow), אז מן הסתם גם לי זה קרה מספר פעמים. אני פשוט לא הייתי סופר את זה כמקרה בו הפרימיטיבים של השפה לא מספיקים. בד"כ יש פתרון פשוט (או לפעמים מורכב) לרוב המגבלות שהשפה מציבה לנו (למשל, אפילו בפתרון המחפיר שלך שמחלק ב-‏2, היה מספיק לשמור במשתנה בוליאני,לפני החלוקה, את זוגיות המספר ואז גם אין סטייה של 1 מהערך המצופה).
מאחורי כל זה מסתתר O של גדול 222393
ומהו אותו משתנה בוליאני אם לא תוספת של ביט ל32 המקוריים? הפיתרון שלך שקול ללעבוד ב33 ביטים.
מאחורי כל זה מסתתר O של גדול 222400
זה בדיוק זה (הוספת ביט). מה רע?
כל עוד אנו במסגרת של ה-O של 1 ביטים, השימוש בפרימטיבים הקיימים בשפה, בד"כ (כמעט תמיד?) מספיק. Long int לא מספיק בשבילך? השתמש בשניים (מצריך טיפול קל בהצגת תוצאות וחישובים, אבל הטיפול פשוט למדי).

אבל אם השאלה הייתה "האם נתקלתם במצבים בהם הייתם צריכים להתמודד עם overflow" אז נראה לי שהתשובה הטריוויאלית היא: כן, מספר פעמים.
geek alert 222409
אין רע בפיתרון הזה, פרט לעניין אסתטי קטן: היה לו overflow אבל למעשה הוא פתר את זה על ידי הוספת ספרות בצד הקטן (LSB) של המספר. באופן טבעי מתבקש להוסיף ספרות דווקא לצד הגדול (MSB).

בכל אופן, אם בבעיות עיגול מדובר, הנה טריק קטן שאני מאוד אוהב:

נניח שצריך לחשב סכום של הרבה מספרים קטנים, אבל יש אוגר יחסית קטן. למשל: נניח שצריך לסכם אלף מספרים בין 0 ל 1023 אבל יש אוגר עם נניח 12 ביטים. ברור שכל יחידה של האוגר חייב לייצג 256 יחידות של הסכום ( הסכום המקסימלי הוא כמליון, אבל ב12 ביטים אפשר לייצג עד כ 4000 ). פרט לפיתרונות כמו הוספת עוד ספרות לאוגר או עוד אוגר ביניים ( שזה בעצם אותו דבר) מה אפשר לעשות?
אפשר לעגל כל מספר בסכום לערכים 0, 256,512,768, ו1024, אבל אז מאבדים דיוק בצורה מחרידה. הטריק שלי הוא לעגל באופן *אקראי* כל מספר למעלה או למטה כך שב*ממוצע* יתקבל הערך המדוייק. כך למשל, את המספר 1 אפשר לעגל בהסתברות קטנה , של אחד מתוך 256 ל 256, ובהסתברות של 255 מתוך 256 לעגל כלפי מעלה ל 256. זה די פשוט לבצע את ההחלטה הזאת לגבי כל מספר לעצמו, על בסיס השארית בחלוקה ב 256, והשוואה למספר אקראי.
geek alert 222419
כמה מתכנתים בדיוק יש פה בקהל ?!
geek alert 222420
אני קצת יודע לתכנת, אבל אני לא מתכנת, אם לזה התכוונת.
geek alert 222430
אני מכיר אנשים שיודעים לתכנת ועובדים בזה שלא היו לגמרי מבינים מה כתבת שם.

אני אפילו נמנה עליהם.
geek alert 222436
פרשתי זאת כבקשה להבהרה:
קודם כל, הבעיה היא לא בעיה של *תיכנות* . אתה לא תהיה מתכנת טוב יותר אחרי שתבין את זה, רק בן-אדם טוב יותר :).

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

אבל, מעשה שטן, האקסל דפוק ומקבל ערכים רק בשקלים שלמים. מה תעשה? תכתוב על צטלה ותסכם בסוף החודש? זאת אפשרות טובה, אבל שלצרכינו לא רלבנטית. אולי תעגל ? ביום של 1.25 שח תרשום 1, ובים של 1.8 תרשום 2? זה לא רע, אבל כשהוא קולט את הפרינציפ , הוא מתחיל לזחול לכיוון ה 1.5001 שח ליום.

רעיון אחר זה לשלם לו *בממוצע* את מה שמגיע לו:
אם הוא הרויח 1.25 שח, תגריל מספר בין 1 ל100. אם יוצא קטן מ25, תרשום 2 שח, אחרת, תן לו 1 שח. אם כל יום בחודש הוא השתכר בדיוק 1.25 שח ליום, יש סיכוי טוב שהסכום שחישבת יהיה די קרוב ל30X1.25. אם הוא הרוויח ביום מסוים 1.8, תרשום 2 שח אם המספר קטן מ 80, ו 1 שח אחרת. ככל שיש יותר ערכים בסכום הזה, הדיוק היחסי שלך משתפר.
geek alert 222444
אם תבחר בשיטה הזו יש סיכוי טוב שתקבל תביעה על הלנת שכר מכל העובדים שיצא להם לקבל שכר נמוך מידי.
העובדה שבסיכוי טוב את ההפרש קיבלו עובדים אחרים לא תעזור לך, ואם ימצא שאחד מהמצ'ופרים סטטיסטית הוא גם בן דוד שלך, העובדה הזו גם תפגע בך.

בקיצור, תחליף אקסל.
geek alert 222448
מעבר לביקורת, שנתקבלה ברוח בה ניתנה, רציתי להבהיר שמדובר באותו עובד, שעבד הרבה ימים ולכן ההפרשים לא הלכו לעובדים אחרים.
geek alert 222459
כלומר יש לך אוגר קטן מדי, אבל מצד שני יש בידך אפשרות לחשב הסתברויות בדיוק מלא. סיטואציה מוזרה, אבל פתרון נאה.
geek alert 222461
מה מוזר? ראובן לא התכוון לכך שבאמת מדובר על מספרים קטנים כמו 1.25, זאת היתה דוגמא להמחשת הרעיון.
geek alert 222464
לא, זה לא סיטואציה מוזרה בכלל: לחשב מספר אקראי זה חשב וזרוק. אין צורך לשמור את התוצאה, בחומרה זה אפילו די טריוואלי ( למשל- לחשב CRC של השעון). כמו כן אין צורך לחשב "הסתברות" - זה כבר נעשה מעצמו. הדיוק של החישוב האקראי תלוי בשיפור בדיוק שרוצים להשיג ביחס לעיגול דטרמניסטי רגיל.

מצב קלאסי לשימוש באלגוריתם כזה הוא כאשר מגיעים מספרים אחד אחד, ויש לחשב את הסכום המצטבר.
geek alert 222468
הבנתי. בסיטואציה כזו זה אכן שימושי.
geek alert 222471
לי היה פעם גרביל קטן. התוצאות לא היו יותר טובות משל ראובן.
geek alert 222581
O(1)‎
geek alert 224046
פתרון ממש יפה - ונראה שהוא גם אופטימלי בנתונים שהיו לך. אבל מצד שני הוא כנראה גם לא משפר יותר מדי (בהנחה שהמספרים שמהם התחלת התפלגו אקראית בתחום).

לשם הנוחות, נניח שאתה מגריל אקראית מליון מספרים בין 0 ל- 101, ותסכם ערכים כאשר לכל מספר אתה בוחר אם לסכם 0 או 101. בשיטה ה"רגילה" של עיגול המספר, הטעות תתפלג באופן אחיד בין 50- ל- 50, מה שאומר שסטיית התקן של הטעות היא 29.155, ואחרי סיכום של מליון כאלו (חוק המספרים הגדולים - התפלגות נורמלית - ידה-ידה-ידה) תקבל טעות בעלת התפלגות נורמלית, עם סטיית תקן של 29,155.

בשיטה שלך התפלגות הטעות הינה התפלגות "משולשת" בין 100- ל- 100, עם שפיץ בגובה כפול ממה שהוא "אמור" להיות ב- 0. כלומר, הסיכוי לטעות של 100 (או 100-) הוא 1 חלקי 101*102, טעות של 99 (או 99-) תתקבל בסיכוי של 2 חלקי 101*102 וכו'. טעות של 0 תקרה בסיכוי 2 חלקי 102, ולא 1 חלקי 102. סטיית התקן היא 29.011, ובסיכום של מליון מספרים - 29,011. לא הרווחת הרבה.

הסיבה העצובה לחוסר הרווח שלך היא ש"מספרים גדולים פגיעתם גדולה", ובמקרה שלנו הטעויות הגדולות (של קרוב ל- 100) מזיקות מאד, אפילו שההסתברות להן קטנה - כי הם נכנסים בריבוע בחישוב התוחלת. אפשר לנקוט בפתרון ביניים שלא יאפשר טעויות גדולות בשום מקרה - למשל לעגל ל- 0 אם הערך קטן מ- 20 או ל- 100 אם גדול מ- 80, ובתחום הביניים לנקוט בשיטה שלך, אבל כנראה שזה לא יהיה יותר טוב.
geek alert 224056
הממ... נראה שהיתה לי טעות קטנה בחישוב (מרכין ראש בבושה) - לצערי היא דווקא לרעתך. בשיטה הרגילה גם כן יש סיכוי כפול ל- 0, ולכן סטיית התקן בסוף יוצאת 29,011 - *בדיוק* כמו בשיטה ה"משופרת" שלך (חבל, כי היא דווקא מאד יפה...). יוצא שאתה לא משפר כלום בהנחת התפלגות אחידה, וכנראה גם כל שיטות הביניים שתיארתי מניבות אותה תוצאה.

עוד מקרה של רעיון יפה-אך-כושל נכנס לסטטיסטיקה...
geek alert 224095
לא הבנתי את ההגיון שלך: אם ההתפלגות נורמלית, למה לסכם- תקע את הממוצע ושלום על ישראל.
geek alert 224098
התכוונתי אחידה. בכל מקרה, אני משחק משחק שנקרא: נחש את הממוצע. השיטה הרגילה היא חסרת תוחלת ( pun intended) במקרה הזה.
geek alert 224397
אני מעוניין לחשב את התפלגות הטעות (כלומר הסטייה של הסכום כמו שאתה מחשב אותו מהסכום האמיתי), כדי לראות אם הטעות באלגוריתם שלך קטנה יותר מהטעות באלגוריתם הפשוט יותר שהצגת. בשתי השיטות התוחלת זהה לתוחלת הסכום, ובשתיהן (בגלל שמדובר בסכום של הרבה משתנים ב"ת בעלי אותה התפלגות) מדובר בהתפלגות נורמלית, ולכן מה שמעניין זו סטיית התקן. As it happens, בשני המקרים סטיית התקן יוצאת זהה, ולכן בשיטה שלך לא מרוויחים כלום, אלא רק מפסידים (את הזמן שלוקח להגריל מספר, לחשב לאיזה כיוון צריך לעגל וכו').
geek alert 224453
במצב שההתפלגות היא אחידה,בין [0 ..101] לא מרוויחים כלום - מוסכם. אבל במצב כזה יש לי אלגוריתם עוד יותר פשוט: כתוב 50 כפול מספר האברים.
הבעיה היא שאני לא יודע מראש את ההתפלגות או את הממוצע שלה ואני מנסה *לאמוד* את הממוצע. אתה עדיין מציע לי לעגל סתם?
geek alert 224733
1) במקרה של התפלגות אחידה (שהחישוב שלי התבסס עליו) שתי השיטות שקולות, ושיטת הכפלת הממוצע במס' האיברים טובה כמעט כמוהן. למעשה, במקרה כזה יש לי אלגוריתם טוב יותר: פשוט סכם את המספרים כמו שהם והתעלם מהגלישה. הסכום מתפלג נורמלית והתוחלת שלו ידועה לך - כך שאת ביטי ה- most של הסכום אתה ממילא יודע (בהסתברות מאד גבוהה). אם אתה מסכם מספיק מספרים ההסתברות לטעות היא ממש זניחה (אם כי במקרה של טעות - הטעות היא גדולה).

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

3) במקרה שההתפלגות אינה ידועה, או גרוע מכך - היא נבחרת על ידי מישהו בהנתן האלגוריתם במטרה למקסם את התוצאה (כמו במקרה העובד) - האלגוריתם שלך אכן יותר טוב.
geek alert 224797
אתה עדיין חושב שזה רעיון יפה אך כושל?
geek alert 224976
לי היתה בראש בעיה שונה מהבעיה שאתה מנסה לפתור (כמו שאורי גוראל שם לב). עבור הבעיה שאתה מנסה לפתור הרעיון הוא טוב.
geek alert 224977
אז נירגעתי :) מה הבעיה שאתה מנסה לפתור, אולי יש טריק גם כאן?
geek alert 225264
כמו שכתבתי - אני חשבתי על המקרה שבו המספרים שאתה צריך לסכם מתפלגים אחיד בתחום מסוים ידוע. במקרה הזה נראה לי שהפתרון האופטימלי (זה שבו תוחלת הטעות היא מינימלית) הוא לסכם את כל המספרים ולהתעלם מהגלישה. ממילא אתה יודע את ביטי ה- most של הסכום, בהסתברות מאד גבוהה. לכן, בהסתברות מאד גבוהה תקבל את הסכום המדויק, ובהסתברות מאד נמוכה תקבל מספר שהוא רחוק מאד מהסכום (כי טעית בביטי ה- most של הסכום).
geek alert 225274
אוקי, אתה מחפש מה שקוראים בעגה "variance reduction".
למעשה, אתה יודע את הממוצע התיאורתי, ומעניין אותך לדעת כמה הראליזציה הזאת סוטה ממנה. שיטת העיגול הדטרמניסטית בעצם מודדת את האחוזון של הממוצע התיאורתי.

במחשבה שניה, בכלל לא בטוח שהחשבון שעשית הוא נכון, כי לא לקחת בחשבון שהממוצע הנמדד סוטה מהממוצע התיאורתי. אני צריך לחשוב קצת על זה.
geek alert 225411
אם אתה מתכוון לחשבון שעשיתי לגבי הטעות במקרה שההתפלגות אחידה, אז הוא נכון: לכל מספר מגדירים מ"מ שהוא הטעות בעיגול של אותו המספר. בשיטה הדיפולטית (עיגול ל- 0 או ל- 101 ע"פ מי מהם שיותר קרוב למספר) מקבלים התפלגות כמעט אחידה בין 50- ל- 50: סיכוי של 1 ל- 102 לכל מספר, פרט ל- 0 שלו יש סיכוי של 2 ל- 102. תסכם הרבה כאלו ותקבל שהסכום שלך סוטה מהסכום האמיתי (הנמדד) בסכום הטעויות - שזה סכום של מ"מ ב"ת בעלי אותה התפלגות, כלומר מתפלג נורמלית עם סטיית תקן שקל לחשב. התוחלת של הטעות היא 0 (שים לב - זו תוחלת וסטיית התקן של ההפרש בין הסכום המחושב לסכום האמיתי, לא בין הסכום המחושב לתוחלת הסכום האמיתי).

בשיטה שאתה הצגת לטעות יש התפלגות משולשית, עם סיכוי כפול ל- 0 (כפול מאשר גובה השפיץ, שהוא ב- 0). מקבלים אותה שונות בדיוק.

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

לעומת זאת, יש לי טריק אחר שאולי יכול לשפר בשיטה "דיפולטית?" -
בעצם אנחנו סופרים כמה נפלו מעל או מתחת לממוצע. בוא נגיד שנפלו N+A מעל לממוצע ו N-A מתחת לממוצע. אנו מנסים לאמוד את הסכום, על ידי עיגול ל 0 או 101,ולכן נאמוד את הסכום ב 101*(N+A).

אבל בעצם יותר הגיוני לעגל ל 75 ו 25 ( אני מזניח מתוך עצלות את ההתעסקות עם 24.5 וכולי). זאת מכיוון שאנחנו יודעים שכל איבר שתורם ל 0 הוא בעל ממוצע 25. לכן, במקום לאמוד את הסכום ב 101*(N+A) ניתן לאמוד אותו כ
101 * N פלוס עוד 50*A . זה מקטין בצורה מהותית את השגיאה.
geek alert 226069
כן, אתה צודק. אם במקום לעגל ל- 0 או ל- 101 תעגל ל- 25 או ל- 75, התפלגות הטעות תהיה אחידה בין 25- ל- 25 במקום בין 50- ל- 50 (בערך, כמובן), ולכן סטיית התקן תקטן בשורש 2, וכך גם הטעות הממוצעת. אבל בכל מקרה, השיטה הכי טובה במקרה של התפלגות אחידה (אני חושב) היא לסכום ולשכוח מהגלישה.

אגב - סתם מחשבה: אפשר לעשות משהו דומה גם בשיטת העיגול המוטה שלך? אפשר לחשוב על עיגול ל- 25 אם המספר קטן מ- 25, ל- 75 אם הוא גדול מ- 75 ולעיגול הסתברותי בתחום הביניים - אבל זה לא יעזור כנגד העובד הרשע שיעבוד 0שעות בכל שבוע וידרוש שכר של 25 שעות שבועיות... אולי אפשר להתאים את טכניקת העיגול באופן שאי אפשר יהיה להרוויח (בתוחלת), אבל הטעות תקטן (שוב בתוחלת)? לא חשבתי על זה יותר מדי.
geek alert וחידה חדשה 224063
פתרון ממש יפה - ונראה שהוא גם אופטימלי בנתונים שהיו לך. אבל מצד שני הוא כנראה גם לא משפר יותר מדי (בהנחה שהמספרים שמהם התחלת התפלגו אקראית בתחום).
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

נראה שזאת בדיוק ההנחה ממנה הוא רצה להמנע.

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

אני מניח שאורי התכוון גם לומר שהגוף חסום (כלומר, מוכל כולו בכדור כלשהו), שכן אחרת ישר או גליל אינסופי הוא פתרון קל מדי.
geek alert וחידה חדשה 224109
תודה, איכשהו זה מזכיר לי את החידה של איך לגלגל בלי גלגל ששאלת לפני כמה זמן.
geek alert וחידה חדשה 224165
נו...
באחת וחצי בלילה אין צורך לאמר חסום, זה הולך ללא פתגם.
בקיצור, שכחתי.
geek alert וחידה חדשה 224173
האם משטח כדורי עם חורים בשני הקטבים נחשב טבעת?

(כנראה שלא, אחרת זה טריויאלי)
הבהרות 224200
טבעת משמעותה טבעת. קבוצת הנקודות
<x,y,z>
המקיימת
z=0
x^2+y^2=1
או משהו איזומורפי לזה.
הבהרות 224215
אה, טבעת זה בכלל משהו חד ממדי, שלא כמו טבעת מוביוס למשל.

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

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

בניגוד לטטראדר, את זה קל, יחסית, לצייר. הטבעת האליפטית האדומה לא ניתנת להפרדה מהכוס. הנה כך:
וריאציה על הנושא 224463
וראה איזה פלא, הרי זהו המשועיגול המפורסם (אני חושב שזה השם): מכיוון ראייה אחד עיגול, מכיוון שני ריבוע, ומשלישי משולש.
משוריבול 224479
וזה לא בדיוק יוצא.
למה שיוצא יש לקרוא משוטרפמשהו, כיון שתקבל משולש, טרפז ומעין מעוין-מעוגל-שתי-פינות. ואפילו זה לא בדיוק.
המשוריבול! 224480
המשוריבול! 224553
תודה
geek alert וחידה חדשה 224223
החידה בכלל נראית כשייכת לתחום ההתמחות של גיל רונן.
geek alert 225735
רק עתה נתקלתי בזה. רעיון יפה מאוד!

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

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