Считай обратный корень быстро с волшебной константой 0x5f3759df

Привет! В этом видео рассматриваем кусок кода из Quake 3 Arena. Тут использована неочевидная оптимизация, о которой захотелось поделиться.

Расшифровка видео
Что и зачем
0:00
[музыка]
0:10
Обожаю эту игру Приветствую вас дорогие
0:13
мои все меня зовут Антон Филатов вы на
0:16
одноименном канале и сегодня мы
0:18
проскинем мозгами над кусочком кода из
0:20
Quake 3 Арена для начала рекомендация
0:23
Посмотрите Вот это видео о числах
0:26
плавающей точкой потому что здесь это
0:28
будет важно мы поговорим о том как еще в
0:30
99 году программисты из isftware хорошо
0:34
знали формат хранения чисел в памяти а
0:37
еще Они знали математику и поэтому они
0:39
смогли придумать лайфхак для вычисления
0:41
в игре которая ускорило выполнение кода
0:45
Раз в пять или шесть и этот кусок кода
0:47
взрывает мозг до сих пор вот этот кусок
0:49
кода фейк писался на си поэтому год носи
0:53
понятно что читать таком виде код сложно
0:55
поэтому давайте я переведу его в
0:58
псевдоход программисты меня потравят
1:00
если я ошибся но с этим ходом нам будет
1:03
гораздо проще разбираться прежде чем
1:05
погрузиться в созерцание кода сначала
1:07
разберемся что он делает Ну из названия
1:09
функции понятно он вычисляет значение 1
1:12
поделить на Х это была критическая
1:15
операция во время программирования
1:16
третьего кэйка потому что из всех
1:18
шутеров Quake был одним из первых где
1:21
было включено глобально динамическое
1:23
освещение Если вы помните там и от
1:26
взрывов ракет по-разному было освещение
1:28
и от того как добрался
1:31
тогда тоже все вокруг предметы начинали
1:34
светиться из компьютерной графики
1:36
известно что такое динамическое
1:37
освещение требует постоянно вычисления
1:40
векторов Нормалек к поверхности и
1:42
длинные этих нормалей так вот это
1:45
величина один поделить на корень из X
1:47
как раз и нужно для вычисления длины
1:50
вектора
Восхищаемся кодом
1:51
Итак давайте разбираться первая строчка
1:54
это представление битов числа с
1:56
плавающей точкой в виде битов целого
2:00
числа важно Это не просто округление это
2:04
именно что представление битов одного
2:06
формата вбитых другого формата
2:09
пока сразу не понятно Зачем
2:11
следующая строчка она еще больше
2:13
вызывает вопросов в адекватности
2:15
разработчик
2:16
комментарий он был оставлен в
2:18
оригинальном коде видимо один
2:20
единственный человек это понимал это
2:22
запрограммировал остальные просто
2:23
удивлялись здесь видно что Из некоторой
2:26
константы 16 вечном виде почитается
2:28
половина числа из которого мы хотим
2:30
квадратный корень согласитесь безумно
2:33
Интересно как они до этого дошли до
2:35
этого вообще можно догадаться Давайте
2:37
разбираться как это выглядит тематически
Разбираемся в математике
2:39
Давайте вспомним как хранятся числа флот
2:42
в памяти Вот например число 5.5 если
2:45
интерпретировать это число по частям как
2:47
это принято в формате float то сначала
2:50
нужно выделить порядок это со второго по
2:53
9 Вот это число
2:56
при этом Сначала мы можем его
2:58
интерпретировать Как целое число Да мы
3:00
берем последнюю единицу умножаем ее на
3:03
два нулевой прибавляем предпоследний
3:06
ноль умножаемый на 2 1 плюс 0 плюс 0
3:09
плюс 0 и так далее до последней единицы
3:11
которую мы умножаем на 2 в 7 и в итоге
3:14
мы получаем 129 вот этот целочисленное
3:17
восприятие порядка будем называть буквой
3:20
Е большое для того чтобы получить
3:22
истинное восприятие порядка во флоте мы
3:25
должны из этого значения вычесть еще 127
3:28
в нашем случае получится 2 Давайте же
3:31
тогда запомним что порядок в смысле
3:33
флота это солочисленный порядок минус
3:36
127 в это время мантиса в интерпретации
3:39
флота это 0 на 2 минус 1 плюс 1 2 минус
3:43
второй плюс еще один на 2 минус 3 плюс 0
3:47
на 2 минус 4 и так далее дальше все
3:50
идущие нули умножаются на все убывающей
3:52
степени двойки Давайте такую
3:53
интерпретацию флота называть буквой М
3:57
маленькая
3:58
при этом точно также как с порядком мы
4:01
можем интерпретировать мантису Как
4:04
целочисленное число
4:05
поесть брать последний бит 0 умножать
4:09
его на нулевой прибавить предпоследний
4:12
бит еще один ноль умножить на 2 1 и так
4:14
далее складывать все нули пока не дойдем
4:16
до первой единицы которая умножится на
4:19
220 потом еще одна единица умножиться на
4:22
2 в 21 ну и 0 на 2 22 такую
4:26
интерпретацию мантисы будем называть м
4:30
большое теперь вспомним что в терминах
4:32
маленьких букв то есть формате float
4:34
число выражается как два в степени E
4:38
умножить на 1 плюс м а если же на все
4:41
это число смотреть как на целое
4:44
то формула выглядит как М большое плюс е
4:48
умножить на 2 23 Откуда взялось 2 в 23
4:52
спросите вы ну Давайте попробуем
4:54
интерпретировать это число как
4:57
целочисленное сразу же Если бы мы ничего
4:59
не знали про М И Е мы бы взяли последний
5:01
бит 0 умножили бы его на два в нулевой
5:05
прибавили бы к нему при последней бит
5:07
умножено на 2 1
5:10
предпоследний Бит 2 в квадрате и так
5:13
далее мы делали бы все эти операции
5:14
поначалу первые 23 числа даровали бы нам
5:18
ровно м
5:19
да потом обе переступили с
5:22
мантиса на порядок и продолжили бы
5:26
традиционное умножение чисел на два
5:28
возрастающей степени следующий бы число
5:30
было бы 223 единицу умножить на 23 плюс
5:34
0 на 224 плюс 025 плюс 000 и так далее
5:40
вплоть до 1 на 230
5:43
а теперь если мы внимательно посмотрим
5:45
на последние 8 слагаемых которые
5:47
отвечают за порядок и вынесем за скобку
5:50
общий множитель 2 23 то в скобках
5:53
останется ровно то что мы договорились
5:56
называть я большое Ну и кстати если мы
6:00
из первых 23 слагаемых вынесем 23 за
6:03
скобку то в скобках останется как раз
6:06
маленькая Респект вам зато что до сих
6:09
пор не выключили это видео напоминаю мы
6:11
пытаемся разобраться про странный код в
6:14
третьем Quake что ж мы близки уже
Самая страшная простыня формул
6:17
давайте сейчас выпишем те формулы
6:19
связывающие порядок и мантиссу который
6:21
мы уже знаем просто чтобы они не
6:23
потерялись Итак вот воплощение числа
6:26
выглядит как два в степени на Один плюс
6:29
м с маленькими буквами
6:31
винтовое воплощение этого же числа
6:34
выглядит как М + Е умножить на 23
6:40
при этом е большое и я маленькая
6:42
связанное почитанием 127
6:45
а м большое м маленькая связаны деление
6:48
на 23 Теперь мы с вами готовы пойти по
6:51
тому пути по которому шли программисты
6:53
квейка когда вычисляли значение 1 /
6:55
корень из X то есть мы имеем выражение
6:58
Y равно 1 на корень из X Ну или Давайте
7:01
Даже его перепишем как
7:02
y равен x в степени минус 1/2
7:06
поскольку И то и другое число в формате
7:08
float то Согласно Формуле 1 мы можем
7:11
подставить ровно вместо Y и X А их флота
7:15
выражение вы просто поставили вместо
7:17
икса выражение по формуле 1 и Вест Ирика
7:21
то же самое выражение А теперь мы
Врываются логарифмы
7:23
сделаем страшно про логарифмируем левую
7:26
правую часть по основанию 2 стой стой
7:28
стой не выключай это не страшно это
7:32
просто логарифм
7:34
не нужно вспоминать сейчас школьные
7:37
знания из логарифмов
7:38
всё что нам сейчас понадобится это
7:41
известное правило о том что логарифм
7:44
произведения это сумма логарифмов помощь
7:46
была такая как мантра заученные слова
7:49
и еще одна мысль что если мы берем
7:52
логарифм от А в степени B то B можно
7:56
вынести как коэффициенты это тоже вроде
7:58
заучилась как мантра вообще не будем
8:00
сейчас сдаваться подробности почему
8:02
зачем и как
8:03
просто объясню что логарифм здесь нужны
8:05
потому что мне не нравится 2 степени е я
8:09
хочу от нее избавиться тогда слева
8:11
вместо произведения мы получим сумму
8:14
логарифмов
8:16
а справа минус 1/2 так как вынесенную
8:19
степень умноженную на сумму логарифмов
8:22
Ну и сразу видно что логарифм по
8:24
основанию 2 от числа 2 степени E это
8:26
ровно е тогда преобразованная формула
8:29
выглядит вот так
8:31
с первого взгляда может показаться что
8:34
стало еще более запутанным
8:37
был сначала понятный корень а сейчас
8:40
непонятное выражение еще какими-то
8:42
логарифмами
8:44
такой же Соблазн был и у разработчиков
8:47
квейка но они не испугались они заметили
8:50
что график функции
8:52
y равен логарифм X + 1
8:55
очень похож на график функции
8:58
y равен X вот эти графики вот видно
9:01
сверху идет логарифм снизу идет прямая и
9:05
действительно Они похожи но еще больше
9:08
похоже логарифм и вот такая прямая
9:10
просто сдвинуть немного
9:14
можно показать что лучше всего подойдет
9:18
прямая сдвинутая на вот такую Константа
9:20
Какой вывод что вместо логарифма 1 + X
9:23
можно писать X + Константа Давайте
9:28
называть эту константу буквой C чтобы
9:29
постоянно не писать теперь вернемся к
9:32
нашей страшной формуле с логарифмами и
9:35
заменим везде логарифм 1 + M на M + C
9:40
согласитесь теперь формула выглядит
9:42
значительно приятнее теперь везде вместо
9:46
маленьких букв воспользуемся формулами 3
9:48
и 4 чтобы поставить большие и попытаемся
9:52
сделать некоторые преобразования слева и
9:54
справа чтобы там и там получить
9:55
интерпретацию числа X и Y В смысле числа
9:59
int получается вот так проверить это
10:03
просто поставляем формулу связывающая
10:05
маленькая большое и я маленькая е
10:07
большое теперь оставим в левой части
10:10
только то что касается Y а 127 и C
10:14
перенесем в правую часть и справа в
10:17
скобках оставим только то что касается
10:19
икса АС и 127 вынесем за скобки не
10:24
забудем умножить на минус 1/2 у меня
10:26
после проведения всех подобных
Математика совпадает с кодом
10:28
получилось вот так
10:33
где я потом не забываю подставить ровно
10:36
X в Интел интерпретации ровно Y в
10:39
интовой интерпретации
10:41
и вот у нас появился X умноженный на
10:44
минус 1/2 как это было в исходном коде А
10:47
теперь Угадайте если вот такое число
10:50
посчитать на калькуляторе перевести в
10:54
шестнадцатеричную форму какое число
10:56
получится
10:58
Ну конечно Вот это число и получается
11:01
дальше Судя по коду мы преобразовываем
11:04
получившееся число обратного флота
11:06
выйдет и делаем эту строчку эта строчка
11:11
это шаг метода Ньютона надо бы сделать
11:13
отдельное видео про метод Ньютона пока я
11:16
просто скажу что метод Ньютона
11:18
используется для приближения значения
11:20
решения если это решение искалось
11:24
приближенно как нашем случае да мы же
11:26
логарифм когда заменяли мы ушли точно в
11:29
равенства к неточному и в итоге мы
11:32
получили приближенное значение Ну я уже
11:35
не говорю о том что приближение
11:36
логарифма работает только на некотором
11:38
интервале А корни Мы хотим извлекать из
11:41
любого числа
11:42
Поэтому нам неизбежно приходится
11:43
применять небольшое приближение к
11:47
истинному значению и Вот так мы
11:49
разобрались с тем как вычисляли обратный
11:51
корень в далеком девяносто девятом году
11:53
разработчики койка это все конечно
И что?
11:56
классно но вот тебе вопрос зачем
12:00
Неужели в 99 году не могли просто
12:03
извлечь квадратный корень могли конечно
12:05
Проблема в том что взять квадратного
12:08
корня это дорогая операция для
12:10
процессора процессор любит операции
12:12
сложения и умножения
12:15
взять от корня я не знаю как оно точно
12:17
реализовано скорее всего там замешан ряд
12:21
Тейлора но лезть туда не хочу совсем наш
12:24
метод не требует никакого извлечения
12:27
кормят он работает только на умножение
12:29
Ну один раз придется поделить на 2 Но
12:32
для компьютера деление на 2 такая же
12:34
приятная операция как для нас людей
12:36
деление на 10 это просто откусывание
12:39
одной цифры от числа получившийся
12:41
алгоритм работает в несколько раз
12:43
быстрее чем классическое излечение корня
12:45
я набрала небольшой код который
12:48
сравнивает время вычисления обычного
12:50
обратного корня и нашего это сейчас
12:54
время работы вычисляется в наносекундных
12:56
тогда оно вычислялось микросекундах или
13:00
даже миллисекунды
13:01
и тогда сокращение в 5 раз это было
13:04
очень серьезное сокращение для
13:07
количества операций и тогда в 99-м это
13:10
позволило сильно сократить требования к
13:12
железу игроков Ну я еще не говорю про
13:14
потенциал который остался
13:15
нереализованным потому что во всех тех
13:18
вычислениях которые мы проделали
13:20
значение минус 1/2 как значение степени
13:23
в котором мы возводили X она была нам
13:25
просто дано Но вообще говоря ничего бы
13:28
не поменялось заменимый минус 1/2 -1/3
13:31
или даже плюс одну четверть сработали бы
13:34
все те же лайфхаки и идеи поменялось бы
13:38
раз Константа и два Константа остальное
13:42
было бы тоже самое Надеюсь вы сейчас
13:45
также Кайфанули как и я когда разобрался
13:47
в том как это работает и как Кайфанули
13:49
разработчики когда это придумали и мы с
13:52
вами вместе уважаем разработчиков квейка
13:54
еще сильнее пойти что-то поиграть 5
13:57
минут Ну а если вы досмотрели видео до
13:59
конца то Поговори со мной понравилось
14:02
вам или не понравилось может быть где-то
14:05
ошибся и до встречи следующий раз

Поделиться: