Микроконтролери и електроника
http://mcu-bg.com/mcu_site/

Абе тая магия от Куейк 3 знаехте ли я?
http://mcu-bg.com/mcu_site/viewtopic.php?f=6&t=10228		 Страница 1 от 1
Автор:  Цецо [ Пет Юни 15, 2012 12:50 pm ]
Заглавие:  Абе тая магия от Куейк 3 знаехте ли я?
http://en.wikipedia.org/wiki/Fast_inverse_square_root

Аз понеже се бях засилил да си търся sqrt функция която да се търкаля прилично на дребен процесор и налетях на това...
Автор:  tgi [ Пет Юни 15, 2012 1:25 pm ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
Бе не, не съм го правил така. Иначе в power има инструкция точно за това, но на мене
като ми трябва корен ми трябва цялата точност та го правя с последователни приближения
и толкова умножения, колкото бита искам в резултата (демек корен от 32 битово
цяло число става с 16 умножения, за FP става по същия начин за мантисите а
какво им баех на експонентите не мога да си спомня без да погледна сорса ама
не беше нищо особено).

Гяволско е де, сега поне знам какво да правя с това "square root esrtimate" дето го имам :D .
Дано потрябва скоро.
Автор:  zaphod [ Пет Юни 15, 2012 9:15 pm ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
бисмилях аррахмани аррахим! това ме изкърти яко!!!
Автор:  anrieff [ Съб Юни 16, 2012 12:59 am ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
Винаги съм се чудил какво толкова невероятно намират хората в това парче код. Идеята е гениална - спор няма. Повечето хора, обаче, се захласват по магическата константа 0x5f3759df. И се дивят на гения, успял да я рафинира. Пък то прецизирането на константата става с малко код и двоично търсене.

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

Код:
#define uint unsigned int
static inline float fastpower_minus_quarter(float val)
{
   const float magicValue = 1331185664.0;
   union {
      float as_float;
      uint as_int;
   } value;
   value.as_float = val;
   float tmp = (float) value.as_int;
   tmp = (tmp * -0.25) + magicValue;
   value.as_int = (uint) tmp;
   return value.as_float;
}


И това без да знам въобще как работи оригиналният код.
Моето е малко по-подробно разписано, с union-и, щото иначе GCC-то се сърди заради нарушаване на strict aliasing (оригиналното от на Quake-а няма да се компилира до правилен машинен код на достатъчно ново GCC с -O2 ;))
Автор:  Н'бабане Гт'муан'га [ Съб Юни 16, 2012 2:32 am ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
anrieff написа:
Аз като бях на 20 години си направих подобна функция, смятаща реципрочен четвърти корен (т.е. смята x^(-0.25), с +- 3% точност):


Аз пък като бях на 20 години, джитках Archon и Cubit по 12 часа на ден, пушех по 50 цигари и слушах Napalm Death. И пет пари не давах дали числата имат корен изобщо :D
Автор:  zaphod [ Съб Юни 16, 2012 6:27 am ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
anrieff написа:
Повечето хора, обаче, се захласват по магическата константа 0x5f3759df.

коснатнатта въобще не ме учудва, а това че някой въобще му е хрумнало да шифтва флоатинг пойнт число и че резултата е смислен. аз също съм правил ускорени функции, но са чисто инт или чисто флоат, аркустангенс примерно.
Автор:  tgi [ Съб Юни 16, 2012 8:22 am ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
А, това с шифта не е голям скок, лесно би ти дошъл ако си писал достатъчно
FP емулатори и/или емулирал по-сложните функции в налично FPU и си запомнил
добре кое къде е във формата. Как ли не съм ги шил и съшивал (или успявал да
го избегна ... :D ). Идеята за самия алгоритъм е интересна според мене, но не
вникнах достатъчно та да имам истинска преценка де.
Автор:  woody [ Съб Юни 16, 2012 11:03 am ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
Сметките за графика позволяват човек да балансира м/у скорост и точност.

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

anrieff написа:
Пък то прецизирането на константата става с малко код и двоично търсене.

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

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

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

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

"Смислен" в рамките на търсената точност. Или ще влезе бит от експонентата, или не. В PDF-а има анализ.
Автор:  tgi [ Съб Юни 16, 2012 12:12 pm ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
woody написа:
...
Или ще влезе бит от експонентата, или не. В PDF-а има анализ.


Има известна забава и от това, че тоя бит ще нахлуе не като най-старши а едно
място по-надолу. Ако въобще съм загрял от половиния поглед какво става де,
може да не са в "нормалния" IEEE формат FP числата та знам ли.
Автор:  woody [ Съб Юни 16, 2012 12:24 pm ]
Заглавие:  Re: Абе тая магия от Куейк 3 знаехте ли я?
Стандартни IEEE са си. Вливането на бит и само един пас N-R са били ОК за търсената графична цел - валидни еди-колко-си бита. Специално за случая на Quake III човекът дори е махнал втория N-R пас. :)
Страница 1 от 1 Часовете са според зоната UTC + 2 часа [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/