Сейчас будет длинная, путаная и медленная история про быстрый | Ioffe hates Landau
Сейчас будет длинная, путаная и медленная история про быстрый обратный квадратный корень! Я её позавчера узнал и до сих пор под впечатлением. Есть такая относительно древняя компьютерная игра Quake III Arena, меня в ней постоянно хэдшотили. Я всех нагибал во вторую кваку, она клавиатурная, а для этих мышиных шутеров я слишком тормоз. Движок у этой игры имеет лицензию GNU, то есть код открыт. Так вот, в коде этой игры обнаружили очень странно выглядевшую функцию вычисления обратного квадратного корня - y = 5F3759DF16 − (x >> 1). Это я самую загадочную часть функции привёл, там ещё несколько строчек кода есть. То есть вместо того, чтобы по людски взять квадратный корень функцией sqrt(x), а потом поделить на него единицу - программа побитово сдвигает вправо всё число формата float, а потом вычитает его из загадочнейшего шеснадцатиричного числа 5F3759DF! Обнаружившие эту неведомую хрень программисты с благоговейным ужасом немедленно выяснили, что эта сатанинская функция вычисляет обратный корень в четыре раза быстрее чем банальное 1/sqrt(x). Есть небольшая погрешность меньше процента, но поскольку в игре эта функция отвечала за что-то типа обсчёта теней на стенах, никого она не волновала. Обратились к автору, легендарному создателю игр Quake и Doom Джону Кармаку. Он сказал, что сам не понимает как работает эта бесовщина, дескать переписал у коллеги. Допрашивали коллег, никто ничего не знает! В отчаянии, желая хотя бы понять, как оно работает, один из математиков таки разобрался в тайне алгоритма. Можете почитать по ссылке в Вики, там листов на десять формул. Кому лень читать формулы, перескажу тот кусок, что мне удалось понять. Короче это вариация итерационного метода Ньютона для приближенного нахождения корня уравнения y -1/√x=0. Для первой итерации алгоритму нужно скормить какое-нибудь начальное значение, не слишком сильно отличающееся от корня. Это начальное значение и вычисляет адская абракадабра 5F3759DF − (x >> 1). Сдвиг я ещё как-то понимаю, хотя выглядит он в применении к числу формата float дико. Что такое формат float не знаете наверное, а, дети языка python с его утиной типизацией? Но наверное слышали, что внутри компьютеры знают только два числа, 0 и 1. Эта штука называется двоичной записью. У неё есть такая проблема, оч сложно записывать большие числа. Чтобы записать 1000 в двоичном надо использовать десять нулей и единиц. Миллион и того больше. Поэтому талантливые доисторические программисты придумали формат записи чисел float или по русски формат с плавающей точкой. В этом формате вы делите число 1234 на две части: 1.234 и 1000, которые при использовании надо умножать. Экономия тут в том, что первое число можно чутка обрезать с хвоста жертвуя точностью, а 1000 записывать как десятичный логарифм, то есть как 3. Число 1.234 называется мантиссой. Что такое мантисса я со второй попытки узнал. С первой попытки я увяз в книге позднеантичного философа Александра Афродисийского "Мантисса или дополнение к Душе". Имеется ввиду естественно трактат Аристотеля "Душа". Не пробуйте, про мантиссу и логарифмы там ничего нет. Вторая попытка вышла сама собой когда у меня случилась истерика, из-за того, что я понял, что забыл как пользоваться таблицей логарифмов. Скачал школьные таблицы Брадиса, тут-то всё и разъяснилось. Логарифм от 1234 это логарифм от тыщи, то есть 3 плюс маленький довесок - что то там 0.0913 и так далее. В таблицах считается, что про тыщу и тройку ты и так сообразишь, там пишут только этот довесок, по латыни мантисса это и есть довесок, добавка или дополнение. В формате float мантиссою называется множитель перед тыщей и он вовсе не маленький и не добавка. Называют его так по глупости, Дональд Кнут например против такого названия. Кто такой Кнут тоже небось не знаете. Это великий программист прошлого который написал мегакнигу "Искусство программирования". В ней неизвестное количество томов, для того чтобы её сверстать он написал гениальную систему верстки TeX и систему создания шрифтов Metafont. На это у него ушло много лет. После этого он всю жизнь писал мегакнигу.
