Математичка мистерија унутар легендарне пуцачине из 90-их Куаке 3

Програмерима игара није било лако током 1990-их. Пошто су имали изузетно ограничену рачунарску моћ, морали су да напишу свој код што ефикасније. Узмимо на пример пуцач из првог лица Куаке ИИИ Арена, који се обично назива Куаке 3: играчи су се кретали тродимензионалним светом, тако да су програмери морали да пронађу најпаметније начине за руковање 3Д графиком и повезаним прорачунима.

Куаке 3 је објављен 1999. године и сматра се једном од најбољих компјутерских игара свог времена. Имао је трајан утицај на индустрију. Ово наслеђе није било толико због приче, већ због тога што је Куаке 3 био један од првих пуцачина из првог лица за више играча. Играчи су могли да повежу своје рачунаре преко мрежних каблова или интернета да би се такмичили у реалном времену.

Код игре је такође оставио траг. Укључио је изузетно ефикасан алгоритам који и даље задивљује стручњаке и изазива радозналост међу научницима.

О подршци научном новинарству

Ако уживате у овом чланку, размислите о томе да подржите наше награђивано новинарство претплата. Куповином претплате помажете да се обезбеди будућност упечатљивих прича о открићима и идејама које данас обликују наш свет.

Чудан код

Да бисте математички утврдили оријентацију објеката, ликова или других играча у тродимензионалном простору, креирате вектор, који је у суштини стрелица која показује правац. Да бисте упоредили векторе, они морају бити нормализовани на исту дужину, тако да их морате сразмерно скалирати. И ту долази до лукавог прорачуна: инверзног квадратног корена, који је подељен квадратним кореном броја.

Ако бих вас замолио да израчунате инверзни квадратни корен од 26 без калкулатора, вероватно бисте били заглављени неко време — а искрено, и ја бих. Још 1990-их компјутери су се суочили са истим изазовом. Иако су могли да смање бројеве, процес је захтевао велику процесорску снагу — што може значити да израчунавање траје много времена. Један проблем је био сам квадратни корен; друга је била дивизија. Зато су програмери Куаке 3 тражили бољи начин да пронађу овај инверзни квадратни корен. И заиста, њихова изворни код открио генијално решење.

Оно што је фасцинантно је да програмери никада нису рекламирали свој трик. Да изворни код Куакеа 3 није постао отворени код, њихов метод би могао заувек остати скривен. Али када је објављен, радознали ентузијасти су приметили. Када су открили исечак кода за израчунавање инверзног квадратног корена, били су збуњени — било је тешко пратити, а пропратни коментари програмера нису били од посебне помоћи. Али постепено су људи схватили како код функционише.

Данас постоје много туторијала који вас воде корак по корак кроз програмски код. Ова упутства користе посебне карактеристике програмског језика Ц. На пример, бројеви се чувају на рачунарским локацијама које се називају меморијске адресе, којима се затим манипулише. Ово је паметан начин да се избегну рачунски интензивне операције попут дељења. „Размишљајте о томе као да ставите погрешну етикету на нешто у продавници и то убедите запосленог, али овде је Ц ми будали,“ објаснио је компјутерски научник Данијел Харингтон са Универзитета у Торонту у презентацији.

Из математичке перспективе, код се лако објашњава. Да бисте одредили инверзни квадратни корен, прво нагађате решење (које је генерално нетачно), а затим прецизирате ту процену кроз постављену процедуру. На тај начин постепено долази до бољих решења.

Ништа од овога није револуционарно или ново. Оно што је импресивно, међутим, јесте да је обично потребно четири до пет итерација процеса пре него што резултат буде довољно близу стварном решењу. Овај процес захтева много рачунарске снаге. У Куаке-у 3, почетна вредност — то јест, процењени број коришћен у првом кораку процеса — изабран је тако паметно да је неопходан само један корак оптимизације.

Тражи магични број

Кораци оптимизације одговарају на такозвану Њутн-Рафсонову методукоји апроксимира вредности при којима функција производи излаз од 0, или корен функција, током многих итерација. Ово у почетку може звучати контраинтуитивно, јер се жели израчунати инверзни квадратни корен, а не било коју нулу. Али програмери користе трик: дефинишу функцију коју треба апроксимирати као разлику између почетне процењене вредности и стварног резултата. Кроз Њутн-Рафсонову методу, грешка постаје прогресивно мања, што омогућава да се све више приближи тачном решењу.

Да бисте ово добро размислили, замислите да желите да израчунате инверзни квадратни корен од 2,5. Алгоритам почиње са извесним нагађањем: рецимо 3.1. Да бисте одредили разлику од стварног решења, квадрирате почетну вредност и поделите једну резултатом. Ако је 3,1 заиста инверзни квадратни корен од 2,5, онда би 1 подељено са 3,1 на квадрат било 2,5. Стварни резултат је 0,1. Разлика је дакле 2,4.

Њутн-Рафсонов метод смањује ову разлику током сваке итерације тако да се постепено приближавате тачној вредности. Обично је потребно четири до пет таквих корака да би се постигао поуздан резултат. Ипак, Куаке 3 је значајно смањио итерације.

Кључ је у томе како се израчунава почетна вредност за Њутнове кораке. Алгоритам методе у суштини ради у три корака:

1. Узмите дати број чији инверзни квадратни корен треба израчунати и конвертујте га у одговарајућу меморијску адресу (локацију у меморисаним подацима рачунара).

2. Ова вредност се преполови и одузима од хексадецималне вредности 0к5ф3759дф. Ово је почетна вредност за Њутнов метод.

3. Затим извршите Њутнов корак.

Посебно мистериозан је криптични стринг 0к5ф3759дф, који је од тада ушао у историју рачунарства као „магични број“. То је разлог зашто је потребна само једна итерација да би се добило приближно решење за инверзни квадратни корен који производи грешку од највише 0,175 процената.

Чим је програмски код постао доступан као отворени код, стручњаци су се збунили око порекла тог магичног броја. У техничком раду објављеном 2003. компјутерски научник Крис Ломонт написао: „Одакле долази ова вредност и зашто код функционише?“

Хексадецимални број 0к5ф3759дф одговара 1.597.463.007 у децималном запису. Разбијајући појединачне кораке програмског кода, Ломонт је схватио да одређеним прорачунима може добити 1.597.463.007. Да бисмо ову математику учинили једноставнијом, ево једног начина да се представи укључени прорачун:

Вредности ³⁄₂2²³ а 127 долази од претварања приказа бројева у Ц. Али порекло 0,0450465 је мање очигледно.

Ломонт је математички истражио која вредност даје оптималан резултат за различите инпуте. Другим речима: Која почетна вредност најбоље апроксимира инверзни квадратни корен и стога би требало да доведе до најмање грешке? Дошао је до вредности од 1.597.465.647, што је отприлике:

Ово одговара вредностима које се налазе у изворном коду Куаке 3. Резултат је прилично близу вредностима које се тамо налазе.

Када је Ломонт упоредио своје резултате са оригиналним, наишао је на изненађење. У два корака Њутн-Рафсонове методе, његова израчуната константа је заправо радила боље: максимална могућа грешка била је мања него код вредности у оригиналном коду. „Ипак, изненађујуће, након једне Њутнове итерације, има већу максималну релативну грешку“, пише Ломонт. „Што поново поставља питање: како је изведена оригинална константа кода?“

У свом прорачуну, компјутерски научник је само разматрао који број би теоретски донео најбољу могућу вредност, занемарујући број Њутнових корака. У потрази за бољом константом, Ломонт је поновио свој прорачун и оптимизовао за најбоље могуће решење за један Њутнов корак. Дошао је до вредности од 1.597.463.174, што је отприлике:

Када је овај резултат ставио на практичан тест, он је заправо дао нешто боље резултате од магичног броја у коду Куаке 3.

Ломонт је у свом раду приметио да пошто су обе константе апроксимације, било која од њих је добра опција у пракси. Додао је да се нада да ће упознати оригиналног аутора константе како би сазнао како су извели магични број.

Заједнице на мрежи започеле су немилосрдну потрагу за овом мистериозном особом. Посебно је посвећен овом напору информатичар Рис Сомефелдкоји је први контактирао Џона Кармака, главног програмера Куакеа 3. Кармак није био сигуран ко је кодирао овај исечак и могао је да понуди само нагађања.

Соммефелдт је контактирао неке од најистакнутијих програмера 1990-их, од којих је сваки предложио друге могуће ауторе без полагања права на ауторство за себе. Сада се чини да је Грег Волш, који је радио за произвођача рачунара Ардент Цомпутер касних 1980-их, увео магични број у алгоритам инверзног квадратног корена. Затим се нашао у алгоритму Куаке 3 преко неколико других појединаца. Али како је тачно одређен магични број, до данас је нејасно.

То није посебно задовољавајући закључак. Ипак, прича о коду Куаке 3 – или барем делу који се врти око инверзног квадратног корена – је изузетно фасцинантна. Запањујуће је колико је труда и памети уложено у ефикасно програмирање софтвера тада — тренд који се данас често занемарује захваљујући тренутној рачунарској моћи.

Овај чланак се првобитно појавио у Спектрум дер Виссенсцхафт и репродуковано је уз дозволу.