1:45 Нормаль - это вектор с длинной равной 1. "Вычислять длину нормали" - этот как минимум абсурдно. :) Обратный корень как раз таки нужен для вычисления этой нормали - нормирования. Обратный корень от квадрата длины вектора (что есть просто возведение в квадрат компонентов со сложением) как раз и даёт величину, на которую нужно умножить каждую компоненту вектора, чтобы его длина стала единичной - сделать нормалью. Ну и вычисляем именно обратный корень, потому что операция деления сложнее чем операция умножения. 11:33 Для любого float числа мантисса 0
Полагаю, что в процессоре при извлечении корня, скорее всего, используется то же представление и показатель делится пополам (видимо, с переносом нечётного бита на мантиссу), а вот мантисса уже методом Ньютона досчитывается. В принципе они в fast_inv_sqrt выиграли за счёт того, что в процессоре не было именно встроенной функции inv_sqrt и за счёт меньшего числа итераций. Процессор должен покрыть весь диапазон с максимальной точностью, а им точность была не так важна. Хотя я видел версии fast_inv_sqrt, где было несколько итераций.
Мне кажется ты путаешь понятия. Нормаль к плоскости - вектор который перпендикулярен плоскости. У него нету ограничения на длину. А вот нормализованный вектор, это вектор с длиной 1.
Похоже в графике так не принято как в матеше, если вы математик, в графике под нормалью понимают перпендикуляр к плоскости. Просто её задают XYZ вектором и после матричных преобразований (растяжений по оси и поворотов) объектов, нормализация затратный процесс и не всегда нужен, а нормаль хоть и не нормализована но продолжает выполнять свою функцию - указывать направление :D
Как сказал один умный человек, "настоящее программирование начинается там, где заканчиваются вычислительные ресурсы". В конце 90-х, для ускорения вычисления графики на моем 486-м, использовал вставки на ассемблере (прямая адресация в видеопамять и синхронизация кадра с обратным ходом электронного луча ЭЛТ), и составлял таблицы с вычисленными значениями синуса и косинуса для ускорения афинных преобразований координат.
Мне 35 и я далёк от программирования. В школе и университете постоянно слышал о том, что программирование есть сплошная математика (это не так). Но это видео продемонстрировало как математика может быть прикладной в жизни. Автор, ты - монстр. Спасибо за исследование.
Господи как же это круто! Вот это реально настоящие программисты! Большой респект и вам за то что сделали такой хороший обзор. Напомнило мне ситуацию когда надо было написать равномерное движение по кривым Безье, но без дифференциалов, интегралов, метода Ньютона (потому что я слишком тупой для этого). 4 недели тычил пальцем в небо, но нашел приемлемое в рамках задачи упрощение и нашел таки сложное уравнение которое и движение делало равномерным (визуально) и не требовало знаний высшей математики и не использовало огромных ресурсов при выполнении
Спасибо вам за ваши слова! Мне кажется, что мы с вами нашли друг друга, поскольку я вижу цель моего канала именно так: рассказывать о том, что может сделать математика без долгих и сложных выводов. Ваш комментарий поддерживает веру, что я это делаю с пользой для окружающих :)
У меня был недавно проект с одной железякой, которая должна была вычислять сложое значени с сплавающей точкой. Но МК достаточно сабая вещь и я занимался лианиризацией подобнлй функции)) в итоге использовал пайтон и сделал формулку, которая была намного проще, чем исходная загагулина (на этом пайтон большен е понадобился. И все, проект заработал на МК. Оказывается сделал то, что делали предки и до меня)))) мне контент зашёл, молодчина!
Где-то читал, что Кармак подсмотрел этот трюк у CGI (уж не знаю где именно они его использовали и придумали ли сами или тоже у головастых математиков подсмотрели), но подписался :)
Для тех, кто изучает C/C++: Подход "i = *(long*)x" не является нормой. В Quake III работал хорошо, но для современного компилятора при высокой оптимизации это может привести к ошибкам. Причина сложна (гуглить "strict aliasing", если хочется узнать больше), но правильной альтернативой будет "memcpy(&i, &x, 4)". Также хорошей идеей будет использовать "uint32_t" вместо "long", чтобы убедиться, что "i" имеет 4 байта. В современных системах "long" часто имеет размер 8 байт.
спасибо за разбор, алгоритм действительно гениален, хотел бы заметить что на больших цифрах этот метод не всегда выдает точный результат, преблизительное значение в играх это круто но не в реальных мат проектах!
Вообще не совсем. Его относительная точность зависит не от размера числа, а от того, насколько значение мантиссы близко к двум точкам, являющимися пересечением log2(1+m) c аппроксимирующей прямой. Например, для числа 1.25 или 1.75 он даст значительно лучшую точность, чем для 1.0 или 1.5. Ну и соответственно для других чисел, являющимися результатом перемножения на степень двойки: для 5 и 7 будет точнее, чем для 4 и 6; для 1280 и 1792 точнее чем для 1024 и 1536. Но учитывая, что в реальных условиях значение мантиссы будет чисто случайным, то и точность вычислений будет скорее опысаваться неким средним значением ошибки. Но вообще, люди считали, точность непосредственно самого метода взятия обратного квадрата без последующего приближения не хуже 2%, т.е. можно получить правильными почти две первые значащие цифры. Первое приближение практически удваивает количество правильных значащих цифр.
Я окончил бакалавриат по ИВТ и сделал где-то 20 курсачей вокруг похожей темы и сначала офигел с того, какая ересь тут происходит. Дело в том, что я реализовывал двоичные автоматы для преобразования числа из float-формата в int и наоборот, а здесь решается обратная задача. Один и тот же набор символов ИНТЕРПРЕТИРУЕТСЯ как float или int, но эти числа не совпадают. В видео очень не хватает одной вещи для понимания: в числе: 11111111 | 000000000000000000000000 Нули это m/M, а единицы это e/E. Конкретная форма зависит от того, смотрим мы на набор знаков как на float (тогда мы мысленно подставляем перед рядом нулей единицу и запятую и умножаем все это на два в степени 11111111) или как на int (тогда нам, как людям, будет проще просто посмотреть на число целиком и перевести из двоичной системы счисления в десятичную, но компьютеру нужно объяснить все манипуляции по тому, что вообще значит мантисса. Чтобы создать такой int, который будет ВЫГЛЯДЕТЬ абсолютно как этот float, нужно выполнить перечисленные операции для E и M. Абсолютно гениально и удивительно, что эта задача вообще кому-то пригодилась.
судя по приведённым данными расчёта, относительная точность метода около 1 процента, что и неудивительно - всего 1 итерация метода Ньютона. Для игры, этого наверное вполне достаточно, но в общем случае необходима точность соответствующая типу float или double. В целом, получаётся, что данный hack позволяет получить хорошее начальное приближение для старта итерационного метода. Весьма поучительно, впрочем, что анализ машинного представления числа помогает получить такого рода оптимизации.
строго говоря, приведенный код, в буквальном его виде работать не будет. здесь надо ввести локальную переменную float y = *(float*) & i; и итоговая величина : y = y*(1.5f - 0.5f*x*y*y); return y; и кстати, эта итерация метода Ньютона, эквивалента разложению по Тейлору функции 1/sqrt(x) вблизи значения найденного hack-методом. повторение последней строки ещё два раза ведёт к повышению точности результата почти до полной точности представления числа типа float: y = y*(1.5f - 0.5f*x*y*y) ; y = y*(1.5f - 0.5f*x*y*y) ; y = y*(1.5f - 0.5f*x*y*y) ; return y; при переходе к последующей строке, 'y' выступает как новое приближение. Дальнейшее повторение этой строки не ведёт повышению точности - упирается в точность формата float. Интересно было бы аналогичный алгоритм сделать для double. то есть надо найти соотвествующую чудо-константу для double :)
Интересно, очень интересно! Я преподаю численные методы и подобные находки - просто изюм в булочке обычных численных методов. Любопытно ещё сравнить ТОЧНОСТЬ подобного вычисления обратного корня, велика ли погрешность?
Ну дак, в ID software настоящие программисты работают. Одни из немногих, кто действительно заморачивался с оптимизацией. DOOM(2016) выдавал потрясающу графику на устаревшем железе (Core 2Duo E8400 + GTX570 + 8GB DDR2) - на средне-высоких настройках графики не было просадок ниже 55FPS в FHD. Полагаю, и там полно таких странных и гениальных решений. Обычно игры того времени если и шли, то очень скудно, на минималках, с пониженным разрешением. Да и таких красот не могли дать. Можно и в древность заглянуть, первые Doom'ы (1992-1993). Там тоже было довольно немало хитростей.
Первые думы - на самом деле плохой пример. Могу объяснить: даже Сильверман, который был ещё менее компетентен в математике, чем Кармак (и тот и другой написали кучу ненужных asm костылей, хотя на FORTH весь код работал бы с той-же скоростью, что написанный ими, ну да ладно). Даже Сильверман, интуитивно, написал метод быстрее, чем перебор BSP-дерева, использованный Кармаком. И к слову id tech и build - ровесники, - разница только в том, что игры на build появились позже.
Это очень полезная штука в 3Д графике для нормализации векторов. Очень частая операция и там именно нужен не просто корень а обратный. В те времена был FPU. Корень-то был но самое самое тормозное это деление. Оно до сих пор самое тормозное даже сейчас. Поэтому обратные корень очень удобен. Во всех процах где SSE/AVX и GPU это делается lookup таблицей и несколькими итерациями Ньютона-Рафсона для повышения точности.
Спасибо, познавательно! Ну и там, наверное, корректнее 1.0/sqrt(number), чтобы не было возни с переводом из int. А с SSE инструкцией RSQRTSS не сравнивали время? Могу сказать что внутрях ARM-библиотеки для DSP я видел rsqrt делался так же через метод Ньютона, см VRSQRTS в armasm или файл arm_sqrt_q31.c в ARM CMSIS, как это делает Intel в SSE (rsqrtss) или FPU(fsqrt) насколько мне известно коммерческая тайна
1.0 вместо 1, думаю, компилятор сам подставил. Ну, во всяком случае я на это надеюсь 😅 Про RSQRTSS не слышал. Спасибо, что поделились, я попробую разузнать
Здо́рово конечно💪👍 Когда на экране всё пыхает, наверное даже приближённый расчёт незаметен🤔 Вот сейчас эвм мощнее, программистов набирают по объявлению, потом запускаешь приложение, а оно вылетает - индекс массива out if range😂😂😂
соптимизирует, да. Тут в комментариях писали, что подобная штука широко известна для разработчиков железа, компиляторов и мат библиотек, поэтому в современных компьютерах пользы от такой оптимизации будет не очень много
Видео супер! Действительно очень классный алгоритм! Теперь понятно, что видеокарты придумали как раз таки чтобы упростить разработчикам игр жизнь в вычислении всяких обратных корней и прочего. Хотелось бы, конечно, узнать и о других задачах и решениях, с которыми пришлось столкнуться программистам в те времена или наже в наши дни.
Сокращение выполнения кода в 5 раз это однократное выполнение, а в игре скорее всего этот расчет производился десятки тысяч раз. Надо скачать исходники движка (так как они в свободном доступе) переписать этот участок кода используя классический подход вычисления, скомпилировать и сравнить производительность игры (FPS, 1%, 0,1% например) до и после изминений) Эх жаль я не программист(
Насколько я понимаю, этот лайфхак в расчёте КАЖДОЙ точки на экране применялся. Если брать стандарт того времени - 1024*768 * 60FPS, то получаем чуть меньше 50 миллионов таких операций в секунду :)
Трюк классный, но сейчас в нём смысла нет. Если в коде посчитать в лоб, то на x86 компилятор скорее всего использует операцию RSQRTSS, которая в несколько раз быстрее этого трюка. Но это не отменяет красоты и необычности подхода. :)
Тут в комментариях много было холивара на эту тему :) Короткий ответ - да, вы правы, современные компьютеры поддерживают подобные оптимизации на уровне железа, так что сейчас добиться реального прироста сложно. Мой код проверялся на виртуальной машине, максимально приближенной к той, что была в 99м. Сейчас этот хак уже не так актуален
интересный факт: с константой 0x5F3759DF получаем неточность около 0.175%, которая потом падает Chris Lomont вывел вот такую константу 0x5F375A86 и неточность после первой итерации составляет уже 0.09%
Представляю какой у вас шок будет, когда кто-нибудь разберёт код из времён классической демосцены. ) Некоторых современных т.н. "программистов" может часом и удар хватить.
Об этом можно посмотреть в другом видео на этом канале. ua-cam.com/video/qJwkkUyS1WU/v-deo.html Там подробно рассматривается формат хранения данных float и обсуждается, почему из порядка вычитается 127, а к мантиссе прибавляется 1. Если совсем коротко отвечать на ваш вопрос: то так устроен стандарт :)
@@math-to-masses чем рилтайм освещать перевод числа в двоичную систему счисления, лучше бы коротко упомянули про 127. Никаких отсылок про это. Даже на видос из вашего комментария выше. При том, что в нём тоже про перевод числа в двоичную систему рассказывается. Тема интересная. Спасибо.
Уф, это сложный вопрос. Перечисленные вами темы очень обширны. Я точно могу посоветовать книгу Волков - численные методы. На этом канале будут штуки из этой книги рассказываться
А кто-то пробовал приведённый код в видео 0:50 и далее проверить на корректность возвращаемых данных?) Там из-за не совсем корректного/верного использования одной и той же переменной возникает ошибка в вычислениях... в строчке перед возвратом:) Кому не лень, подставте в функцию 4.0... она выдаёт 0.697425 вместо 0.499154
Ничего не понял, но очень интересно. Суть метода это упрощение, подгонка некоторой функции? (Там где для упрощения формулы заменили логарифм.) Круто применять такие решения если можно ограничиться заданной точностью. Но сам метод это компромисс между надо проще и быстрее,и надо точно? Спасибо за видео, в математике не шарю но все равно интересно.
Да, суть в том, что мы жертвуем точностью, но вычисляем быстрее. Оказывается, что так можно сделать не для любой операции. Например, не получится таким вот образом оптимизировать вычисление какого-нибудь синуса от числа. А для вычисления корня математика нашлась
хм... вот насчёт того, что этот алгоритм может переплюнуть оптимизации которые нынче используются при вычислениях подобного рода - в этом сомнения. Во всяком случае, у меня получилось, что в release режиме сборки кода (VisualStudio2022, Intel core I7) использование стандартного 1/sqrt(x) на массиве из миллиона случайных чисел работает примерно в 2 раза быстрее, чем использование этой оптимизации. В debug режиме отрыв не столь большой, но все равно стандартный вызов чуть быстрее. Я думаю, что дело в оптимизациях и аппаратной поддержке базовой арифметики.
Нет, это всегда зависит от задачи. Такой спопосб даёт погрешность в сотых от числа. Иногда это может быть критично. Так что так можно делать только тогда, когда высокая точность не нужна
интересно что подобные моменты критически важны для работы на ограниченных мощностях. Во времена этих 99х годов это было очень к месту. В наши годы же железо хорошо справляется и со сложными операциями. Сейчас это все потыкать и прочувствовать можно на слабеньких платах, типа ардуинок, esp, stm, когда есть реально ощутимое ограничение на количество вычислений. И вот ты в какой то момент ловишь себя на том, что на куче листов представляешь необходимые тебе значения в виде нулей и единиц, а вместо делений и умножений пытаешься переписать все действия на битовых сдвигах, кратности двум, переходу к 8-битным целым вместо 16х и 32х или плавающих точек и тому подобное. В этом есть свой шарм и увлеченность, понимаю ребят из ID)
Не согласен. Тот же DLSS, как и современные реализации рейтрейсинга, и большинства графических наворотов - это попытки упрощения и срезания углов, чтобы меньшими вычислениями добиться крутой картинки.
Сравнение по времени не совсем корректное, даже если опустить возможные оптимизации на уровне CPU, скорее всего вычислять корень придется для множества чисел, а значит для вычисления во float можно использовать векторизацию (если переписать код с развернутым циклом умный компилятор gcc со включенной оптимизацией даже сам сможет это сделать), что ускорит выполнение операций еще в ~8 раз. Так что быстрый обратный корень давольно давно потерял свою актуальность, вопрос даже насколько он был актуален в момент написания, т.к. уже тогда появлялись SIMD инструкции (тот же 3dNow! уже имеет PFRSQRT, а вышел аж в 98).
жаль в современность больше программистов не интересует ускорение, потому что не знают математику и считают что она не нужна, но как показывает пример хороший и оптимизированный продукт отличается от современных игр как раз знанием математики разработчиками
Спасибо :) На самом деле разница будет только в том, что в формате double из порядка надо вычесть не 127, а 1023 (у double на порядок выделяется 11 бит, а не 8, соответственно там будет не 2^7, а 2^10), а также вместо 2^23 нужно подставить 2^52 (потому что на мантиссу там 52 бита, а не 23). Так что изменится только вот эта сама волшебная константа 0х5f3759df, а остальное будет точно так же всё
@@sleirsgoevy Да кто сейчас считает на float? большинство машин 64 битные.Вся встроенная математика С, С++ или С# Math или СMаth ориентированы на операции с double .Более того (по слухам, тут я не уверен) - процессор на самом деле ВСЁ скрытно считает в double, а пользователю под заказ выдает как бы float. А то что точность этого хитрого подхода невелика - ну да, верно. Вопрос - удасться ли сохранить более высокое быстродействие по сравнению с библиотечным double Sqrt(double x)?
@@alexefremov4158 да, с этот способ всё равно быстрее даже с даблом. Другое дело, что дабл обычно используется для повышения точности, а наш способ выдаёт погрешность уже в сотых. О том, что комп всё считает в даблах вместо флоатов - это не совсем так. Правильнее сказать, что современным компам не важно, с чем работать, с тем или с другим (с точки зрения скорости работы)
@@math-to-masses Вычитал в сети нечто такое: 1) "Intel в FPU всегда используется 80-bit precision, а результат потом просто округляется до нужного." и 2) "На некоторых процессорах double вообще не поддерживается аппаратно." Складывается впечатление, что попытки работать напрямую с битами чисел плавно исчезло за горизонтом. Если когда-то писали на С с ассемблерными вставками, то сейчас в них нет никакой нужды.
Формально *(int*)(&x) - можно считать UB для современных стандартов c++. Конкретно на G++ - это не UB. Но может найтись компилятор, который скажет, что это UB
@@mr.i3298 конечно, на современных машинах лучше reinterpret_cast. Код из видео писался на С, там только такие касты есть. Сейчас игры на С, конечно, уже не пишут - сейчас пишут на плюсах и там уже, конечно, "православно" делают
Так-так-так. Видео полезное, но немного истории: лайфхак, который использовал Кармак, был придуман в 1989 году, одним американским математиком и информатиком, занимавшимся оптимизацией вычислений на ЭВМ. Метод был запатентован им-же. Поэтому при всём моём уважении к Кармаку, метод он подсмотрел на 100%, т.к. уже становился доступен интернет, и научные публикации можно было читать без похода в библиотеку. Поэтому как-то так, для исторической справки.
@@neg0dnick769 да в том то и дело. Чем дальше, тем больше уже придумано. Но это можно испытать порешав задачи из проекта эйлера (допустим там первую задачу решило миллион человек, а есть задача, которую только 50 решили)
действительно интересный ролик, но вот подборка цветовой гаммы меня немного напрягла (например, на моменте 7:05). у меня лично от такого синего цвета начали болеть глаза. так что, пожалуйста, автор выбирайте более приятные для глаза цвета (flat ui цвета, например) тогда смотреть ролики будет куда приятнее. спасибо!
Ролик про олдскул. Именно такие цвета были в средах разработки от Borland. Автор не только рассказал про 99 год, но и визуально вернул туда тех, кто застал. Мне эта отсылка была весьма приятна.
Часть с m e замудреная. Но я не вникал. В целом сам факт что простую линию приблизили к логарифму от 0 до 1 забавляет! Ещё бы историю как они это так сделали, читал что один спросил второго, а второй спросил третьего, а третий ничего не помнит так как был обгашен или пьян.
Элементарно спёрли это у математика, который запатентовал метод: причём метод строился на развитии идей "деления умножением." Поэтому, всё что там заявляют пиарщики id (или сами id) - красивые сказки для лопухов. Типа "тихо сп*здил и ушёл, называется изобрёл)", а как я это это сделал, - да хрен знает, - гашеный был. Отличная отмаза
Может я что-то не так делал, но когда я пробовал данный метод, он оказался на порядок медленнее, чем sqrt из стандартной библиотеки c++. Хз почему, особо вникать не стал
Жаль что сегодня так не оптимизируют, а то играли бы киберпанк на ультрах в 4к 500 фпс на rtx3050. Утрирую конечно, но ход мысли думаю понятен. Сам я в свободное время разрабатываю движок, и как оказалось, на моем древнем железе пентиум Е6600 и 9800GT можно такие вещи вытворять, что Хуангу не снилось, хотя к сожалению на мать не ставится больше 4 гигов оперативы в двухканале, ддр2 же, че поделаешь.
@@leptosomic Конечно, с превеликим удовольствием! Но он ооочень сырой и обращаться с ним умею только я. Так как я всего лишь один человек, а не команда, от меня не стоит ждать что-то типа Unreal Engine 5. И даже интерфейса нет, еще не сделал. А приходиться делать движок по частям, а именно, графику отдельно, физику отдельно, интерфейс отдельно, остаётся ещё и работа с сетью и ИИ и т. д. И всё это надо потом как-то соединить, а сеть и ИИ я ещё даже не начинал, так как пока что в этом вообще не шарю, думаю, что наверно закажу алгоритм у опытных людей. Да я вообще новичок и нигде не учился, всё что у меня есть, это амбиции и стремление)) А самое главное, меня завораживает этот древний 775-сокет, не могу от него оторваться, я как-будто околдован, я столько раз хотел обновиться на новое железо, но в своё время не смог, всякий раз были проблемы, в том числе и недавние Ковид с майнингом, отношение Хуанга к своим клиентам (имеются в виду геймеры), что окончательно отбили желание к ПК-геймингу. Я купил наконец-то смартфон и начал в них разбираться, ща играю Фри фаер. Но я не отпустил руки, так как очень хочу доказать, что ещё не все соки выжаты из этого паст-ген железа, а разработчики игр забили болт на оптимизацию и поддержку софта на старом железе и тупо перешли на новое следуя маркетингу. То есть ещё можно делать шедевры на старье, по крайней мере я так думаю. Движок ещё не закончен, так как надо заниматься ещё банально и насущным хлебом, работать, так сказать, а кодинг это хобби, точнее один из хобби. Но есть ещё одна проблема на данный момент - я наконец-то продал комп... А 775-х матерей уже трудно найти даже на вторичке, хотя когда-то был момент, что их на помойках и свалках находили, притом в рабочем состоянии, хоть попой жуй, а сейчас их редкие барыги как раритет продают, мягко говоря по завышенной цене)) Но и это не самая главная причина. А главная причина это моё стеснение. Но раз зашли так далеко, так придётся уже сказать. Тсссс, тихо! Если об этом узнают программисты, они пошлют меня оочень далеко, за тридевять земель, это тааакоой трэээш!)) Короче, я пишу... знаете на чём? На Delphi 7! Уфф, прям от груза избавился! Да, это самая ненавистная и тормознутая среда которую терпеть не могут уважающие себя программисты, так как она предназначена для инженеров, а не для этих самых программистов. Но а я плевал на всякие Си плюс плюсы и Джаву, я самым первым ещё в школе научился писать на Паскале и в этот синтаксис влюблён до гроба! И я намерен идти до конца. Оказалось, есть куча вещей, которых надо исправить, например, так как я новичок, я писал всё на integerе))) А это оказывается тупо разбрасывание памятью направо-налево! Ща профессионалы делали бы фейспалм, читая это)) Значит надо использовать байты, а ещё лучше побитовые функции, но тогда придётся углубиться до Ассемблера, а в идеале - знать некоторые машинные коды и чистить мусор в регистрах. Вот уж тогда, думаю 775 точно восстанет из мёртвых!)) Нет, я согласен перейти на нормальный, "человеческий" язык, например Си++ или Си#, но при условии, что синтаксис будет Паскалевским. Вот так вот.
Забыл упомянуть, я остановился на физике, точнее на разрушаемости объектов, хотя есть такие игры, забыл названия, разрушаемость там - Майкрафт курит в сторонке, но у них хромает графика, так как требует больших ресурсов, а например, Батла имеет шикарную графику, но физические разрушения в основном, заскриптованы и обычному игроку незаметны, а дотошные Сталкаши разберут их в пух и прах. То есть приходится выбрать либо вид, либо функционал. А я хочу их объединить их, притом оптимально, чтобы фпс был в пределах разумного. Я много видосов посмотрел про всякие SSAO, MSAA, анизотропную фильтрацию и много других, есть очень классный парень, автор канала Alek OS, еще Onigiri и Вектозавр. Кстати, я буду применять векторную 3Д графику, а текстуры будут использоваться только на стадии разработки игры, а в готовой игре их не будет. А проблема, из-за которой нельзя собрать команду разработчиков такая: я не могу всю мою идею им рассказать как есть, вот очень кстати подошёл бы нейралинк от Илона Маска, я бы свою мысль за считанные секунды передал бы команде)) Вот такие вот дела...
Нашел видео Nemean'а (у которого 3.8 млн просмотров за 2 года) и решил по-быстрому запились контент? Или просто перевод для тех, кто не умеет в английский?
об этом говорится в видео, указанном в аннтоациях - про хранение числа с плавающей точкой. Если коротко, то так устроен формат float - мы хотим уметь хранить и положительный порядок, и отрицательный. Всего 8 бит выделяется на порядок. То есть это числа от 0 до 255. Половина должна быть отдана на положительный порядок, а половина - на отрицательный. Поэтому граница проходит по числу 127, как половина от 255
Ид-софтвер - всегда держали марку - хорошей и качественной оптимизации. Разбор действительно хороший) (так-же восхищает количество представительниц прекрасного пола в комментариях.. - Не поделитесь статистикой - сколько вообще из них, просмотрели ролик в % соотношение...(я не сексист Т_Т))
![Кватернионы | Вращение в 3D [Самая суть]](http://i.ytimg.com/vi/tBYXR_fAXSQ/mqdefault.jpg)
![Кватернионы | Вращение в 3D [Самая суть]](/img/tr.png)
1:45 Нормаль - это вектор с длинной равной 1. "Вычислять длину нормали" - этот как минимум абсурдно. :) Обратный корень как раз таки нужен для вычисления этой нормали - нормирования. Обратный корень от квадрата длины вектора (что есть просто возведение в квадрат компонентов со сложением) как раз и даёт величину, на которую нужно умножить каждую компоненту вектора, чтобы его длина стала единичной - сделать нормалью. Ну и вычисляем именно обратный корень, потому что операция деления сложнее чем операция умножения.
11:33 Для любого float числа мантисса 0
Всё правильно сказали, да. Спасибо!
Полагаю, что в процессоре при извлечении корня, скорее всего, используется то же представление и показатель делится пополам (видимо, с переносом нечётного бита на мантиссу), а вот мантисса уже методом Ньютона досчитывается.
В принципе они в fast_inv_sqrt выиграли за счёт того, что в процессоре не было именно встроенной функции inv_sqrt и за счёт меньшего числа итераций. Процессор должен покрыть весь диапазон с максимальной точностью, а им точность была не так важна.
Хотя я видел версии fast_inv_sqrt, где было несколько итераций.
Мне кажется ты путаешь понятия. Нормаль к плоскости - вектор который перпендикулярен плоскости. У него нету ограничения на длину. А вот нормализованный вектор, это вектор с длиной 1.
Похоже в графике так не принято как в матеше, если вы математик, в графике под нормалью понимают перпендикуляр к плоскости. Просто её задают XYZ вектором и после матричных преобразований (растяжений по оси и поворотов) объектов, нормализация затратный процесс и не всегда нужен, а нормаль хоть и не нормализована но продолжает выполнять свою функцию - указывать направление :D
@@levshx так вот как раз в математике под нормалью это и понимают
Как сказал один умный человек, "настоящее программирование начинается там, где заканчиваются вычислительные ресурсы".
В конце 90-х, для ускорения вычисления графики на моем 486-м, использовал вставки на ассемблере (прямая адресация в видеопамять и синхронизация кадра с обратным ходом электронного луча ЭЛТ), и составлял таблицы с вычисленными значениями синуса и косинуса для ускорения афинных преобразований координат.
Спасибо алгоритмам ютуба что нашёл этот канал, спасибо вам за ваше творчество!
Почему мой мозг не шарит в логике...
Мне 35 и я далёк от программирования. В школе и университете постоянно слышал о том, что программирование есть сплошная математика (это не так). Но это видео продемонстрировало как математика может быть прикладной в жизни. Автор, ты - монстр. Спасибо за исследование.
@@MarkMath можно, пиши XD
Математика там конечно далеко не сплошная, но без неё некоторые задачи не решить
Я в восторге!
Самый приятный геймдев - видос связанный с математикой, который я видел за последние времена
Господи как же это круто! Вот это реально настоящие программисты! Большой респект и вам за то что сделали такой хороший обзор. Напомнило мне ситуацию когда надо было написать равномерное движение по кривым Безье, но без дифференциалов, интегралов, метода Ньютона (потому что я слишком тупой для этого). 4 недели тычил пальцем в небо, но нашел приемлемое в рамках задачи упрощение и нашел таки сложное уравнение которое и движение делало равномерным (визуально) и не требовало знаний высшей математики и не использовало огромных ресурсов при выполнении
Спасибо вам за ваши слова! Мне кажется, что мы с вами нашли друг друга, поскольку я вижу цель моего канала именно так: рассказывать о том, что может сделать математика без долгих и сложных выводов.
Ваш комментарий поддерживает веру, что я это делаю с пользой для окружающих :)
У меня был недавно проект с одной железякой, которая должна была вычислять сложое значени с сплавающей точкой. Но МК достаточно сабая вещь и я занимался лианиризацией подобнлй функции)) в итоге использовал пайтон и сделал формулку, которая была намного проще, чем исходная загагулина (на этом пайтон большен е понадобился. И все, проект заработал на МК. Оказывается сделал то, что делали предки и до меня)))) мне контент зашёл, молодчина!
Видел похожее видео на английском, но там не было момента где бы мне сказали "подожди не выключай" и досмотрел ведь и даже интересно было, спасибо
Я все ждал, пока кто нибудь тот популярный ролик переведёт или интерпретирует. И это случилось)
Смотришь на такое и реально задумываешься как люди прошлого с умом подходили к таким вопросам. Как находили ухищрения для своего времени. Шикарно
Вас ждёт большой успех, рада, что нашла ещё этот чудесный канал в самом начале!
Спасибо за тёплые слова! Я честно не ожидал, что эта тематика настолько большому количеству человек понравится!
Прямо восхищает! Спасибо большое!
Офигенная оптимизация! И офигенное объяснение) спасибо!
Только закончился первый семестр... а тут вспоминать свои знания про логарифмирование функций...
то чувство, когда далёк от темы, а к концу ролика так и не научился "считать обратный корень быстро"
Гениально! Спасибо большое!
Где-то читал, что Кармак подсмотрел этот трюк у CGI (уж не знаю где именно они его использовали и придумали ли сами или тоже у головастых математиков подсмотрели), но подписался :)
Даже не у CGI - там вполне конкретный математик придумал данный алгоритм, и к слову CGI у него лицензировала его.
Огромное спасибо за видео, очень интересно, пилите еще! :)
Офигенный разбор! Спасибо за видео)
Шедеврально
Алгоритмы зарешали, топ контент
Для тех, кто изучает C/C++:
Подход "i = *(long*)x" не является нормой.
В Quake III работал хорошо, но для современного компилятора при высокой оптимизации это может привести к ошибкам. Причина сложна (гуглить "strict aliasing", если хочется узнать больше), но правильной альтернативой будет "memcpy(&i, &x, 4)".
Также хорошей идеей будет использовать "uint32_t" вместо "long", чтобы убедиться, что "i" имеет 4 байта. В современных системах "long" часто имеет размер 8 байт.
Всё правильно сказали
Я не знаю что я смотрю. Мало чего понял но очень интересно )
На парах Артём Юрьевич, а в ютубе Антон Юрьевич...
Контент невероятен
Спасибо, очень круто! 👍
ну за такое не грех и подписаться ))
бро, это очень круто, спасибо!
Очень классный разбор, спасибо!
Классное видео, спасибо большое, теперь знаю чуть больше!
спасибо за разбор, алгоритм действительно гениален, хотел бы заметить что на больших цифрах этот метод не всегда выдает точный результат, преблизительное значение в играх это круто но не в реальных мат проектах!
Вообще не совсем. Его относительная точность зависит не от размера числа, а от того, насколько значение мантиссы близко к двум точкам, являющимися пересечением log2(1+m) c аппроксимирующей прямой. Например, для числа 1.25 или 1.75 он даст значительно лучшую точность, чем для 1.0 или 1.5. Ну и соответственно для других чисел, являющимися результатом перемножения на степень двойки: для 5 и 7 будет точнее, чем для 4 и 6; для 1280 и 1792 точнее чем для 1024 и 1536. Но учитывая, что в реальных условиях значение мантиссы будет чисто случайным, то и точность вычислений будет скорее опысаваться неким средним значением ошибки. Но вообще, люди считали, точность непосредственно самого метода взятия обратного квадрата без последующего приближения не хуже 2%, т.е. можно получить правильными почти две первые значащие цифры. Первое приближение практически удваивает количество правильных значащих цифр.
@@iforand Спасибо, за подрбный ответ!
Как-то натыкался в поисковике на этот код и толком не понял. Теперь немножко понятнее.
Спасибо вам за ваши слова!
Я окончил бакалавриат по ИВТ и сделал где-то 20 курсачей вокруг похожей темы и сначала офигел с того, какая ересь тут происходит. Дело в том, что я реализовывал двоичные автоматы для преобразования числа из float-формата в int и наоборот, а здесь решается обратная задача. Один и тот же набор символов ИНТЕРПРЕТИРУЕТСЯ как float или int, но эти числа не совпадают.
В видео очень не хватает одной вещи для понимания:
в числе:
11111111 | 000000000000000000000000
Нули это m/M, а единицы это e/E. Конкретная форма зависит от того, смотрим мы на набор знаков как на float (тогда мы мысленно подставляем перед рядом нулей единицу и запятую и умножаем все это на два в степени 11111111) или как на int (тогда нам, как людям, будет проще просто посмотреть на число целиком и перевести из двоичной системы счисления в десятичную, но компьютеру нужно объяснить все манипуляции по тому, что вообще значит мантисса. Чтобы создать такой int, который будет ВЫГЛЯДЕТЬ абсолютно как этот float, нужно выполнить перечисленные операции для E и M. Абсолютно гениально и удивительно, что эта задача вообще кому-то пригодилась.
Понятнее не стало, но спасибо за уделённое время
Круто, нужно эту штуку запомнить на будущее
Комментарий для продвижения ролика, именно такие программисты должны быть ;)
Комментарий был оставлен самим Кармаком на code review.
судя по приведённым данными расчёта, относительная точность метода около 1 процента, что и неудивительно - всего 1 итерация метода Ньютона. Для игры, этого наверное вполне достаточно, но в общем случае необходима точность соответствующая типу float или double.
В целом, получаётся, что данный hack позволяет получить хорошее начальное приближение для старта итерационного метода.
Весьма поучительно, впрочем, что анализ машинного представления числа помогает получить такого рода оптимизации.
строго говоря, приведенный код, в буквальном его виде работать не будет. здесь надо ввести локальную переменную float y = *(float*) & i;
и итоговая величина :
y = y*(1.5f - 0.5f*x*y*y);
return y;
и кстати, эта итерация метода Ньютона, эквивалента разложению по Тейлору функции 1/sqrt(x) вблизи значения найденного hack-методом.
повторение последней строки ещё два раза ведёт к повышению точности результата почти до полной точности представления числа типа float:
y = y*(1.5f - 0.5f*x*y*y) ;
y = y*(1.5f - 0.5f*x*y*y) ;
y = y*(1.5f - 0.5f*x*y*y) ;
return y;
при переходе к последующей строке, 'y' выступает как новое приближение. Дальнейшее повторение этой строки не ведёт повышению точности - упирается в точность формата float.
Интересно было бы аналогичный алгоритм сделать для double. то есть надо найти соотвествующую чудо-константу для double :)
При 64 битных числах, точно получается очень высокой к слову, и практически не отличается от искомого.
Интересно, очень интересно!
Я преподаю численные методы и подобные находки - просто изюм в булочке обычных численных методов.
Любопытно ещё сравнить ТОЧНОСТЬ подобного вычисления обратного корня, велика ли погрешность?
Погрешность, конечно, большая. Сотые от числа. Поэтому применять с осторожностью :)
Кармак крутой, знаю это во времён Commander Keen. Уже есть видео, как там он сделал правный скорллинг? )
Чел, какой же ты классный, про метод Ньютона обязательно сними ролик!!!
Ну дак, в ID software настоящие программисты работают. Одни из немногих, кто действительно заморачивался с оптимизацией.
DOOM(2016) выдавал потрясающу графику на устаревшем железе (Core 2Duo E8400 + GTX570 + 8GB DDR2) - на средне-высоких настройках графики не было просадок ниже 55FPS в FHD.
Полагаю, и там полно таких странных и гениальных решений. Обычно игры того времени если и шли, то очень скудно, на минималках, с пониженным разрешением. Да и таких красот не могли дать.
Можно и в древность заглянуть, первые Doom'ы (1992-1993). Там тоже было довольно немало хитростей.
Первые думы - на самом деле плохой пример. Могу объяснить: даже Сильверман, который был ещё менее компетентен в математике, чем Кармак (и тот и другой написали кучу ненужных asm костылей, хотя на FORTH весь код работал бы с той-же скоростью, что написанный ими, ну да ладно). Даже Сильверман, интуитивно, написал метод быстрее, чем перебор BSP-дерева, использованный Кармаком. И к слову id tech и build - ровесники, - разница только в том, что игры на build появились позже.
Это очень полезная штука в 3Д графике для нормализации векторов. Очень частая операция и там именно нужен не просто корень а обратный. В те времена был FPU. Корень-то был но самое самое тормозное это деление. Оно до сих пор самое тормозное даже сейчас. Поэтому обратные корень очень удобен. Во всех процах где SSE/AVX и GPU это делается lookup таблицей и несколькими итерациями Ньютона-Рафсона для повышения точности.
Я думал глаза просто выпадут в итоге
Спасибо, познавательно! Ну и там, наверное, корректнее 1.0/sqrt(number), чтобы не было возни с переводом из int. А с SSE инструкцией RSQRTSS не сравнивали время? Могу сказать что внутрях ARM-библиотеки для DSP я видел rsqrt делался так же через метод Ньютона, см VRSQRTS в armasm или файл arm_sqrt_q31.c в ARM CMSIS, как это делает Intel в SSE (rsqrtss) или FPU(fsqrt) насколько мне известно коммерческая тайна
1.0 вместо 1, думаю, компилятор сам подставил. Ну, во всяком случае я на это надеюсь 😅
Про RSQRTSS не слышал. Спасибо, что поделились, я попробую разузнать
@@math-to-masses делается приблизительно так:
#include
#include "immintrin.h"
float sse_rsqrtf (const float a)
{
__m128 b, t;
float res;
b = _mm_set_ss (a);
t = _mm_rsqrt_ss (b);
_mm_store_ss (&res, t);
return res;
}
int main()
{
std::cout
Кислотно-жёлтые тексты с мелким шрифтом на кислотно-синем фоне...
Зачем? За что?
Здо́рово конечно💪👍
Когда на экране всё пыхает, наверное даже приближённый расчёт незаметен🤔
Вот сейчас эвм мощнее, программистов набирают по объявлению, потом запускаешь приложение, а оно вылетает - индекс массива out if range😂😂😂
В бенчмарке также стоит попробовать сравнить ещё и с pow(x, -0.5f). Хотя возможно современный компилятор это соптимизирует в такой же код :)
соптимизирует, да. Тут в комментариях писали, что подобная штука широко известна для разработчиков железа, компиляторов и мат библиотек, поэтому в современных компьютерах пользы от такой оптимизации будет не очень много
Нифига не понятно, НО очень интересно)
Красиво написан код на С++. 🙂
Хотя для единичных бенчмарков цифры и показательные, я бы подряд побольше итераций запустил и посчитал время.
Видео супер! Действительно очень классный алгоритм! Теперь понятно, что видеокарты придумали как раз таки чтобы упростить разработчикам игр жизнь в вычислении всяких обратных корней и прочего. Хотелось бы, конечно, узнать и о других задачах и решениях, с которыми пришлось столкнуться программистам в те времена или наже в наши дни.
Сокращение выполнения кода в 5 раз это однократное выполнение, а в игре скорее всего этот расчет производился десятки тысяч раз. Надо скачать исходники движка (так как они в свободном доступе) переписать этот участок кода используя классический подход вычисления, скомпилировать и сравнить производительность игры (FPS, 1%, 0,1% например) до и после изминений) Эх жаль я не программист(
Мне нужна ссылка на исходники и желательно знать как всю эту банду собрать.
Насколько я понимаю, этот лайфхак в расчёте КАЖДОЙ точки на экране применялся.
Если брать стандарт того времени - 1024*768 * 60FPS, то получаем чуть меньше 50 миллионов таких операций в секунду :)
Для каждого полигона, который нужно отрендерить.
я Джун - стажёр,я бы додумался до этого когда нибудь в жизни...но из id Software опередили 😭😭
Го метод Ньютона!
Трюк классный, но сейчас в нём смысла нет. Если в коде посчитать в лоб, то на x86 компилятор скорее всего использует операцию RSQRTSS, которая в несколько раз быстрее этого трюка.
Но это не отменяет красоты и необычности подхода. :)
согласен с вами. Раньше компьютеры были проще :)
Странно, когда я запускал этот код он у меня не работал быстрее чем просто rsqrt. В Doom 3 например разрабы уже этот хак не используют.
Тут в комментариях много было холивара на эту тему :)
Короткий ответ - да, вы правы, современные компьютеры поддерживают подобные оптимизации на уровне железа, так что сейчас добиться реального прироста сложно. Мой код проверялся на виртуальной машине, максимально приближенной к той, что была в 99м. Сейчас этот хак уже не так актуален
очень круто! да! старый id молодцы)))
В Дейва, Кина и Квейки порой поигрываю)
интересный факт:
с константой 0x5F3759DF получаем неточность около 0.175%, которая потом падает
Chris Lomont вывел вот такую константу 0x5F375A86 и неточность после первой итерации составляет уже 0.09%
А я всегда так программирую. Гадаю до талого, а потом говорят гений..)
Представляю какой у вас шок будет, когда кто-нибудь разберёт код из времён классической демосцены. ) Некоторых современных т.н. "программистов" может часом и удар хватить.
зашёл сюда ради quake
Не понял, откуда взялось число 127 для "реального" представления числа Е.
Об этом можно посмотреть в другом видео на этом канале.
ua-cam.com/video/qJwkkUyS1WU/v-deo.html
Там подробно рассматривается формат хранения данных float и обсуждается, почему из порядка вычитается 127, а к мантиссе прибавляется 1.
Если совсем коротко отвечать на ваш вопрос: то так устроен стандарт :)
@@math-to-masses чем рилтайм освещать перевод числа в двоичную систему счисления, лучше бы коротко упомянули про 127. Никаких отсылок про это. Даже на видос из вашего комментария выше. При том, что в нём тоже про перевод числа в двоичную систему рассказывается.
Тема интересная. Спасибо.
@@ИванПиманкин-ш4п можно просто почитать IEEE 754
Классный видос! Спасибо, Антон. Посоветуй пожалуйста какой-нибудь ресурс (ну или бук) по теме вычислительных алгебры и геометрии.
Уф, это сложный вопрос. Перечисленные вами темы очень обширны.
Я точно могу посоветовать книгу Волков - численные методы. На этом канале будут штуки из этой книги рассказываться
Сам Кармак говорил, что этот хак притащил кто-то. Поэтому не смотря на всю его гениальность, разработчики легендарной кваки не причем
зря я математику прогуливал :D
А кто-то пробовал приведённый код в видео 0:50 и далее проверить на корректность возвращаемых данных?) Там из-за не совсем корректного/верного использования одной и той же переменной возникает ошибка в вычислениях... в строчке перед возвратом:) Кому не лень, подставте в функцию 4.0... она выдаёт 0.697425 вместо 0.499154
Ничего не понял, но очень интересно. Суть метода это упрощение, подгонка некоторой функции? (Там где для упрощения формулы заменили логарифм.) Круто применять такие решения если можно ограничиться заданной точностью. Но сам метод это компромисс между надо проще и быстрее,и надо точно? Спасибо за видео, в математике не шарю но все равно интересно.
Да, суть в том, что мы жертвуем точностью, но вычисляем быстрее. Оказывается, что так можно сделать не для любой операции. Например, не получится таким вот образом оптимизировать вычисление какого-нибудь синуса от числа. А для вычисления корня математика нашлась
@@math-to-masses И хорошо что так, а то многие игры требовательны к ресурсам, а подобная оптимизация помогает требования снизить.
хм... вот насчёт того, что этот алгоритм может переплюнуть оптимизации которые нынче используются при вычислениях подобного рода - в этом сомнения. Во всяком случае, у меня получилось, что в release режиме сборки кода (VisualStudio2022, Intel core I7) использование стандартного 1/sqrt(x) на массиве из миллиона случайных чисел работает примерно в 2 раза быстрее, чем использование этой оптимизации. В debug режиме отрыв не столь большой, но все равно стандартный вызов чуть быстрее.
Я думаю, что дело в оптимизациях и аппаратной поддержке базовой арифметики.
Да, вы правильно понимаете - тут самый большой вопрос в аппаратной части. У меня на машине оптимизация работает раз в 5 быстрее
Правильно ли я понимаю, что вычислять обратный квадратный корень в любой современной программе лучше через подобный код?
Нет, это всегда зависит от задачи. Такой спопосб даёт погрешность в сотых от числа. Иногда это может быть критично. Так что так можно делать только тогда, когда высокая точность не нужна
Подскажите название игры
Малым в нее рубился
Quake 3
Ты обожаешь эту игру?
интересно что подобные моменты критически важны для работы на ограниченных мощностях. Во времена этих 99х годов это было очень к месту. В наши годы же железо хорошо справляется и со сложными операциями.
Сейчас это все потыкать и прочувствовать можно на слабеньких платах, типа ардуинок, esp, stm, когда есть реально ощутимое ограничение на количество вычислений.
И вот ты в какой то момент ловишь себя на том, что на куче листов представляешь необходимые тебе значения в виде нулей и единиц, а вместо делений и умножений пытаешься переписать все действия на битовых сдвигах, кратности двум, переходу к 8-битным целым вместо 16х и 32х или плавающих точек и тому подобное. В этом есть свой шарм и увлеченность, понимаю ребят из ID)
"В наши годы же железо хорошо справляется и со сложными операциями." по этому у нас каждая первая игра лагает.
Не согласен. Тот же DLSS, как и современные реализации рейтрейсинга, и большинства графических наворотов - это попытки упрощения и срезания углов, чтобы меньшими вычислениями добиться крутой картинки.
Автор хорош
Всё. Дайте математикам делать игры и они перевернут эту индустрию с головы на ноги.
Логарифмы простые их я до сих пор помню, а вот с первородными и пределами беда там где фигурная ф в общем
Сравнение по времени не совсем корректное, даже если опустить возможные оптимизации на уровне CPU, скорее всего вычислять корень придется для множества чисел, а значит для вычисления во float можно использовать векторизацию (если переписать код с развернутым циклом умный компилятор gcc со включенной оптимизацией даже сам сможет это сделать), что ускорит выполнение операций еще в ~8 раз. Так что быстрый обратный корень давольно давно потерял свою актуальность, вопрос даже насколько он был актуален в момент написания, т.к. уже тогда появлялись SIMD инструкции (тот же 3dNow! уже имеет PFRSQRT, а вышел аж в 98).
жаль в современность больше программистов не интересует ускорение, потому что не знают математику и считают что она не нужна, но как показывает пример хороший и оптимизированный продукт отличается от современных игр как раз знанием математики разработчиками
Не совсем верно, ускорение почти всегда не интересует потому что за него не платят, а не потому что не знают математику.
я думал кваку вообще на ассемблере написали
Чувак начал ти неплохо. Развивайся, улучшай контент и не теряй свой стиль і вкус. А ми подержим❤
хороший ролик. тока ИМХО формулы и вычисления надо на холсте держать и не скрывать пока не станет ясна суть.
Понравилось! А насколько сложнее код если нужны числа double, а не float?
Спасибо :) На самом деле разница будет только в том, что в формате double из порядка надо вычесть не 127, а 1023 (у double на порядок выделяется 11 бит, а не 8, соответственно там будет не 2^7, а 2^10), а также вместо 2^23 нужно подставить 2^52 (потому что на мантиссу там 52 бита, а не 23). Так что изменится только вот эта сама волшебная константа 0х5f3759df, а остальное будет точно так же всё
а смысл? там точность такая низкая что от замены float на double ничего не поменяется
@@sleirsgoevy Да кто сейчас считает на float? большинство машин 64 битные.Вся встроенная математика С, С++ или С# Math или СMаth ориентированы на операции с double .Более того (по слухам, тут я не уверен) - процессор на самом деле ВСЁ скрытно считает в double, а пользователю под заказ выдает как бы float. А то что точность этого хитрого подхода невелика - ну да, верно. Вопрос - удасться ли сохранить более высокое быстродействие по сравнению с библиотечным double Sqrt(double x)?
@@alexefremov4158 да, с этот способ всё равно быстрее даже с даблом. Другое дело, что дабл обычно используется для повышения точности, а наш способ выдаёт погрешность уже в сотых.
О том, что комп всё считает в даблах вместо флоатов - это не совсем так. Правильнее сказать, что современным компам не важно, с чем работать, с тем или с другим (с точки зрения скорости работы)
@@math-to-masses Вычитал в сети нечто такое: 1) "Intel в FPU всегда используется 80-bit precision, а результат потом просто округляется до нужного." и 2) "На некоторых процессорах double вообще не поддерживается аппаратно." Складывается впечатление, что попытки работать напрямую с битами чисел плавно исчезло за горизонтом. Если когда-то писали на С с ассемблерными вставками, то сейчас в них нет никакой нужды.
Не приведёт ли эта оптимизация к UB? Просто некоторые пользователи сети считают иначе
Формально *(int*)(&x) - можно считать UB для современных стандартов c++. Конкретно на G++ - это не UB. Но может найтись компилятор, который скажет, что это UB
@@math-to-masses да, я про это же. Не логичнее reinterpret_cast? А так - полнейшее нарушение strict aliasing
@@mr.i3298 конечно, на современных машинах лучше reinterpret_cast. Код из видео писался на С, там только такие касты есть. Сейчас игры на С, конечно, уже не пишут - сейчас пишут на плюсах и там уже, конечно, "православно" делают
Говорят создатель продал душу дьяволу за этот алгоритм. А потом кармак нашел его исходники и стырил себе.
Вот они гигачады из id, до которых мне далеко, к сожалению😢
Так-так-так. Видео полезное, но немного истории:
лайфхак, который использовал Кармак, был придуман в 1989 году, одним американским математиком и информатиком, занимавшимся оптимизацией вычислений на ЭВМ. Метод был запатентован им-же. Поэтому при всём моём уважении к Кармаку, метод он подсмотрел на 100%, т.к. уже становился доступен интернет, и научные публикации можно было читать без похода в библиотеку. Поэтому как-то так, для исторической справки.
за 10 лет до квейка? ОгО! Я был готов к тому, что это было придумано за год, ну за два до них, но на десять! Офигеть! Спасибо за информацию :)
Эх... Как же раньше было приятней работать программистом. Придумываешь всякие такие "Простые" гениальные штуки, и радуешься.
Всегда просто смотреть на прошлое с текущими знаниями. Попробуй сейчас что-нибудь придумать и поймешь каково им было.
@@neg0dnick769 да в том то и дело. Чем дальше, тем больше уже придумано. Но это можно испытать порешав задачи из проекта эйлера (допустим там первую задачу решило миллион человек, а есть задача, которую только 50 решили)
действительно интересный ролик, но вот подборка цветовой гаммы меня немного напрягла (например, на моменте 7:05). у меня лично от такого синего цвета начали болеть глаза. так что, пожалуйста, автор выбирайте более приятные для глаза цвета (flat ui цвета, например) тогда смотреть ролики будет куда приятнее. спасибо!
Ролик про олдскул. Именно такие цвета были в средах разработки от Borland. Автор не только рассказал про 99 год, но и визуально вернул туда тех, кто застал. Мне эта отсылка была весьма приятна.
Сделайте людям ещё видео про CORDIC:)
Часть с m e замудреная. Но я не вникал. В целом сам факт что простую линию приблизили к логарифму от 0 до 1 забавляет! Ещё бы историю как они это так сделали, читал что один спросил второго, а второй спросил третьего, а третий ничего не помнит так как был обгашен или пьян.
Элементарно спёрли это у математика, который запатентовал метод: причём метод строился на развитии идей "деления умножением." Поэтому, всё что там заявляют пиарщики id (или сами id) - красивые сказки для лопухов. Типа "тихо сп*здил и ушёл, называется изобрёл)", а как я это это сделал, - да хрен знает, - гашеный был. Отличная отмаза
Может я что-то не так делал, но когда я пробовал данный метод, он оказался на порядок медленнее, чем sqrt из стандартной библиотеки c++. Хз почему, особо вникать не стал
хм ну здорово конечно. Но это все же жесткий костыль ахаха хотя бы дали именование константному значению
Подписался)
Блин, аж слюна потекла, а мозг онемел от осознания своей необразованной тупости.
Жаль что сегодня так не оптимизируют, а то играли бы киберпанк на ультрах в 4к 500 фпс на rtx3050. Утрирую конечно, но ход мысли думаю понятен. Сам я в свободное время разрабатываю движок, и как оказалось, на моем древнем железе пентиум Е6600 и 9800GT можно такие вещи вытворять, что Хуангу не снилось, хотя к сожалению на мать не ставится больше 4 гигов оперативы в двухканале, ддр2 же, че поделаешь.
Покажете?
@@leptosomic Конечно, с превеликим удовольствием! Но он ооочень сырой и обращаться с ним умею только я. Так как я всего лишь один человек, а не команда, от меня не стоит ждать что-то типа Unreal Engine 5. И даже интерфейса нет, еще не сделал. А приходиться делать движок по частям, а именно, графику отдельно, физику отдельно, интерфейс отдельно, остаётся ещё и работа с сетью и ИИ и т. д. И всё это надо потом как-то соединить, а сеть и ИИ я ещё даже не начинал, так как пока что в этом вообще не шарю, думаю, что наверно закажу алгоритм у опытных людей. Да я вообще новичок и нигде не учился, всё что у меня есть, это амбиции и стремление)) А самое главное, меня завораживает этот древний 775-сокет, не могу от него оторваться, я как-будто околдован, я столько раз хотел обновиться на новое железо, но в своё время не смог, всякий раз были проблемы, в том числе и недавние Ковид с майнингом, отношение Хуанга к своим клиентам (имеются в виду геймеры), что окончательно отбили желание к ПК-геймингу. Я купил наконец-то смартфон и начал в них разбираться, ща играю Фри фаер. Но я не отпустил руки, так как очень хочу доказать, что ещё не все соки выжаты из этого паст-ген железа, а разработчики игр забили болт на оптимизацию и поддержку софта на старом железе и тупо перешли на новое следуя маркетингу. То есть ещё можно делать шедевры на старье, по крайней мере я так думаю. Движок ещё не закончен, так как надо заниматься ещё банально и насущным хлебом, работать, так сказать, а кодинг это хобби, точнее один из хобби. Но есть ещё одна проблема на данный момент - я наконец-то продал комп... А 775-х матерей уже трудно найти даже на вторичке, хотя когда-то был момент, что их на помойках и свалках находили, притом в рабочем состоянии, хоть попой жуй, а сейчас их редкие барыги как раритет продают, мягко говоря по завышенной цене)) Но и это не самая главная причина. А главная причина это моё стеснение. Но раз зашли так далеко, так придётся уже сказать. Тсссс, тихо! Если об этом узнают программисты, они пошлют меня оочень далеко, за тридевять земель, это тааакоой трэээш!)) Короче, я пишу... знаете на чём? На Delphi 7! Уфф, прям от груза избавился! Да, это самая ненавистная и тормознутая среда которую терпеть не могут уважающие себя программисты, так как она предназначена для инженеров, а не для этих самых программистов. Но а я плевал на всякие Си плюс плюсы и Джаву, я самым первым ещё в школе научился писать на Паскале и в этот синтаксис влюблён до гроба! И я намерен идти до конца. Оказалось, есть куча вещей, которых надо исправить, например, так как я новичок, я писал всё на integerе))) А это оказывается тупо разбрасывание памятью направо-налево! Ща профессионалы делали бы фейспалм, читая это)) Значит надо использовать байты, а ещё лучше побитовые функции, но тогда придётся углубиться до Ассемблера, а в идеале - знать некоторые машинные коды и чистить мусор в регистрах. Вот уж тогда, думаю 775 точно восстанет из мёртвых!)) Нет, я согласен перейти на нормальный, "человеческий" язык, например Си++ или Си#, но при условии, что синтаксис будет Паскалевским. Вот так вот.
Забыл упомянуть, я остановился на физике, точнее на разрушаемости объектов, хотя есть такие игры, забыл названия, разрушаемость там - Майкрафт курит в сторонке, но у них хромает графика, так как требует больших ресурсов, а например, Батла имеет шикарную графику, но физические разрушения в основном, заскриптованы и обычному игроку незаметны, а дотошные Сталкаши разберут их в пух и прах. То есть приходится выбрать либо вид, либо функционал. А я хочу их объединить их, притом оптимально, чтобы фпс был в пределах разумного. Я много видосов посмотрел про всякие SSAO, MSAA, анизотропную фильтрацию и много других, есть очень классный парень, автор канала Alek OS, еще Onigiri и Вектозавр. Кстати, я буду применять векторную 3Д графику, а текстуры будут использоваться только на стадии разработки игры, а в готовой игре их не будет. А проблема, из-за которой нельзя собрать команду разработчиков такая: я не могу всю мою идею им рассказать как есть, вот очень кстати подошёл бы нейралинк от Илона Маска, я бы свою мысль за считанные секунды передал бы команде)) Вот такие вот дела...
Нашел видео Nemean'а (у которого 3.8 млн просмотров за 2 года) и решил по-быстрому запились контент? Или просто перевод для тех, кто не умеет в английский?
Как будто только в том видео есть объяснение. :)
е = Е - 127, почему именно 127?
об этом говорится в видео, указанном в аннтоациях - про хранение числа с плавающей точкой. Если коротко, то так устроен формат float - мы хотим уметь хранить и положительный порядок, и отрицательный. Всего 8 бит выделяется на порядок. То есть это числа от 0 до 255. Половина должна быть отдана на положительный порядок, а половина - на отрицательный. Поэтому граница проходит по числу 127, как половина от 255
@@math-to-masses Спасибо большое, канал большая находка!
АААААААААААААААААААААААААААААААААААААААААА. Извините.
Отличное видео! Надеюсь, что когда-то в будущем я его пойму.
ua-cam.com/video/p8u_k2LIZyo/v-deo.html - знакомое видео? Нет?
Ничего не понятно, надо разбираться
Ид-софтвер - всегда держали марку - хорошей и качественной оптимизации. Разбор действительно хороший)
(так-же восхищает количество представительниц прекрасного пола в комментариях.. - Не поделитесь статистикой - сколько вообще из них, просмотрели ролик в % соотношение...(я не сексист Т_Т))
1% зрителей этого видео - девушки. А всего на канале 2% зрителей - девушек :)
Возможно, ютуб меня рекомендует только суровым мужикам :)
@@math-to-masses Достойно :)) Настоящее сообщество гик-задр...тов.....:))
Какой же я тупой... T___T
Оптимизация кода 80 уровня
Контент по квейку 3 и программирование. Это что сказка?