Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Быстрое вычисление угла.

Return0 Профи (678), на голосовании 10 лет назад
Есть точки A[x;y] и B[x;y]. Нужно максимально быстро вычислить угол между прямой AB и осью координат X (или Y - не существенно) . Арктангенс получается у меня слишком медленным в программе, ведь считать нужно от 25 миллионов и более точек в секунду.
Голосование за лучший ответ
Алексей Иванов Ученик (110) 10 лет назад
Вряд ли что-то быстрее арктангенса получится.
Хотя можно попробовать:
1) для маленьких тангенсов - угол приблизительно равен самому тангенсу и не надо считать арктангенс
2) для больших тангенсов - угол приблизительно равен пи/2 минус обратное значение тангенса. Опять же не надо считать арктангенс
3) При тангенсах порядка 1 - разложить в ряд Тейлора около пи/4

Или ещё есть вариант:
сделать таблицу значений : тангенс - угол, и потом линейная интерполяция соседних значений
Return0Профи (678) 10 лет назад
Таблица - долго...значения углов нужно находить не от 0 до 360, а от 0 до 65536. Поиск в таблице из 65536 элементов - долговато.
Я вот тут формулу вывел...основываясь на равенстве соотношений сторон и углов...По идее всё верно, или я ошибся?

Угол=16384/(x+y)*y

Это формула для x>=0 и y>=0. 16384 - это угол в 90 градусов (65536/4). Я чего-то напутал? Или эта формула медленнее арктангенса будет?
Табличный способ вычисления арктангенса является самым быстрым. "Поиск в таблице" - это не табличный метод, а вообще не понятно что!
К.Ученик (245) 2 года назад
Про ряд Тейлора для аппроксимации функций лучше забыть. Одни из наиболее эффективных методов – это разложение функции в ряд Чебышёва и связанный с ним метод Паде–Чебышёва, позволяющий получать дробно-рациональные аппроксимации. Мои исследования показывают, что для арктангенса второй из перечисленных методов дает лучшие результаты, для него я и написал программу.

Что касается таблиц, то это тоже достаточно эффективный путь, но он не настолько хорош, как может показаться. Дело в том, что в современных компьютерах подсистема памяти является узким местом, и это ощущается при произвольной выборке из больших массивов данных.
К. Ученик (245) 2 года назад
// Самый быстрый код для арктангенса. Написано на Visual Studio. Быстрее без снижения точности не сделать.

_declspec(naked) float _vectorcall arctg(float x)
{
_declspec(align(16)) static const float ct[12] = // Таблица констант
{
1.57079633f, // pi/2
-1.57079633f, // -pi/2
1.0f, // 1
4.27012574E15f, // Значение x^2, начиная с которого arctg(x)=pi/2*sgn(x)
4.25772129E-17f, // a0
4.25772129E-17f, // a0
1.25756221E-17f, // a0*a2
2.50182221E-17f, // a0*c2
4.86816191E-17f, // a0*a1
6.28740230E-17f, // a0*c1
4.02179951E-19f, // a0*a3
2.24874637E-18f // a0*c3
};
_asm
{
vmovmskps eax,xmm0 // Считать в младший бит eax знаковый бит числа x
vshufps xmm1,xmm0,xmm0,0 // xmm1 = x # x : x # x
mov edx,offset ct // В edx - адрес таблицы констант
and al,1 // eax = 1, если x<0, иначе eax = 0
vmulps xmm2,xmm1,xmm1 // xmm2 = x^2 # x^2 : x^2 # x^2
vmovss xmm0,[edx+4*eax] // xmm0 = pi/2*sgn(x)
vcomiss xmm2,[edx+12] // Сравнить y=x^2 и пороговое значение
jae arctg_exit // Результат готов, если y не ниже порогового значения
vmovaps xmm4,[edx+16] // xmm4 = a0*c2 # a0*a2 : a0 # a0
vmovaps xmm3,[edx+32] // xmm3 = a0*c3 # a0*a3 : a0*c1 # a0*a1
vmulps xmm5,xmm2,xmm2 // xmm5 = y^2 # y^2 : y^2 # y^2
vcomiss xmm2,[edx+8] // Сравнить y с 1, выставить флаги согласно результату
ja arctg_big // Перейти, если |x|>1
vfmadd213ps xmm3,xmm2,xmm4 // xmm3 ~ c3*y+c2 # a3*y+a2 : c1*y+1 # a1*y+1
vmovhlps xmm4,xmm4,xmm3 // xmm4 ~ c3*y+c2 # a3*y+a2
vfmadd213ps xmm4,xmm5,xmm3 // xmm4 ~ c3*y^3+c2*y^2+c1*y+1 # a3*y^3+a2*y^2+a1*y+1
vmovshdup xmm2,xmm4 // xmm4 = P; xmm2 = Q
vdivss xmm4,xmm4,xmm2 // xmm0 = P/Q
vmulss xmm0,xmm4,xmm1 // xmm0 = x*P/Q
ret // Вернуться
arctg_big: // При |x|>1 используем формулу pi/2*sgn(x)-arctg(1/x)
vfmadd213ps xmm4,xmm2,xmm3 // xmm4 ~ c2*y+c3 # a2*y+a3 : y+c1 # y+a1
vmovhlps xmm3,xmm3,xmm4 // xmm3 ~ c2*y+c3 # a2*y+a3
vfmadd213ps xmm4,xmm5,xmm3 // xmm4 ~ y^3+c1*y^2+c2*y+c3 # y^3+a1*y^2+a2*y+a3
vmovshdup xmm2,xmm4 // xmm4 = P; xmm2 = Q
vmulss xmm2,xmm2,xmm1 // xmm2 = x*Q
vfmsub231ss xmm4,xmm2,xmm0 // xmm4 = pi/2*|x|*Q-P
vdivss xmm0,xmm4,xmm2 // xmm0 = pi/2*sgn(x)-P/(x*Q)
arctg_exit: // Результат в xmm0 готов
ret // Вернуться
}
}
Похожие вопросы