Более быстрая точность принесения в жертву математического алгоритма
6 ответов
Эти алгоритмы в литературе называются «алгоритмами аппроксимации». Стандартная книга с множеством примеров - это Аппроксимационные алгоритмы Виджая В. Вазирани .
Случай sin x ~~ x является частным случаем чего-то более общего: посмотрите на Taylor ряд (или ряд Фурье в случае периодических функций) вашей функции и вычислить только несколько первых членов.
Другой (несколько жестокий) метод - это случайным образом собрать несколько точек вашей функции и затем выполнить линейную регрессию против них. Таким образом, вы также можете получить хороший многочлен, описывающий вашу функцию :).
для малых x: sin (x) ~ = x часто используется в физике
У Нико есть несколько хороших предложений, к которым я бы добавил старомодную справочную таблицу.
Я много раз успешно использовал справочную таблицу для круговых функций (sin / cos / tan) в высокопроизводительной системе реального времени. Sqrt () сложнее, но если ваш диапазон ввода ограничен (например, пиксели экрана), его трудно превзойти по скорости, и вы можете точно настроить компромисс между пространством / точностью. Вы также можете использовать поиск для общего диапазона, а затем использовать функцию sqrt () фреймворка для редкого случая.
Paul
Все вероятностные обычно выглядят так. Выполнение моделирования в 10 раз будет быстрее, но даст менее точные результаты, чем выполнение моделирования в 1000 раз.
Любая непрерывная функция (которая включает в себя наиболее распространенные математические операции) может быть хорошо аппроксимирована на ограниченном интервале полиномом. Это, вместе с относительно простыми тождествами, которым обычно удовлетворяют обычные математические функции (например, законы сложения) и поиском в таблицах, обеспечивает основу стандартных методов построения алгоритмов быстрого приближения (а также основу методов высокой точности, подобных тем, которые используются в системной математике). библиотека).
Однако серии Тейлора обычно плохой выбор; Полиномы Чебышева или Минимакс имеют гораздо лучшие характеристики ошибок для большинства вычислительных применений. Стандартный метод подбора минимаксных полиномов заключается в использовании алгоритма Ремеса, который реализован во многих коммерческих математических программах, или вы можете свернуть свою собственную реализацию с дневной работой, если знаете, что вы
Для справки, на современных процессорах следует избегать «быстрого обратного квадратного корня», поскольку гораздо быстрее использовать команду вычисления обратного квадратного корня с плавающей запятой ( rsqrtss / rsqrtps на SSE, vrsqrte на NEON, vrsqrtefp на AltiVec). Даже (не приблизительный) аппаратный квадратный корень довольно быстрый на современных процессорах Intel.
Из исходного кода Doom для приблизительного расстояния между двумя двухмерными точками без использования 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 , но немного быстрее - современные современные компиляторы делают это автоматически, но тогда они были не так хороши.