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

לכל תחום מחקר יש את התעלומות שלו. במתמטיקה יש את "ההוכחה נפלאה" שהמתמטיקאי פרמה הבטיח בשולי ספר שלו ומעולם לא נמצאה, ובמדעי המחשב יש את תעלומת קבוע הקסם 0x5f3759d.

הסיפור מתחיל בשנת 2005, כאשר חברת id-software שחררה לציבור את קוד המקור של אחד ממשחקי היריות המצליחים ביותר שלה - Quake 3. באופן טבעי התעוררה התעניינות רבה בקוד של החברה שיצרה משחקים כמו Wolfenstein 3D ו-Doom (השמות הגדולים ביותר בתחום משחקי היריות מגוף ראשון בשנות התשעים) הרבה בזכות המנועים הגרפיים פורצי הדרך שלהם. בקוד מתגלה קטע קוד קצרצר שכולל בתוכו את השורה המוזרה הבאה:

i  = 0x5f3759df - ( i >> 1 );               // what the fuck?

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

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

הניסיונות להתחקות על מקור הקוד עלו בתוהו, אבל הראו שהקוד כנראה קיים כבר משנות השמונים ופשוט הועתק ממקום למקום. בהתחלה חשבו שיוצר הקוד היה ג'ון קרמק, מייסד id-software והמתכנת הראשי שלה, אבל הוא אמר שאין לו מושג מי כתב אותו. לאף אחד אין מושג מי חשב על המספר המוזר 0x5f3759df ואיך הוא הגיע אליו. זה לא אומר שלא מבינים מה הקוד עושה או מה המטרה של המספר הזה; מיד נסביר.

ובכן, מה הולך פה?

מטרת הקוד פשוטה: מקבלים מספר ומחזירים אחד חלקי השורש שלו. למשל, עבור 4 מחזירים חצי (כי השורש של 4 הוא 2, ואחד חלקי 2 זה חצי) ועבור 2 מחזירים בערך 0.7071.

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

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

שיטה כללית שמשמשת לפתרון בעיות קירוב רבות - שיטת ניוטון-רפסון (ראו לדוגמה [2]). הרעיון הוא שאם x הוא קירוב "קטן מדי" של השורש אז n חלקי x יהיה קירוב "גדול מדי" של השורש והממוצע ביניהם יתקרב אל השורש. מה שעושה הקוד (בחלקים ממנו שלא הראיתי בפוסט) הוא לבצע זאת עבור הוצאת שורש וחלוקה בו זמנית. החלק המרשים הוא שהקוד מבצע בדיוק סיבוב אחד של ניוטון רפסון. למעשה, בקוד מופיע עוד סיבוב, אבל המתכנת האלמוני שכתב את הקוד ביטל את הסיבוב הנוסף כי הקוד מדויק מספיק גם בלעדיו.

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

i  = 0x5f3759df - ( i >> 1 );               // what the fuck?

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

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

מקורות:

[1]  אם הלכתם צעד אחד ימינה וצעד אחד למעלה, אז המרחק הכולל שעברתם ביחס לנקודת ההתחלה הוא השורש של 2: נסו לצייר את המשולש ישר הזווית המתאים.

[2] שיטה אחת להוצאת שורש למספר כלשהו n שמיוחסת כבר לבבלים (והתיעוד הראשון שלה הוא בכתביו של הרון מאלכסנדריה מהמאה הראשונה לספירה): מנחשים קירוב התחלתי x לשורש של n (למשל מספר אקראי כלשהו עם חצי ממספר הספרות של n), ואז חוזרים שוב ושוב על הפעולה הבאה: מחלקים את n ב-x ולוקחים את הממוצע בין התוצאה של החלוקה הזו ובין x עצמו. התוצאה תהיה x החדש.
למשל, אם רוצים שנמצא את השורש של 70: נזרוק מהראש ניחוש התחלתי של 7, נחלק את 70 ב-7 ונקבל 10. ניקח את הממוצע בין 7 ובין 10 ונקבל 8.5. עכשיו נעשה את זה שוב:

70 חלקי 8.5 זה בערך 8.235 והממוצע בינו ובין 8.5 הוא בערך 8.367.
70 חלקי 8.367 הוא בערך 8.366 והממוצע בינו ובין 8.367 הוא בערך 8.3665.

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

לחצו כאן לקריאה נוספת