Войти
ПрограммированиеФорумОбщее

Быстрые и точные тригонометрические функции (2 стр)

Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5 6 Следующая »
#15
20:46, 24 мар. 2009

Zefick

Согласен. Есть такой алгоритм.
http://algolist.manual.ru/maths/count_fast/sincos.php

Но я не думаю, что он достаточно быстр, даже по сравнению со стандартными функциями.
Ведь вам всего лишь надо вычислить целу часть градусов угла. :)

Этот ряд не есть чистая апрокксимация. Есть несколько методов апроккимации (полиномиальная, рациональная и др.)
В основе этого ряда лежит рациональная на основе полиномов Чебушева + регрессия. Я всего лишь сложил все в кучу и просчитал полином с наименьшим внесением погрешности.

>Ээээ.... Не ну ты всё-таки соберись да проверь свой велосипед на точньсть/быстродействие со стандартным sin/cos от FPU.
А так понятно что непонятно если и велика производительность/точность твоего кода - то насколько?
Ответь на этот вопрос - тогда и будет ясно стоит ли овчинка выделки.

Естественно я проверял и тестировал со стандартными функциями и еще с несколькими другими алгоритмами. На Core2 Duo трудно конечно получить точные значения. Но при всех эксперементах COS0(полином 26 степени) выполнялся с от ~0.1218 мс  , стандартный ~0.15 мс. А погрешость не превысила +-1.3*10^-14. Интерации делал от 0 до 2PI c шагом 1.0*10^-5.

Вот примерный код.

  ::SetProcessAffinityMask(::GetCurrentProcess(), 1);
  ::SetPriorityClass(::GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
  ::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
  for (F64 a=0; a<=_dTwoPI; a+=1.0e-5)
  {
    Reset();
    m_c=COS0(a);
    m_tc=CTIMER::GetDeltaTime();
    Reset();
    m_fc=COS(a);
    m_tfc=CTIMER::GetDeltaTime();
    m_epsc=ABS(m_c-m_fc);
}

Вы сами попробуйте.  Мне очень интересно, какие вы получите результаты.
Да есть книга "3D Game Engine Architecture Engineering Real-Time Applications with Wild Magic David H. Eberly"
Там как раз используются быстрые функции.

http://www.gamedev.ru/download/?id=8647
http://www.gamedev.ru/download/?id=8648


#16
21:09, 24 мар. 2009

Предварительно расчитанный полином COS степени 12
0.9998990005099806- 0.49974184489072426 x^2 +
0.04155259288504809 x^4 - 0.0013708002084648239 x^6 +
0.000023433503025436393 x^8 - 2.212769358520237*10^-7 x^10 +
9.533857784766455*10^-10 x^12

http://www.gamedev.ru/images/?id=40452
На рис. показана сходимость полиномов из которых состоит данных полигон (пунктирные линии). Сходимость полинома показана красной сплошной линией.
Теоритеическая прогрешность не более ~0.0002

#17
21:56, 24 мар. 2009

asvp
>Согласен. Есть такой алгоритм.
>http://algolist.manual.ru/maths/count_fast/sincos.php
>Но я не думаю, что он достаточно быстр, даже по сравнению со стандартными функциями.
  А я лично думаю, что это и есть стандартная функция.

>Предварительно расчитанный полином COS степени 12
>0.9998990005099806- 0.49974184489072426 x^2 +
> 0.04155259288504809 x^4 - 0.0013708002084648239 x^6 +
> 0.000023433503025436393 x^8 - 2.212769358520237*10^-7 x^10 +
> 9.533857784766455*10^-10 x^12
  Надо бы округлить коэффициенты, ведь уже же ясно, какие они должны быть. Например, даже если внимательно на них посмотреть, то 0.9998990005099806 подозрительно смахивает на 1.0, а 0.49974184489072426 - на 0,5.

>  for (F64 a=0; a<=_dTwoPI; a+=1.0e-5){
>    Reset();
>    m_c=COS0(a);
>    m_tc=CTIMER::GetDeltaTime();
>    Reset();
>    m_fc=COS(a);
>    m_tfc=CTIMER::GetDeltaTime();
>    m_epsc=ABS(m_c-m_fc);
>}
  А не точнее ли будет сначала засечь время один раз, потом посчитать все, а потом засечь второй раз? Надо же думать. Так на каждом прогоне цикла накапливается ошибка синхронизации таймера. Не понимаю, как на таком коде вообще были получены результаты с точностью до 0,1 мс. Вообще надо прогнать этот цикл как можно большее количество раз, чтобы в итоге получилось время порядка нескольких секунд. Тогда колебания загруженности процессора будут меньше влиять на рузульта. А так "не верю!"

  А у стандартного, надо думать точность куда больше четырнадцати разрядов (для double). Она вообще максимальная при выбранном типе результата. Правда ирония судьбы в том, что это никак не проверить.

#18
22:26, 24 мар. 2009

asvp

> Вы сами попробуйте. Мне очень интересно, какие вы получите результаты.

Ну так выложи законченный код из 100 строк на тестирование того и иного. А то непонятно, реально, как ты умудрился быстродействие пары десятков инструкций замерить через вызов CTIMER::...., где еще пара десятков инструций, причём полюбасу с уходом в недра ОС API. Zefick всё правильно говорит. Такому тесту пока верить рано.
Да даже если и верить - десяток процентов улучшения с потерей точности и приличным cash-miss-заделом - далеко не айс...

#19
22:28, 24 мар. 2009

asvp
>Этот ряд основан на "Экономичной рациональной аппроксимации + регрессия"
А это разве точнее чем многочлены Чебышева? ^_^

#20
22:53, 24 мар. 2009

id-alex
>А это разве точнее чем многочлены Чебышева? ^_^
Многочлены чебышева и лежандра, насколько я помню, аппроксимируют функцию многочленом наименьшей возможной степени при условии, что она проходит через заданный набор точек. Многочлен - частичная сумма ряда тейлора задаёт многочлен наименьшей степени, частные производные которого совпадают с частными производными исходной функции. Ума не приложу, с чего автор взял, что многочлен тейлора будет аппроксимировать функцию хуже с тем же порядком аппроксимирующего многочлена. По какой норме во-первых?, начнём с этого.

#21
0:26, 25 мар. 2009

Suslik
Мое видение ситуации состоит в том, что интерполяция по узлам многочлена Чебышева минимизирует inf-норму погрешности приближения n-непрерывно-дифференцируемых функций в классе многочленов n-ой степени. Ряд тейлора n-ой степени - это тоже многочлен n-ой степени, с одним чрезвычайно кратным узлом, поэтому точнее чем многочлен Лагранжа, вычисленный по узлам многочлена Чебышева, он интерполировать в этом же классе функций не может.

Однако, ниоткуда не следует, что узлы многочлена Чебышева лучше всех других узлов в условиях когда интерполируемая функция зафиксирована.

#22
0:36, 25 мар. 2009

Suslik
>Ума не приложу, с чего автор взял, что многочлен тейлора будет аппроксимировать функцию хуже с тем же порядком аппроксимирующего многочлена.
Вооружившись калькулятором и числами из поста #16, я заметил, что 1 / 0.0013708002084648239 = 729.50091036 что не равно 6! (причем ошибка аж в третьем знаке). Поэтому приведенная формула не является формулой Тейлора. Скособоченность графика погрешности заставляет меня думать, что это и не многочлен Чебышева тоже. Так что же это - подумал я - и написал провокационный пост #19.

Я тут еще немного подумал и понял, что многочлен Чебышева 12-ой степени позволяет персонально для косинуса получить точность не меньше чем 1 / ( 2^11 * 11! ) = что без учета погрешности вещественной арифметики составляет 1.22e-11. Предлагаемые автором ~0.0002 на фоне достижений Пафнутия Львовича требуют пояснений.

#23
2:04, 25 мар. 2009

id-alex
>минимизирует inf-норму погрешности приближения n-непрерывно-дифференцируемых функций в классе многочленов n-ой степени
ок, норму ввели.

на википедии для чистоты спора лезть не хочу, поэтому честно признаюсь, что не помню, какой из многочленов наиболее оптимально аппроксимирует в норме по супремуму.

>Вооружившись калькулятором и числами из поста #16, я заметил, что 1 / 0.0013708002084648239 = 729.50091036 что не равно 6!
то, что коэффициент близок к коэфф. тейлора, но им не является, очевидно

>1.22e-11
стандартная двойная точность при вычеслении double-величин. автор уверяет, что его многочлен заруливает по точности любой стандартный метод но, извольте, sinh считает с точностью порядка точности представления числа, так что вот не пофиг на точность?

по производительности:
автор привёл два асм-листинга: своей уберфункции и интелкомпайлеровский sincos, тыча пальцем "вот видите??7" - интересно, что он хотел этим сказать? то, что в intel-листинге в четыре раза больше инструкций не значит ровным счётом ничего, "на глаз" оценить эффективности таких нетривиальных операций, которые выполняет ICL, практически невозможно. Единственный верный способ - собственно, проверить

>на фоне достижений Пафнутия Львовича
а вот кто-то без педивикии не обошёлся :)


мой скромный контрибьюшн:
http://www.everfall.com/paste/id.php?sv75oq5a1rtt

результаты в миллисекундах на Core2Duo E6600 2х2.4GHz:

ubertime: 125 //уберфункция топикстартера. никто не знает, что она делает, но она делает это вот так.
taylorTime: 47 //моя идиотская влобная реализация ряда маклорена.
classicDoubleTime: 157 //обычный дабл-косинус
classicFloatTime: 125 //обычный флот-синус

замечаем:
уберфункция работает по времени примерно как обыкновенный флот-синус, который, в отличии от уберфункции, определён везде и способен "спариваться" с подсчётом ещё одного косинуса, то есть на практике время делим пополам.

быдлоряд тейлора выполняется быстрее при той же точности. к чему бы это?

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

компилятор MSVS зафейлил буквально всё, на нём стандартные синусы-косинусы считались достаточно долго(в три раза дольше), так что пользовался православным ICL на max optimization.

вывод:
если Вам нужна функция, которая считает косинус на отрезке -pi..pi и вам очень сильно важны эти десять процентов производительности, вы можете убить мозг всех своих программистов-напарников разом, вставив в код эту божественную формулу. потом останется только молиться, что следующая версия компилятора не додумается до ещё более хитрых оптимизаций и Вам не придётся вырезать всю эту муть, заменяя стандартным косинусом без ограничений, который будет впридачу быстрее.

#24
2:21, 25 мар. 2009

Suslik
В MSVC стандарный sin/cos - интринсик, т.е. на место вызова посдтавляется fsincos [+fstp] в релизе.
Проверь ещё раз, функция должна заменяться одной инструкцией.

#25
2:22, 25 мар. 2009

Nomad
MSVC нервно курит в сторонке, intel его в любом случае заруливает, часто даже на атлоне.

#26
2:39, 25 мар. 2009

Suslik
Я просто сомневаюсь в таком случае, что ф-ия синуса в IC превращается в стопицот строк, если даже студия копилит её в одну иснтрукцию.
Кто-то лжёт в этом треде.

#27
2:46, 25 мар. 2009
;;;   for(float i = -3.1415926f; i < 3.1415926f; i += 1e-6f)

        movss     xmm2, DWORD PTR _2il0floatpacket$28           ;76.50
$LN59:
        movss     xmm3, DWORD PTR _2il0floatpacket$29           ;76.33
        pxor      xmm0, xmm0                                    ;
        movss     DWORD PTR [esp+72], xmm0                      ;
                                ; LOE ebx esi edi xmm1 xmm2 xmm3
$B1$17:                         ; Preds $B1$35 $B1$16
$LN61:

;;;   {
;;;     val4 += cosf(i);

        movss     DWORD PTR [esp+68], xmm1                      ;78.11
        movaps    xmm0, xmm1                                    ;78.11
        call      ___libm_sse2_cosf                             ;78.11
                                ; LOE ebx esi edi xmm0
$B1$35:                         ; Preds $B1$17
        movss     xmm1, DWORD PTR [esp+68]                      ;
$LN63:
        movss     xmm2, DWORD PTR [esp+72]                      ;78.3
$LN65:
        addss     xmm1, DWORD PTR _2il0floatpacket$28           ;76.45
$LN67:
        addss     xmm2, xmm0                                    ;78.3
$LN69:
        movss     xmm3, DWORD PTR _2il0floatpacket$29           ;76.33
        comiss    xmm3, xmm1                                    ;76.33
$LN71:
        movss     DWORD PTR [esp+72], xmm2                      ;78.3
$LN73:
        ja        $B1$17        ; Prob 82%                      ;76.33
                                ; LOE ebx esi edi xmm1
$B1$18:                         ; Preds $B1$35
$LN75:

;;;   }
за что купил - за то продаю. видимо, все прыжки - чтобы спарить четыре вызова cos32 в один SSE2 cos128.
#28
6:48, 25 мар. 2009

Фтопку Тейлора! При равном количестве членов ряды Чебышева дают на два порядка высокую точность!
Кроме у предложенных здесь реализаций функции sin и cos будет сильное падение точности для углов больших по модулю чем PI/4.
p.s.
Оптимизированная реализация функции sincos4, вычисляющая одновременно sin и сos для 4-х произвольных
углов (!), на sse с рядами Чебышева и с точностью не хуже 10^-6 (на  диапазоне от -2PI до 2PI) занимает
всего 120 тактов и 57 SSE инструкций.

#29
8:28, 25 мар. 2009

G++ стабильно вызывает call sin, даже при -O3 и прочих ключах SSE-оптимизации.

Страницы: 1 2 3 4 5 6 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.