Quake 3 o‘yinidagi “magic number” sirlari: invers kvadrat ildiz algoritmi

1999‑yilda chiqarilgan Quake 3 Arena o‘yinida, uch‑o‘lchamli grafikalar va real‑vaqtli ko‘p o‘yinchi rejimi uchun juda samarali kod yozilgan. Bu kodning eng mashhur qismi – invers kvadrat ildiz (inverse square root) algoritmi bo‘lib, u 0x5f3759df deb ataladigan “magic number” ga asoslanadi.

Invers kvadrat ildiz nima?

Matematikada 1/√x ifodasi invers kvadrat ildiz deb ataladi. O‘yinlarda bu hisoblash ko‘pincha obyektlarning yo‘nalishini normalizatsiya qilish, ya’ni uzunligini bir birlikka keltirishda qo‘llaniladi. An’anaviy usulda kvadrat ildizni topish va keyin bo‘lish amallari ko‘p vaqt oladi, bu esa o‘yin tezligini pasaytiradi.

Newton‑Raphson usuli

Bu usul birinchi taxminni (guess) asos qilib, takroriy ravishda yaxshilash orqali aniq natijaga yaqinlashadi. Odatda to‘rt‑besh marta takrorlash kerak bo‘ladi, lekin Quake 3 dasturchilari bir qadamda yetarli aniqlikni olishga muvaffaq bo‘lishdi.

Quake 3 dagi “magic number”

Algoritm quyidagi uch bosqichdan iborat:

• Berilgan sonni float turidan int turiga (xotira manziliga) aylantirish.
• Bu qiymatni 0x5f3759df dan ayirish – bu yerda “magic number” paydo bo‘ladi.
• Natijani float ga qaytarib, bir Newton‑Raphson takrorlashini bajarish.

Natijada 1/√x qiymati maksimal 0.175 % xatolik bilan olinadi. “Magic number” ning aniq kelib chiqishi hali ham muhokama qilinadi, lekin u 1 597 463 007 (ondalik) ga teng bo‘lib, dasturchilar tomonidan tajriba‑asosida tanlangan.

Kim yaratdi?

Quake 3 kodlari open source bo‘lgandan keyin jamoatchilik bu sirni ochib berdi. Tadqiqotchilar, xususan Chris Lomont va Rys Sommefeldt, “magic number” ning kelib chiqishini aniqlashga harakat qilishdi. Eng yaqin taxmin – bu raqam 1980‑yillarda Ardent Computer kompaniyasida ishlagan Greg Walsh tomonidan yaratilgan.

Zamonaviy dasturchilar uchun saboqlar

Bu tarixiy misol bir necha muhim dars beradi:

• Resurslarni tejash: Hozirgi kunda kuchli protsessorlar bo‘lsa ham, samarali algoritmlar energiya va batareya hayotini uzaytiradi.
• Matematika va kodning uyg‘unligi: Newton‑Raphson kabi nazariy usullarni amalda qo‘llash natijada tezkor yechimlar beradi.
• Open source kuchi: Kodni ochiq qilish orqali butun jamoa uni tahlil qilib, yanada takomillashtiradi.

Quake 3 ning “magic number” hikoyasi, bugungi kunning sunʼiy intellekt, mashina o‘rganish va grafik hisoblash sohalarida ham ilhom manbai bo‘lib qoladi.