Thursday, August 24, 2017

המעשה המופלא בקבוע המסתורי 0x5f3759df (Hebrew)

http://www.gadial.net/2017/08/22/0x5f3759df_part_1/
http://www.gadial.net/2017/08/24/0x5f3759df_part_2/


See also:
http://h14s.p5r.org/2012/09/0x5f3759df.html
https://en.wikipedia.org/wiki/Fast_inverse_square_root

אני רוצה לספר על תעלומה בת למעלה מעשור, שגם היא כנראה שלא תיפתר לעולם אבל היא מעניינת מספיק גם ככה – תעלומת המספר 0x5f3759df וקטע הקוד שבו הוא מופיע. קטע הקוד הזה נמצא, מכל המקומות בעולם, בקוד של משחק היריות מגוף ראשון Quake 3. הוא נתגלה בשנת 2005, כשקוד המשחק שוחרר לציבור הרחב. אפשר למצוא אותו כאן, והוא נראה ככה:





Ниже есть продолжение.

לפני שנתחיל לצלול לקוד, בואו נבהיר מה הוא עושה: זו פונקציה שלוקחת מספר x ומחשבת את
$\frac{1}{\sqrt{x}}$

כלומר את ההופכי של השורש של x. זה הכל. למה זה חשוב לגרפיקה? אסביר זאת בהמשך, אבל בשורת מחץ אחת: כי ככה מנרמלים וקטורים. שאלה אחרת היא למה לעשות את זה ככה ולא לבנות כמו בני אדם שפויים פונקציה שלוקחת את x ומחשבת את
$\sqrt{x}$
אחר כך אפשר לעשות פעולת חילוק רגילה ולחשב את
$\frac{1}{\sqrt{x}}$
כמו בני תרבות. התשובה היא יעילות. יעילות היא מילת המפתח בכל מה שאנחנו עושים פה. פעולת חילוק היא בדרך כלל פעולה יקרה לביצוע יחסית; אם אפשר להימנע ממנה, למה לא.
...
קחו מבט נוסף על הקוד, עכשיו כשאתם יודעים מה הוא אמור לעשות. האם אתם מרגישים קצת מוזר? אני מרגיש מאוד מוזר. חישוב שורש… זה משהו שאמור להיות מסובך, לא? איך אפשר שקוד יבצע גם חישוב שורש וגם הופכי שלו ביחד בכל כך מעט שורות קוד, ויעשה את זה מהיר ומדויק? משהו פה מרגיש כאילו הוא לא מסתדר. אבל הכל מסתדר – זה עובד, וזה עובד מאוד יפה.

בואו נסביר את הקוד שורה שורה, עבור מי שלא מכיר שפות תכנות. אין כאן שום דבר שמעבר ליכולת ההבנה שלכם – זה קוד מאוד פשוט. רק טיפה טרמינולוגיה קודם: כשאני מדבר על "מספר ממשי" אני מתכוון לכל מספר שאנחנו יודעים לכתוב עם ייצוג עשרוני, למשל 3 או 3.141 או 0.333 וכדומה. ליתר דיוק, אני מתכוון רק לאלו מתוכם שאנחנו יודעים לייצג במחשב, אבל מי אלו בדיוק נראה רק בהמשך. באופן דומה, "מספר שלם" הוא מספר שאין לו כלום אחרי הנקודה העשרונית. 3 הוא שלם ו-3.1 או 0.3 הם לא שלמים. גם על השלמים יש הגבלה, שלא אתאר כרגע, לגבי מי מהם יכול להיות מיוצג במחשב.

float Q_rsqrt( float number )

השורה הראשונה הזו אומרת "שלום בוקר טוב אני פונקציה ושמי הוא Q_rsqrt (אני מנחש ש-rsqrt זה קיצור של reciprocal square root – ההופכי של שורש ריבועי), אני מקבלת קלט בשם number שהוא מספר ממשי ומחזירה פלט שגם הוא מספר ממשי". מה שאולי לא ברור לכם הוא למה משתמשים במילה float כדי לתאר מספר ממשי; הסיבה לכך היא שבשפת C, מספרים ממשיים מיוצגים על ידי שיטת ייצוג שנקראת נקודה צפה ואתאר בהמשך הפוסט. אתם לא באמת צריכים להבין אותה בשלב הזה.

שלוש השורות הבאות מגדירות משתנים וקבועים שבהם ישתמשו בהמשך הפונקציה


long i;
float x2, y;
const float threehalfs = 1.5F;



המשתנים x2,y שניהם מספרים ממשיים. לעומת זאת i הוא מספר שלם. זה חשוב כי מספרים שלמים מיוצגים בצורה שונה מאשר מספרים ממשיים כלליים. המילה long נובעת מכך שיש שיטות שונות לייצג מספרים שלמים ב-C שנבדלות בגודל המקסימלי של המספרים שאפשר לייצג. שם מקובל למספר שלם הוא int, קיצור של integer; השם long בא לומר שהמספר השלם הולך להיות גדול יחסית – לכל הפחות בתחום מספרים סביב 0 שגודלו
$2^{32}$
ואולי גם יותר (לא ניכנס פה לדקויות של הגדרות טיפוסים ב-C, זו זוועה שאין כמוה).

השורה האחרונה מגדירה קבוע: משתנה שערכו נקבע מראש ולא ישתנה אחר כך. במקרה הנוכחי, threehalfs מוגדר להיות בדיוק מה ששמו מרמז: המספר 1.5 כאשר הייצוג שלו הוא על ידי float (זה ה-F שבסוף). למה צריך את הקבוע הזה? בהמשך, כשנראה את החישובים שעומדים מאחורי הפונקציה הזו, נראה שהוא אכן צץ מעצמו.

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



x2 = number * 0.5F;
y = number;


כלומר, y הוא כרגע בדיוק המספר שקיבלנו בתור קלט, ו-x2

הוא חצי ממנו. למה צריך את זה, נראה אחר כך.

שלוש השורות הבאות הן ללא ספק החלק הכי לא ברור בכל הקוד:


i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;


אשית, הטקסט האנגלי שמופיע אחרי זוג הלוכסנים בסוף שתי השורות הראשונות הוא הערה, כלומר משהו שלא רץ בפועל אלא קיים שם למען הדורות הבאים שיקראו את הקוד. אני מנחש שמי שהוסיף את ההערות הללו לא היה המתכנת המקורי אלא מישהו שניסה להבין מה בעצם הוא עשה שם, וכפי שניתן לראות, השורה האמצעית די בלבלה אותו… כל שלוש השורות הללו הן לחלוטין בלתי קריאות למי שלא מכיר C, אבל קל להסביר את ה"בערך" של מה שהן עושות: השורה הראשונה אומרת "קח את המספר הממשי y ותתייחס אליו לרגע בתור מספר שלם, ואת זה תציב ב-i". השורה האחרונה אומרת "קח את המספר השלם i ותתייחס אליו לרגע בתור מספר ממשי ואת זה תציב ב-y". מפתה לומר שמתבצעת פה המרה ממספר ממשי למספר שלם, וההפך. אבל זה ממש לא מה שקורה פה. המרה היא תהליך מתוחכם שבו מתבצעת מניפולציה על המספר, למשל 3.7 יומר ל-3

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

ואז מגיעה השורה האמצעית. דווקא אותה די קל להבין, אבל צריך להכיר את הסימונים. ראשית, הקבוע המסתורי 0x5f3759df. הקבוע הזה הוא בסך הכל דרך ייצוג מקובלת למספר השלם 1597463007, כאשר כותבים אותו בבסיס הקסדצימלי, כלומר בסיס ספירה שבו יש לנו 16 ספרות. ה-0x בהתחלה הוא האופן הסטנדרטי שבו מודיעים לשפת C "הנה עכשיו אני מביא לך מספר בבסיס 16 ולא בבסיס 10 כמו בדרך כלל" וה-d,f הללו שנמצאים שם הם פשוט הספרות עבור 13 ו-15.

קצת יותר מסתורי ה-i >> 1 הזה. אני אסביר בהמשך למה בדיוק משתמשים בסימון הזה, אבל המשמעות שלו פשוטה – זו חלוקה ב-2. אם כן, כל מה שהשורה הקסומה הזו עושה הוא לקחת את הקבוע 0x5f3759df ולהפחית ממנו את "הקלט של הפונקציה שלנו כאשר הוא מתפרש איכשהו בתור מספר שלם ומחולק ב-2".

למה? למה עושים דבר מוזר כזה? בשביל מה?

התשובה היא שהשורות הללו נותנות לנו קירוב לערך של
$\frac{1}{\sqrt{x}}$.

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


y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed


השורות הללו מבצעות שתיהן בדיוק את אותו חישוב:

$y\leftarrow\frac{3}{2}-x_{2}y^{2}$.

חישוב הזה הוא מימוש למקרה הספציפי שלנו של שיטת קירוב שנקראת שיטת ניוטון-רפסון ואתאר בהמשך.


http://www.gadial.net/2017/08/22/0x5f3759df_part_1/
http://www.gadial.net/2017/08/24/0x5f3759df_part_2/

No comments:

Post a Comment