-
@odeddvir
לא קשור לתיכנות אבל זה הרעיון...טכניקה לא שגרתית לחישובו היא "שיטת מונטה קרלו": על לוח עץ נצייר ריבוע שאורך צלעו שתי יחידות. נצייר מעגל חסום בריבוע זה (זהו מעגל שרדיוסו שווה ליחידה אחת), ונתחיל להטיל חיצים אל הריבוע (לא נכוון את החץ למרכז הריבוע, אלא אל הריבוע כולו, באופן אקראי). לאחר מספר רב של הטלות, היחס, בין מספר הפעמים שהחצים פגעו בתוך המעגל למספר הפעמים שבהם פגעו בתוך הריבוע, שואף ליחס שבין שטחי שתי הצורות.
-
@רחמים כאשר מדובר על תוכנה ולא על לוח עץ פיזי, עדיין חסר פה שלב. איך נחשבן איזה מהמספרים האקראיים נמצא בתוך העיגול ואיזה מחוצה לו?
(כנראה צריך קצת טריגונומטריה... מתמטיקה הוא לא מהצדדים החזקים שלי...
אולי משהו כזה, נגיד שנדמיין ריבוע של מאה פיקסלים על מאה פיקסלים. סה"כ 10000 פיקסלים. נקח מספר אקראי בין 0-1 ונכפיל אותו ב-10000 כדי לקבל מיקום בריבוע. עכשיו נחשבן אם המיקום בתוך העיגול או מחוצה לה. וזאת על ידי שנחשב את המרחק שלו מהנקודה האמצעית של העיגול. נגיד שקיבלנו את המספר 3455. נחלק ב-100 כדי לקבל את השורה שבו הוא נמצא ונקח את השארית כדי לקבל את העמודה. יוצא שהוא בשורה 34 עמודה 55. המרכז של הריבוע נמצא בין שורה 50 לשורה 51 בגובה ובין עמודה 50 ל-51 ברוחב. בחישוב קל נמצא שהמיקום שקיבלנו גבוה מהרכז ב16 פיקסלים ומשוך לצד ימין ב-5 פיקסלים. כדי לקבל את המרחק מהמרכז נשרטט בדמיוננו משולש שהצד השוכב שלו הוא ברוחב 5 וצד העומד בגובה 16 ונשתמש בחשבון פיתאגרוס כדי לקבל את האלכסון שיוצא משהו כמו 16.76. טוב, מספר נמוך מ-50 אומר שהמיקום בתוך העיגול. ככל שנמשיך על זו הדרך ונחשבן את היחס של המספרים שבתוך העיגול למספרים שמחוצה לו נגיע יותר קרוב למספר PI) -
-
@yossiz אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:
כנראה צריך קצת טריגונומטריה
כל פונקציה מתמטית שתגלה לך אם אתה בתוך העיגול - מבוססת על הפאי, ואיך אתה יכול להשתמש בפונקציה זו כאשר אתה בא לברר מהו הפאי, אתה עדיין לא יודע מהו הפאי!
-
-
-
-
-
-
@רחמים השיטה שהבאת תעבוד, והדיוק המתקבל ממנה אכן תלוי ישירות ברוחב הריבוע (אם כי אני לא בטוח שהדיוק של 6 ספרות אחר הנקודה, זהה לסדר הגודל של הריבוע (מיליון ~ 6 ספרות בערך...)
החיסרון שלה לעומת הפתרון שאליו אני חותר, הוא סדר הגודל של החישובים הנדרשים (מליון*מליון=טריליון
). -
-
@רחמים הנקודה העיקרית כאן היא לא איך לחשב את π, לזה יש אלגוריתמים יעילים פי אלף (על ידי טור מתכנס לדוגמא, אפשר להגיע לדיוק של 10 ספרות אחרי הנקודה בסיכום של כמה איברים בודדים, עיין כאן למשל)
הרעיון מאחורי החידה היא איך לשער את π בצורה יחסית יעילה (ובעיקר אלגנטית), בהתחשב בהגבלות של החידה. -
@OdedDvir חמסי עליך! (קח בקלות, אני לא באמת מתרגז, ותודה על החידה
)
חיכיתי יומיים לראות אם אחרים ינסו את כוחם, וכאשר ראיתי שאין קול ואין עונה הלכתי לגוגל.
ממה שהצלחתי למצוא נראה לי שעניתי נכון לגמרי. ושדבריך לא נכונים. אשמח אם תראה לי איפה אני טועה.חיפשתי בגוגל: https://www.google.com/search?q=Monte+Carlo+pi+python
ומצאתי כמה דוגמאות, מתוכם זה: https://gist.github.com/louismullie/3769218@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:
אתה ממש קרוב לפתרון
לא הייתי "ממש קרוב", הייתי שם לגמרי, רק חסרה קצת אלגנטיות (טוב, לא נתווכח על זוטות כאלו)
לא צריך טריגונומטריה
הפתרון הנ"ל מבוסס על משפט פיתגורס בדיוק כמו הפתרון שלי, אולי עשיתי שימוש לא נכון במונח "טריגונומטריה". אני לא יודע מה נכנס תחת מטריה זו.
@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:
@רחמים זו דרך לא רעה, אבל הדיוק שלה מוגבל לרזולוציה של הריבוע. המספרים האקראיים הם כדי לשפר את הדרך הזו.
@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:
@yossiz אמר
אני מקווה שהפתרון הסופי מאפשר להגיע לדיוק אינסופי
תיאורטית - כן (אם גם הזמן שלרשותך הוא אינסופי, כמובן )
אני רוצה לחלוק על הנחה זו. דרך זו גם כן מוגבלת לרזלוציה של המספר הרנדומלי בדיוק כמו הפתרון של @רחמים. כל ההבדל מסתכם בכך שניתן להגיע להשערה קרובה עם פחות חישובים.
-
הנה דוגמאות קוד עבור כל שפה שרק תבחר:
https://www.rosettacode.org/wiki/Monte_Carlo_methods -
@yossiz אמר:
הייתי שם לגמרי, רק חסרה קצת אלגנטיות
ברור, כתבתי ל@רחמים שזה הכיוון. מצטער אם הטעתי אותך במה שכתבתי שאתה קרוב, יש לי נטייה להתלהב מהאלגנטיות יותר מעצם המטרה... זה באמת זוטות.
כמדומני שמשפט פיתגורס שייך יותר לגיאומטריה (לפחות בלשון העם), ולכן רציתי להוריד אותך מלהסתבך עם פונקציות טריגונומטריות.
דרך זו גם כן מוגבלת לרזלוציה של המספר הרנדומלי
נכון, אבל שם המוגבלות נובעת ממבנה הנתונים שמייצרת הפונקציה (למשל Decimal), ומכל מקום אפשר להריץ את האלגוריתם בלולאה אינסופית שתשפר את הדיוק בכל פעם, ואפשר להתגבר על המוגבלות של מספר הספרות המקסימלי של Decimal על ידי שימוש במבני נתונים ענקיים, בניגוד לאלגוריתם שהציע @רחמים, שם מספר החישובים המקסימלי הוא קבוע מראש לפי גודל המערך, וכדי להגיע לדיוק יותר טוב צריך להריץ הכל מחדש על מערך יותר גדול.
אגב, לכבוד הוא לי להתווכח על זוטות כאלו איתך.
-
@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:
ברור, כתבתי ל@רחמים שזה הכיוון. מצטער אם הטעתי אותך במה שכתבתי שאתה קרוב, יש לי נטייה להתלהב מהאלגנטיות יותר מעצם המטרה... זה באמת זוטות.
נחמתני
דרך זו גם כן מוגבלת לרזלוציה של המספר הרנדומלי
נכון, אבל שם המוגבלות נובעת ממבנה הנתונים שמייצרת הפונקציה (למשל Decimal), ומכל מקום אפשר להריץ את האלגוריתם בלולאה אינסופית שתשפר את הדיוק בכל פעם, ואפשר להתגבר על המוגבלות של מספר הספרות המקסימלי של Decimal על ידי שימוש במבני נתונים ענקיים, בניגוד לאלגוריתם שהציע @רחמים, שם מספר החישובים המקסימלי הוא קבוע מראש לפי גודל המערך, וכדי להגיע לדיוק יותר טוב צריך להריץ הכל מחדש על מערך יותר גדול.
לא הבנתי. אני לא רואה הבדל בין הפתרון שלך לבין זה של @רחמים חוץ מזה שאתה לוקח דגימות רנדומליות כדי להגיע לתוצאה קרובה והוא מדגים את הכל כדי להגיע לתוצאה מדויקת יותר. שתי הפתרונות מושפעות מרזלוצית הריבוע שאתה מדגים.
-
@yossiz נראה לי שעכשיו הבנתי את טענתך.
בהתחלה אני הבנתי שדרכו של @רחמים היא ליצור מבנה נתונים של מערך שמצייג את הפיקסלים, ואחר כך לסרוק אותו תא אחר תא. ואז ממילא אתה מוגבל מבחינת זיכרון (מערך של מליון על מליון), ולכן עניתי לו שאתה מוגבל מבחינת הרזולוציה. גם לפי האמת שכלל לא צריך ליצור מערך, כי צריך רק את הקוורדינציות, ומספיקה לולאה כפולה שבה נגדיל את הנתונים בכל איטרציה בערך המינימלי של Decimal, עדיין השיטה הזו בזבזנית להחריד, ולא תיתן תוצאות רלוונטיות (קרובות לפאי מספיק) עד שתהיה מאוד קרוב לסוף הביצוע.
הפתרון של שליפת קואורדינציה אקראית הוא יותר יעיל כך שהוא מספק תוצאות די קרובות במעט בדיקות (יחסית) ובנוסף דיוק התוצאה משתפר בכל איטרציה, כך שניתן לעצור בכל שלב שרוצים.עיין עוד כאן בניסוי המחט לחישוב פאי, שבו הגיעו לתוצאה מרשימה למדי, וכל מה שהם היו צריכים זה לזרוק מחט באויר...
-
D dovid העביר נושא זה מ-תכנות ב-
