Я разрабатываю игру, которая вызывает так много математических функций для физики и рендеринга. "Быстрый обратный sqrt" , используемый в Quake3, как известно, быстрее, чем sqrt(), и его фон красив.
Знаете ли вы какой-либо другой алгоритм, который быстрее обычного с приемлемой потерей точности?
Эти алгоритмы называются "алгоритмами аппроксимации" в литературе. Стандартная книга с большим количеством примеров Аппликационные алгоритмы Виджая В. Вазирани.
Случай sin x ~~ x является частным случаем чего-то чуть более общего: посмотрите на серия Тейлора (или ряд Фурье в случае периодических функций) вашей функции и вычислять только первые несколько членов.
Другая (несколько жестокая) техника состоит в том, чтобы случайно собрать несколько точек вашей функции, а затем запустить линейную регрессию против нее. Таким образом, вы также можете получить хороший полином, описывающий вашу функцию:).
Любая непрерывная функция (включающая наиболее распространенные математические операции) может быть хорошо аппроксимирована на ограниченный интервал полиномом. Это вместе с относительно простыми тождествами, которые обычно удовлетворяют обычным математическим функциям (например, законам сложения) и табличным поиском, составляет основу стандартных методов построения алгоритмов быстрой аппроксимации (а также основы методов высокой точности, подобных тем, которые используются в системной математике библиотека).
Серия Тейлора обычно является плохим выбором; Многочлены Чебышева или Минимакса имеют гораздо лучшие характеристики ошибок для большинства вычислительных целей. Стандартный метод установки минимаксных полиномов заключается в использовании алгоритма Ремеса, который реализован во множестве коммерческих программ математики, или вы можете выполнять собственную реализацию с помощью дневной работы, если знаете, что делаете.
Для записи следует избегать "быстрого обратного квадратного корня" на современных процессорах, так как значительно быстрее использовать инструкцию оценки квадратного корня с плавающей запятой (rsqrtss/rsqrtps на SSE, vrsqrte на NEON, vrsqrtefp на AltiVec). Даже (не приблизительный) аппаратный квадратный корень довольно быстр на современных процессорах Intel.
при малых x: sin (x) ~ = x - это тот, который часто используется в физике
В Niko есть несколько хороших предложений, к которым я бы добавил старую таблицу поиска.
Я использовал таблицу поиска для циклических функций (sin/cos/tan) успешно многократно в режиме симуляции в режиме реального времени. Sqrt() сложнее, но если ваш входной диапазон ограничен (скажем, пиксели экрана), его трудно бить за скорость, и вы точно можете точно настроить объем/точность. Вы также можете использовать поиск для общего диапазона, а затем иметь выпадение для функции sqrt() для фреймворка для редкого случая.
Пол
Из исходного кода Doom для приблизительного расстояния между двумя точками 2D без необходимости использования sqrt() или тригонометрических функций:
fixed_t P_AproxDistance(fixed_t dx, fixed_t dy )
{
dx = abs(dx);
dy = abs(dy);
if (dx < dy)
return dx+dy-(dx>>1);
else
return dx+dy-(dy>>1);
}
Обратите внимание, что x >> 1 совпадает с x / 2, но немного быстрее - хорошие современные компиляторы делают это автоматически в наши дни, но тогда они были не такими уж большими.
Что-нибудь вероятностное обычно такое. Запуск моделирования 10 раз будет быстрее, но даст менее точные результаты, чем запуск моделирования 1000 раз.