죄와 코스를 함께 계산하는 가장 빠른 방법은 무엇일까?
값의 사인(Sine)과 코사인(Co-Sine)을 함께 계산(예: 회전 행렬 생성)하고 싶다.물론 나는 그것들을 차례로 이렇게 따로따로 계산할 수 있었다.a = cos(x); b = sin(x);그러나 나는 두 가지 가치관을 모두 필요로 할 때 더 빠른 방법이 있는지 궁금하다.
편집: 지금까지의 답변을 요약하려면:
블라드가 말하길, asm 명령이 있다.
FSINCOS두 가지 모두 계산(호출과 거의 동시에)FSIN혼자)기를가 알아차린 것처럼, 이러한 최적화는 컴파일러에 의해 이미 수행되는 경우도 있다(최적화 플래그를 사용할 때).
카페에서 지적한 기능
sincos그리고sincosf아마도 이용가능하며, 다음을 포함하는 것만으로 직접 호출될 수 있다.math.h조사표를 사용하는 타나시우스 접근법은 논란의 여지가 있다.(그러나 내 컴퓨터와 벤치마크 시나리오에서는 보다 3배 더 빨리 실행된다.
sincos32비트 부동 소수점에 대해 거의 동일한 정확도로).조엘 굿윈은 상당히 높은 정확도를 가진 초고속 근사 기법의 흥미로운 접근법에 연결했다. (나에게는 테이블 검색보다 훨씬 빠르다.)
현대의 x86 프로세서는 fsincos 명령어를 가지고 있는데, 이것은 당신이 원하는 것을 정확히 할 것이다 - 죄와 cos를 동시에 계산하는 것이다.최적화를 잘 하는 컴파일러는 동일한 값에 대해 죄와 코스를 계산하는 코드를 검출하고 fsincs 명령을 사용하여 이를 실행해야 한다.
이것을 작동시키려면 컴파일러 깃발을 약간 돌려야 했지만, 다음과 같다.
$ gcc --version
i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5488)
Copyright (C) 2005 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ cat main.c
#include <math.h>
struct Sin_cos {double sin; double cos;};
struct Sin_cos fsincos(double val) {
struct Sin_cos r;
r.sin = sin(val);
r.cos = cos(val);
return r;
}
$ gcc -c -S -O3 -ffast-math -mfpmath=387 main.c -o main.s
$ cat main.s
.text
.align 4,0x90
.globl _fsincos
_fsincos:
pushl %ebp
movl %esp, %ebp
fldl 12(%ebp)
fsincos
movl 8(%ebp), %eax
fstpl 8(%eax)
fstpl (%eax)
leave
ret $4
.subsections_via_symbols
타다, 이건 핀소스 명령을 사용한다고!
AMD FSINCOS사인 함수와 코사인 함수를 동시에 계산하는 경우.강력한 최적화가 필요하다면, 아마도 그것을 사용해야 할 것이다.
여기 작은 예가 있다: http://home.broadpark.no/~alein/fsincos.properties
다음 다른 예(MSVC의 경우): http://www.codeguru.com/forum/showthread.php?t=328669
여기 또 다른 예가 있다(gcc 포함): http://www.allegro.cc/forums/thread/588470
그들 중 한 명이 도움이 되길 바라. (내가 직접 이 지시를 사용한 것은 아니야, 미안해.)
프로세서 수준에서 지원되기 때문에 테이블 룩업보다 훨씬 빠를 것으로 예상한다.
편집:
위키피디아는 다음과 같이 제안한다.FSINCOS387개의 프로세서에 추가되어서 당신은 그것을 지원하지 않는 프로세서를 거의 찾을 수 없다.
편집:
인텔의 문서에는 다음과 같이 명시되어 있다.FSINCOS.FDIV(즉, 부동 소수점 분할).
편집:
일부 최신 컴파일러가 Sine 및 Cosine의 계산을 호출로 최적화하는 것은 아니라는 점에 유의하십시오.FSINCOS내 하지 특히 내 VS 2008은 그런 식으로 하지 않았다.
편집:
첫 번째 예시 링크는 죽었지만 웨이백 머신에는 아직 버전이 있다.
상업용 제품을 사용할 의향이 있고 동시에 다수의 sin/cos 계산을 하고 있다면(그래서 벡터링된 함수를 사용할 수 있다) 인텔의 수학 커널 라이브러리를 확인해 보아야 한다.
그것은 사악한 기능을 가지고 있다.
그 문서에 따르면, 그것은 높은 정확도 모드의 코어 2 듀오에서 평균 13.08 클럭/소자를 나타내며, 나는 이것이 핀소스보다 더 빠를 것이라고 생각한다.
GNU C 라이브러리를 사용하는 경우 다음 작업을 수행하십시오.
#define _GNU_SOURCE
#include <math.h>
그리고 당신은 그들에 대한 선언서를 받을 것이다.sincos()sincosf()그리고sincosl()두 값을 함께 계산하는 함수 - 아마도 목표 아키텍처를 위한 가장 빠른 방법일 것이다.
이 포럼 페이지에는 매우 흥미로운 것들이 있는데, 빠른 근사치를 찾는 데 초점을 맞추고 있다: http://www.devmaster.net/forums/showthread.php?t=5784
고지 사항:내가 직접 쓴 건 하나도 없어
업데이트 2018년 2월 22일: 웨이백 머신만이 현재 원본 페이지를 방문할 수 있는 유일한 방법: https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate-sine-cosine
CEPSHES 라이브러리에는 속도가 상당히 빠를 수 있고 CPU 시간을 조금 더/더 적게 두고 정확도를 상당히 유연하게 추가/제거할 수 있는 훌륭한 솔루션이 있다.
와하라.그래서 우리는 둘 다 얻기 위해 exp(ix)를 계산하고 싶다. - 0 - 2pi 를 사전 한다.x를 간격[0, 2pi]으로 변경한다.그런 다음 x에 가장 가까운 y를 선택하여 쓴다.
exp(ix-iy)= exp(iy) exp.
우리는 조회대에서 정보를 얻는다.그리고 |x-y|가 작기 때문에(y-값 사이의 거리 최대 절반) 테일러 시리즈는 단 몇 가지 용어로 잘 수렴될 것이므로 exp(i(x-y))에 그것을 사용한다.그리고 exp(ix)를 얻기 위해서는 복잡한 곱셈이 필요하다.
이것의 또 다른 좋은 특성은 SSE를 사용하여 벡터링할 수 있다는 것이다.
당신은 CEPHES 라이브러리에서 영감을 받은 SSE 벡터화된 구현을 제공하는 http://gruntthepeon.free.fr/ssemath/,을 보고 싶을 것이다.정확도(5e-8)와 속도(5e-8)가 좋다.
다음 중 하나를 계산한 다음 ID를 사용하십시오.
cos(x)2 = 1 - sin(x)2
@tanascius가 말했듯이, 미리 계산된 테이블이 가는 길이다.
이런 일에 성과가 중요한데 룩업 테이블을 도입하는 것은 예사롭지 않다.
창의적인 접근을 위해, 테일러 시리즈를 확장하는 것은 어떨까?그들은 비슷한 용어를 가지고 있기 때문에 다음과 같은 사이비 같은 것을 할 수 있다.
numerator = x
denominator = 1
sine = x
cosine = 1
op = -1
fact = 1
while (not enough precision) {
fact++
denominator *= fact
numerator *= x
cosine += op * numerator / denominator
fact++
denominator *= fact
numerator *= x
sine += op * numerator / denominator
op *= -1
}
이것은 당신이 이런 것을 한다는 것을 의미한다: 죄와 코사인(cosine)의 경우 x와 1에서 시작하여, 패턴을 따라라 - 코사인(cosine)에서 x^2 / 2!, 사인(sine)에서 x^3 / 3!을 빼라, x^4 / 4!를 더하고, 코사인(cosine)에 x^5 / 5!를 더하라...
나는 이것이 공연적일지 어떨지 모르겠다.빌트인 죄()와 코스()가 주는 것보다 정밀도가 낮으면 선택사항일 수 있다.
기술적으로, 당신은 복잡한 숫자와 오일러의 포뮬라를 사용함으로써 이것을 성취할 수 있을 것이다.따라서 (C++)와 같은 것
complex<double> res = exp(complex<double>(0, x));
// or equivalent
complex<double> res = polar<double>(1, x);
double sin_x = res.imag();
double cos_x = res.real();
한국사회는 수긍할 수 있다. 하는 되고 있는지에 질문이다이 작업이 내부에서 어떻게 이루어지는가는 컴파일러와 라이브러리가 사용되고 있는지에 대한 질문이다.단지 오일러의 포뮬러가 콤플렉스를 계산하는 데 주로 사용되기 때문에 이런 식으로 하는 데 시간이 더 걸릴 수 있다(그리고 걸릴 수도 있다).exp사용.sin그리고cos– 그 반대는 아니지만) 이론적 최적화가 가능할 수 있다.
편집
의 머리글<complex>GNU C++ 4.2는 다음과 같은 명시적 계산을 사용한다.sin그리고cos안쪽에polar, 그래서 컴파일러가 약간의 마법을 행하지 않는 한 그곳의 최적화에 그다지 좋아 보이지 않는다.-ffast-math그리고-mfpmathChi의 대답에 쓰여진 것과 같이 전환한다.
성능이 필요한 경우 사전 계산된 sin/cos 테이블(한 테이블이면 충분하며 사전으로 저장됨)을 사용할 수 있다.글쎄, 그것은 당신이 필요로 하는 정확성에 따라 달라지지만(아마 테이블이 크게 될 것이다), 그것은 정말 빠를 것이다.
카페에서 나타내듯이 많은 C 수학 라이브러리에는 이미 sincos()가 있다.주목할 만한 예외는 MSVC이다.
- Sun은 적어도 1987년 이후 (23년; 나는 하드 카피 맨 페이지를 가지고 있다)를 가지고 있다.
- 1997년에 HPUX 11에서 사용(HPUX 10.20에 없음)
- 버전 2.1에서 glibc에 추가 (1999년 2월)
- gcc 3.4 (2004), _builtin_sincos()에서 빌트인이 되었다.
그리고 룩업과 관련하여 에릭 S.Unix Programming의 기술 (2004) (12장)의 Raymond는 명시적으로 이것이 나쁜 생각 (현재 시점에서)이라고 말한다.
"또 다른 예는 작은 테이블을 미리 계산하는 것이다. 예를 들어, 3D 그래픽 엔진의 회전을 최적화하기 위한 정도별 sin(x) 테이블은 현대적인 기계에서 365 × 4바이트가 소요될 것이다.프로세서가 메모리보다 더 빨리 캐싱을 요구하기 전에, 이것은 명백한 속도 최적화였다.오늘날에는 테이블에 의해 야기되는 추가적인 캐시 누락의 비율을 지불하는 것보다 매번 다시 계산하는 것이 더 빠를 수 있다.
"하지만 앞으로는, 이것은 캐시가 커짐에 따라 다시 돌아설지도 모른다.보다 일반적으로 많은 최적화는 일시적이며 비용비율이 변함에 따라 쉽게 비관론으로 바뀔 수 있다.알 수 있는 유일한 방법은 측정하고 보는 것이다.(유닉스 프로그래밍의 기술에서)
그러나 위에서 논의한 것으로 미루어 모든 사람이 동의하는 것은 아니다.
나는 룩업 테이블이 반드시 이 문제에 대한 좋은 생각이라고 생각하지 않는다.당신의 정확도가 매우 낮지 않다면 그 표는 매우 커야 한다.그리고 현대의 CPU는 메인 메모리에서 값을 가져오는 동안 많은 계산을 할 수 있다.이것은 논쟁으로 적절하게 대답할 수 있는 질문들 중 하나가 아니다(내 질문도 아니다), 시험하고 측정하고 데이터를 고려할 수 있다.
하지만 AMD의 ACML과 Intel의 MKL과 같은 라이브러리에서 찾을 수 있는 SinCos의 빠른 구현을 살펴보겠다.
이 글은 사인 및 코사인 모두를 생성하는 포물선 알고리즘을 구성하는 방법을 보여준다.
DSP 트릭: Sin과 Cos의 동시 포물선 근사치
http://www.dspguru.com/dsp/tricks/parabolic-approximation-of-sin-and-cos
한 번에 두 각도의 사인 및 코사인 모두를 계산할 수 있는 인라인 ARM 어셈블리와 관련된 솔루션을 게시했다: ARMv7+NEON의 경우 빠른 사인/코사인
javascript에서 sin과 cos 기능에 대한 정확하면서도 빠른 근사치를 여기서 찾을 수 있다: http://danisraelmalta.github.io/Fmath/ (c/c++로 가져오기)
두 기능에 대한 조회 표를 선언할 생각을 해보셨습니까?여전히 죄(x)와 코스(x)를 "계산"해야 하지만, 높은 정확도가 필요하지 않다면 분명히 더 빠를 것이다.
MSVC 컴파일러는 (내부) SSE2 기능을 사용할 수 있음
___libm_sse2_sincos_ (for x86)
__libm_sse2_sincos_ (for x64)
적절한 컴파일러 플래그가 지정된 경우 최적화된 빌드에서(최소 /O2 /arch:SSE2 /fp:fast).이 함수들의 이름은 그들이 분리된 죄와 코스를 계산하는 것이 아니라 둘 다 "한 번에" 계산한다는 것을 암시하는 것 같다.
예를 들면 다음과 같다.
void sincos(double const x, double & s, double & c)
{
s = std::sin(x);
c = std::cos(x);
}
/fp:fast를 사용한 어셈블리(x86):
movsd xmm0, QWORD PTR _x$[esp-4]
call ___libm_sse2_sincos_
mov eax, DWORD PTR _s$[esp-4]
movsd QWORD PTR [eax], xmm0
mov eax, DWORD PTR _c$[esp-4]
shufpd xmm0, xmm0, 1
movsd QWORD PTR [eax], xmm0
ret 0
/fp:fast를 사용하지 않고 /fp:precise(기본값)를 사용하는 어셈블리(x86)는 별도의 죄와 cos를 호출한다.
movsd xmm0, QWORD PTR _x$[esp-4]
call __libm_sse2_sin_precise
mov eax, DWORD PTR _s$[esp-4]
movsd QWORD PTR [eax], xmm0
movsd xmm0, QWORD PTR _x$[esp-4]
call __libm_sse2_cos_precise
mov eax, DWORD PTR _c$[esp-4]
movsd QWORD PTR [eax], xmm0
ret 0
따라서 /fp:fast는 sincos 최적화를 위해 필수적이다.
그러나 유의하십시오.
___libm_sse2_sincos_
아마도 보다 정확하지 않을 것이다.
__libm_sse2_sin_precise
__libm_sse2_cos_precise
이름 끝에 " missing"가 없어졌기 때문에
최신 MSVC 2019 컴파일러와 적절한 최적화가 적용된 나의 "조금씩" 구형 시스템(Intel Core 2 Duo E6750)에서, 나의 벤치마크는 신코스의 호출이 별도의 죄와 코스콜보다 약 2.4배 더 빠르다는 것을 보여준다.
가장 빠른 방법은 체비셰프 다항식들에 의한 단일 정밀도로 함수의 근사치 입니다.논점을 도 단위로 설정하는 것이 좋기 때문에 논점을 줄이는 데 드는 자원이 적다.Visual Studio에는 다음과 같은 코드가 제안된다.C++의 예시지만 조립 코드는 다른 환경에 적응할 수 있다.
void _declspec(naked) _vectorcall SinCosD(float x, float &s, float &c)
{
_declspec(align(16)) static const float ct[8] = // Таблица констант
{
-1/180.0f, // Множитель для приведения x
-0.0f, // 80000000h
1.74532924E-2f, // b0/90 = c0
90.0f, // Константа для перехода от cos к sin
1.34955580E-11f, // b2/90^5 = c2
3.91499677E-22f, // b4/90^9 = c4
-8.86095677E-7f, // b1/90^3 = c1
-9.77249307E-17f // b3/90^7 = c3
};
_asm
{
mov eax,offset ct // В eax - адрес таблицы констант
vmovaps xmm1,[eax] // xmm1 = 90 # c0 : 80000000h # -1/180
vmovddup xmm4,[eax+16] // xmm4 = c4 # c2 : c4 # c2
vmulss xmm1,xmm1,xmm0 // xmm1 = 90 # c0 : 80000000h # -x/180
vmovddup xmm5,[eax+24] // xmm5 = c3 # c1 : c3 # c1
vcvtss2si eax,xmm1 // eax = -k, где k - округлённое до целых значение x/180
vshufps xmm2,xmm1,xmm1,93 // xmm2 = 90 # 80000000h
imul eax,180 // eax = -180*k; of=1, если переполнение
jno sc_cont // В случае слишком большого |x| считать, как при x=0
sub eax,eax // Для этого обнулить eax
vxorps xmm0,xmm0,xmm0 // и обнулить xmm0
sc_cont: // Продолжаем для корректного значения x
vcvtsi2ss xmm1,xmm1,eax // xmm1 = -180*k в позиции 0
vaddss xmm1,xmm1,xmm0 // xmm1 = x-k*180 = 90*t - число в диапазоне [-90; 90]
shl eax,29 // При нечётном k установить знаковый бит eax
vmovd xmm0,eax // В xmm0 - знаковая маска результата
vorps xmm2,xmm2,xmm1 // xmm2 = -90 # -|90*t|
vmovlhps xmm0,xmm0,xmm0 // Знаковую маску скопировать в старшую половину xmm0
vhsubps xmm2,xmm2,xmm1 // xmm2 = 90*t : 90-|90*t| - приведённые аргументы
vxorps xmm0,xmm0,xmm2 // В xmm0 - приведённые аргументы с учётом знака
vmovsldup xmm2,xmm2 // xmm2 = 90*t # 90*t : 90-|90*t| # 90-|90*t|
vmulps xmm2,xmm2,xmm2 // xmm2 = p # p : q # q - аргументы многочлена
vmovhlps xmm1,xmm1,xmm1 // xmm1 = c0 : с0 (свободный член)
vfmadd231ps xmm5,xmm4,xmm2 // xmm5 = c3+c4*p # c1+c2*p : c3+c4*q # c1+c2*q
vmulps xmm3,xmm2,xmm2 // xmm3 = p^2 : q^2
vmovshdup xmm4,xmm5 // xmm4 = c3+c4*p : c3+c4*q
vfmadd231ps xmm5,xmm4,xmm3 // xmm5 = c1+c2*p+c3*p^2+c4*p^3 : c1+c2*q+с3*q^2+с4*q^3
vfmadd231ps xmm1,xmm5,xmm2 // xmm1 = сумма для синуса : сумма для косинуса
vmulps xmm0,xmm0,xmm1 // xmm0 = sin x : cos x - готовый результат (-1)^k*t*f(t)
vmovss [edx],xmm0 // Сохранить косинус в переменной c
vextractps [ecx],xmm0,2 // Сохранить синус в переменной s
ret // Вернуться
}
}
참조URL: https://stackoverflow.com/questions/2683588/what-is-the-fastest-way-to-compute-sin-and-cos-together
'programing' 카테고리의 다른 글
| 데이터로 전체 페이지를 바인딩하는 올바른 방법 또는 vuejs 방법은 무엇인가? (0) | 2022.05.03 |
|---|---|
| 조건에 따른 VueJS HTML 요소 유형 (0) | 2022.05.03 |
| C-String을 비우는 적절한 방법 (0) | 2022.05.03 |
| vue의 로컬 저장소에 값을 추가하는 방법 (0) | 2022.05.03 |
| webpack.config.babel에서 '가져오기'를 사용하는 중 오류 발생.js (0) | 2022.05.03 |