Оценка квадратного корня

Question

Я пишу приложение для iPhone, которое должно вычислять квадратный корень из числа примерно 2000 раз каждые 1/30 секунды. sqrt () отлично работает на компьютере, но частота кадров на iPhone или iPad падает примерно до 10 кадров в секунду, и я уже оптимизировал остальную часть кода. Я слышал, что это может быть значительно ускорено путем оценки квадратного корня, но я не могу найти какой-либо код для этого. Мне нужно только одно или два десятичных знака точности. Буду признателен за любые предложения о том, как это сделать, или другие способы ускорить процесс.

Спасибо!

Answer 1

Если вам на самом деле не нужен квадратный корень, сравните квадратные значения, а не необработанные значения и квадратный корень.

Квадрат гораздо быстрее (и точнее), чем брать квадратroot, если вам нужны только сравнения.Так большинство игр делают это.

Answer 2

Знаете ли вы диапазон значений, для которого вы пытаетесь найти квадратный корень?Допустим, у вас есть значения в диапазоне от 0 до 10. Затем вы можете предварительно рассчитать массив:

sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10

Затем во время выполнения вы берете число, для которого вы хотите получить sqrt, преобразуете его в целое число (например, 3.123становится 3) и используется как индекс (3) для поиска предварительно рассчитанного значения.

Конечно, если вы хотите более точное разрешение, вы можете просто увеличить количество элементов в вашем массиве.

Answer 3

Прежде всего, вы уверены, что квадратный корень на самом деле является узким местом?Вы профилировали?2000 квадратных корней каждые 1/30 секунды на самом деле не так много, даже на мобильном телефоне.Документация ARM цитирует 33 цикла для квадратного корня с одинарной точностью и 60 циклов для двойной точности;процессор с тактовой частотой 600 МГц может выдавать 10 миллионов квадратных корней в секунду (больше, если инструкция вообще конвейерна).

Если у вас есть профилирование, а квадратный корень действительно является узким местом, вам нужноиспользовать инструкцию NEON vrsqrte.f32.Эта инструкция довольно быстрая и дает вам приблизительные квадратные корни из четырех чисел с плавающей точкой одновременно.Затем вы можете использовать инструкцию vmul.f32, чтобы получить приблизительные квадратные корни (хотя для многих применений обратный корень более полезен, чем сам квадратный корень).

Answer 4

Если вам нужен квадратный корень для вычисления треугольника Пифагора (sqrt (x * x + y * y)), а оба x и y неотрицательны, то очень быстрое приближение к этому равно

max(x,y) + min(x,y)*0.333

Это имеет максимальную ошибку 5,7%.Остерегайтесь ошибочного прогнозирования веток в min () и max ().

Answer 5

Самое простое изменение, которое вы можете сделать на iPhone, - это использовать sqrtf () вместо sqrt ().Матрица с плавающей запятой одинарной точности намного быстрее, чем двойная, особенно на устройствах третьего поколения и старше.

Answer 6

Насколько точной должна быть ваша оценка? Если вы знаете, насколько близко вы хотите, чтобы ваша оценка была к реальной площади, метод Ньютона - ваш друг.

Знаете ли вы диапазон значений, передаваемых в sqrt? Если это так, вы можете составить справочную таблицу, которая предварительно вычисляется при запуске (или даже считывается с диска при запуске в зависимости от того, что оказывается быстрее). Найдите в таблице самый близкий к вам вход, и вы получите свою оценку.

Answer 7

Может быть, это для вас: Быстрый обратный квадратный корень Если этот метод не обеспечивает необходимой точности, есть также много других итерационных методов, где вы можете выбрать более или менее точный между скоростью и точностью: Методы вычисления квадратных корней

Answer 8

Если у вас есть «нормальное» положительное число с плавающей запятой или двойное число, а не int, и вы хотите использовать метод поиска в таблице, вы можете выполнить два отдельных просмотра таблицы, один для показателя степени (смещенный) иодин для нескольких битов мантиссы (сдвиг и извлечение битового поля маски), а затем умножить две таблицы для поиска результатов вместе.

Answer 9

Быстрый поиск в Google включает все виды ссылок.

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Approximations_that_depend_on_IEEE_representation

http://www.azillionmonkeys.com/qed/sqroot.html