Удивительная История Алгоритма Нахождения Обратного Квадратного Корня из Quake III
Я, кажется, как-то уже писал, что не считаю себя труЪ программистом. Я скорее разработчик, использующий строительные блоки, созданные другими, чтобы собрать из них что-то работающее, как из деталей конструктора. Настоящими же программистами лично я считаю людей, создающих уникальные алгоритмы или эффективные способы хранения данных и манипуляций над ними.
И сегодня речь пойдёт как раз о таком случае. Дейв Пламер на своём канале рассказывает историю одного такого алгоритма вычисления обратного квадратного корня, который нашли в выпущенном в 2005м году исходном коде игры Quake III Arena.
В двух словах. Графика в игре постоянно имеет дело с векторами. И самой распространённой задачей является нормализация вектора, т.е. преобразование заданного вектора в вектор в том же направлении, но с единичной длиной. Например, для вектора
{x, y, z}, его длина будет определяться как sqrt(x*x + y*y + z*z), а нормальный вектор получится путём деления каждой величины на эту длину. Таким образом, задача состоит в быстром нахождении значения 1.0/sqrt(x).Алгоритм, представленный в исходном коде Quake III, не имел ничего общего с обычными алгоритмами нахождения квадратного корня, вроде итеративного нахождения корня функции. Он же использовал приведения чисел с плавающей точкой в целые и обратно, а также магическую константу. И при этом он работал в 30 раз быстрее.
Подробнее в 2х частях видео от Дейва Пламера:
- Часть 1
- Часть 2
Сразу предупреждаю, очень много математики.