http://en.wikipedia.org/wiki/Fast_inverse_square_root

Аз понеже се бях засилил да си търся sqrt функция която да се търкаля прилично на дребен процесор и налетях на това...

Бе не, не съм го правил така. Иначе в power има инструкция точно за това, но на мене
като ми трябва корен ми трябва цялата точност та го правя с последователни приближения
и толкова умножения, колкото бита искам в резултата (демек корен от 32 битово
цяло число става с 16 умножения, за FP става по същия начин за мантисите а
какво им баех на експонентите не мога да си спомня без да погледна сорса ама
не беше нищо особено).

Гяволско е де, сега поне знам какво да правя с това "square root esrtimate" дето го имам .
Дано потрябва скоро.

бисмилях аррахмани аррахим! това ме изкърти яко!!!

Винаги съм се чудил какво толкова невероятно намират хората в това парче код. Идеята е гениална - спор няма. Повечето хора, обаче, се захласват по магическата константа 0x5f3759df. И се дивят на гения, успял да я рафинира. Пък то прецизирането на константата става с малко код и двоично търсене.

Аз като бях на 20 години си направих подобна функция, смятаща реципрочен четвърти корен (т.е. смята x^(-0.25), с +- 3% точност):



И това без да знам въобще как работи оригиналният код.
Моето е малко по-подробно разписано, с union-и, щото иначе GCC-то се сърди заради нарушаване на strict aliasing (оригиналното от на Quake-а няма да се компилира до правилен машинен код на достатъчно ново GCC с -O2 )

Аз пък като бях на 20 години, джитках Archon и Cubit по 12 часа на ден, пушех по 50 цигари и слушах Napalm Death. И пет пари не давах дали числата имат корен изобщо

коснатнатта въобще не ме учудва, а това че някой въобще му е хрумнало да шифтва флоатинг пойнт число и че резултата е смислен. аз също съм правил ускорени функции, но са чисто инт или чисто флоат, аркустангенс примерно.

А, това с шифта не е голям скок, лесно би ти дошъл ако си писал достатъчно
FP емулатори и/или емулирал по-сложните функции в налично FPU и си запомнил
добре кое къде е във формата. Как ли не съм ги шил и съшивал (или успявал да
го избегна ... ). Идеята за самия алгоритъм е интересна според мене, но не
вникнах достатъчно та да имам истинска преценка де.

Сметките за графика позволяват човек да балансира м/у скорост и точност.

http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf


Не баш двоично търсене. По-скоро зиг-заг след теоретично определяне на стартовата, следейки критерия за грешката.


Когато слушах Napalm Death и играех Archon и на мен това щеше да ми се види като пълна магия.


"Смислен" в рамките на търсената точност. Или ще влезе бит от експонентата, или не. В PDF-а има анализ.

Има известна забава и от това, че тоя бит ще нахлуе не като най-старши а едно
място по-надолу. Ако въобще съм загрял от половиния поглед какво става де,
може да не са в "нормалния" IEEE формат FP числата та знам ли.

Стандартни IEEE са си. Вливането на бит и само един пас N-R са били ОК за търсената графична цел - валидни еди-колко-си бита. Специално за случая на Quake III човекът дори е махнал втория N-R пас.