פענחו את האלגוריתם

[עריסטו]

פענחו את האלגוריתם

מה מחשב האלגוריתם הבא? האלגוריתם מקבל מספר x. מה המשמעות של המספר שהוא מחזיר? נסו לענות בלי להריץ את האלגוריתם.

s = x * x / 3609483753574802 do 20 times: s = s * (4 - s) RETURN 1 - s / 2​

 

[ןן גיל ןן]

../images/Emo62.gif

עבור מספרים x בגודל סביר, ודיוק מקובל של מספרים במחשב, אני מהמר שהאלגוריתם יחזיר את האיבר הנייטרלי לחיבור. הסבר: מבצעים 20 איטרציות של אותה פונקציה, ולאיטרציות כאלה יש נטיה להתכנס לנקודת השבת של הפונקציה שהיא s=2. והפקודה האחרונה תחזיר במקרה זה 0. מנקודת מבט מתמטית טהורה פלט האלגוריתם הוא פולינום ממעלה 21^2 ב- x- ולכן עבור ערכים גדולים מאד של x התוצאה תשאף לאינסוף.

 

[עריסטו]

../images/Emo128.gif

עבור ערכים גדולים של x כנראה אתה צודק, אבל עבור ערכים בגודל סביר התשובה שלך לא נכונה.

 

[גיל14]

רק

נקודת השבת היא לא s=2, שמחזיר 2*(4-2) = 4.

s(4-s)=s s = 3,0​

אם הוא אכן מתכנס לזה, יתכן שיוחזר zz 1-s/2 zz שהוא מינוס חצי, או אחת. אבל נתבונן בפונקציה

f(s) = s(4-s) = 4s-s^2 f'(s) = 4-2s​

עבור s מאוד קטן, הנגזרת שווה קרוב ל-4 ובכל מקרה לא קטן מ1, מה שבד"כ דרוש בשביל שדברים כאלו יתכנסו לנקודת השבת שלהם.

 

[ייץ]

אם אני לא טועה

קוסינוס X/2

 

[ייץ]

שכחתי לרשום

במעלות

 

[עריסטו]

../images/Emo2.gifכמעט...

 

[ייץ]

צודק

מדובר ב קוסינוס X אבל אם נבצע 19 איטרציות נקבל קוסינוס X/2 עבור 18 נקבל קוסינוס X/4 וכו,