Действительно ли возможно прокрутить значительно более быструю версию sqrt
В приложении я являюсь профильным, я нашел, что в некоторых сценариях эта функция может принять 10% общего времени выполнения.
Я видел обсуждение за эти годы быстрее sqrt реализации с помощью подлого обмана с плавающей точкой, но я не знаю, устарели ли такие вещи на современных центральных процессорах.
MSVC ++ компилятор 2008 года используется для ссылки..., хотя я предположил бы, что sqrt не собирается добавлять много служебное все же.
См. также здесь для подобного обсуждения функции modf.
Править: для ссылки это - один широко используемый метод, но это на самом деле намного более быстро? Сколько циклов SQRT так или иначе в эти дни?
4 ответа
Да, это возможно даже без обмана:
1) жертва точность для скорости: алгоритм sqrt является итеративным, повторно реализуйте с меньшим количеством итераций.
2) таблицы поиска: либо только для начальной точки итерации, либо в сочетании с интерполяцией, чтобы добраться до нее.
3) кеширование: всегда ли вы вводите один и тот же ограниченный набор значений? в таком случае кеширование может работать нормально. Я нашел это полезным в графических приложениях, где одно и то же вычисляется для множества фигур одинакового размера, поэтому результаты можно удобно кэшировать.
Скорее всего, вы получите больше улучшений скорости, изменив свои алгоритмы , чем изменив их реализации : Попробуйте позвонить sqrt () меньше вместо того, чтобы делать вызовы быстрее. (И если вы думаете, что это невозможно - улучшения для sqrt () , о которых вы упомянули, являются всего лишь улучшениями алгоритма , используемого для вычисления квадратного корня.)
Поскольку он используется очень часто, вполне вероятно, что реализация sqrt () в вашей стандартной библиотеке почти оптимальна для общего случая. Если у вас нет ограниченного домена (например, если вам нужна меньшая точность), где алгоритм может использовать некоторые сокращения, очень маловероятно, что кто-то придумает более быструю реализацию.
Обратите внимание: поскольку эта функция использует 10% времени выполнения, даже если вам удастся придумать реализацию, которая занимает только 75% времени std :: sqrt () , эта по-прежнему сокращает время выполнения только на 2,5% . Для большинства приложений пользователи даже не заметят этого, за исключением случаев, когда они используют часы для измерения.
Вот отличная сравнительная таблица: http://assemblyrequired.crashworks.org/timing-square-root/
Короче говоря, SSE2 ssqrts примерно в 2 раза быстрее, чем FPU fsqrt , а приближение + итерация примерно в 4 раза быстрее, чем это (в 8 раз в целом).
Кроме того, если вы пытаетесь использовать sqrt с одинарной точностью, убедитесь, что это действительно то, что вы получаете. Я слышал, по крайней мере, об одном компиляторе, который преобразовывал бы аргумент float в double, вызывал бы sqrt двойной точности, а затем конвертировал бы обратно в float.
Насколько точным должен быть ваш sqrt ? Вы можете очень быстро получить разумные приближения: см. Превосходную функцию обратного квадратного корня в Quake3 для вдохновения (обратите внимание, что код под лицензией GPL, поэтому вы можете не захотеть интегрировать его напрямую).