חידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים

[רחמים]

@yossiz אז למה לך להגריל מספרים אקראיים, פשוט תעבור על כל הפיקסלים ותספור כמה מהם בתוך העיגול וכמה בחוץ וככה תדע את הפאי - לפי היחס שבינהם?

[yossiz]

@רחמים אתה צודק. אני מקווה שהפתרון הסופי מאפשר להגיע לדיוק אינסופי - דבר שאי אפשר אם אתה ממיר את הריבוע לפיקסלים.

[OdedDvir]

@רחמים זו דרך לא רעה, אבל הדיוק שלה מוגבל לרזולוציה של הריבוע. המספרים האקראיים הם כדי לשפר את הדרך הזו.

[OdedDvir]

@yossiz אמר

אני מקווה שהפתרון הסופי מאפשר להגיע לדיוק אינסופי

תיאורטית - כן (אם גם הזמן שלרשותך הוא אינסופי, כמובן )

[רחמים]

@odeddvir המספרים האקראיים למעשה מצביעים על פיקסלים, כך שגם הם בסופו של דבר תלויים ברזולוציה.
אגב, רזולוציה גבוהה היא לא בעיה כלל. קח ריבוע של 2 מליון על 2 מליון פיקסלים, ועיגול ברדיוס של 1 מליון, ויצא לך פאי עם 6 ספרות אחרי הנקודה.

[OdedDvir]

@רחמים השיטה שהבאת תעבוד, והדיוק המתקבל ממנה אכן תלוי ישירות ברוחב הריבוע (אם כי אני לא בטוח שהדיוק של 6 ספרות אחר הנקודה, זהה לסדר הגודל של הריבוע (מיליון ~ 6 ספרות בערך...)
החיסרון שלה לעומת הפתרון שאליו אני חותר, הוא סדר הגודל של החישובים הנדרשים (מליון*מליון=טריליון ).

[רחמים]

@odeddvir למה אתה צריך את זה כל כך מהר? הרי פאי זה משהו שבודקים פעם אחת ומאז משתמשים, אפילו אם החישוב יקח דקה או שעה מה מפריע, הוא חד פעמי.

[OdedDvir]

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

[yossiz]

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

חיפשתי בגוגל: https://www.google.com/search?q=Monte+Carlo+pi+python
ומצאתי כמה דוגמאות, מתוכם זה: https://gist.github.com/louismullie/3769218

@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:

אתה ממש קרוב לפתרון

לא הייתי "ממש קרוב", הייתי שם לגמרי, רק חסרה קצת אלגנטיות (טוב, לא נתווכח על זוטות כאלו)

לא צריך טריגונומטריה

הפתרון הנ"ל מבוסס על משפט פיתגורס בדיוק כמו הפתרון שלי, אולי עשיתי שימוש לא נכון במונח "טריגונומטריה". אני לא יודע מה נכנס תחת מטריה זו.

@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:

@רחמים זו דרך לא רעה, אבל הדיוק שלה מוגבל לרזולוציה של הריבוע. המספרים האקראיים הם כדי לשפר את הדרך הזו.

@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:

@yossiz אמר

אני מקווה שהפתרון הסופי מאפשר להגיע לדיוק אינסופי

תיאורטית - כן (אם גם הזמן שלרשותך הוא אינסופי, כמובן )

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

[yossiz]

הנה דוגמאות קוד עבור כל שפה שרק תבחר:
https://www.rosettacode.org/wiki/Monte_Carlo_methods

[OdedDvir]

@yossiz אמר:

הייתי שם לגמרי, רק חסרה קצת אלגנטיות

ברור, כתבתי ל@רחמים שזה הכיוון. מצטער אם הטעתי אותך במה שכתבתי שאתה קרוב, יש לי נטייה להתלהב מהאלגנטיות יותר מעצם המטרה... זה באמת זוטות.

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

דרך זו גם כן מוגבלת לרזלוציה של המספר הרנדומלי

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

אגב, לכבוד הוא לי להתווכח על זוטות כאלו איתך.

[yossiz]

@odeddvir אמר בחידה חביבה: כיצד להעריך בקירוב את הקבוע π באמצעות מספרים אקראיים:

ברור, כתבתי ל@רחמים שזה הכיוון. מצטער אם הטעתי אותך במה שכתבתי שאתה קרוב, יש לי נטייה להתלהב מהאלגנטיות יותר מעצם המטרה... זה באמת זוטות.

נחמתני

דרך זו גם כן מוגבלת לרזלוציה של המספר הרנדומלי

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

לא הבנתי. אני לא רואה הבדל בין הפתרון שלך לבין זה של @רחמים חוץ מזה שאתה לוקח דגימות רנדומליות כדי להגיע לתוצאה קרובה והוא מדגים את הכל כדי להגיע לתוצאה מדויקת יותר. שתי הפתרונות מושפעות מרזלוצית הריבוע שאתה מדגים.

[OdedDvir]

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

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