태그 보관물: algorithm

algorithm

죄와 cos를 함께 계산하는 가장 빠른 방법은 무엇입니까? = cos(x); b = sin(x);, 처럼

값의 사인과 코사인을 함께 계산하고 싶습니다 (예 : 회전 행렬 생성). 물론 a = cos(x); b = sin(x);, 처럼 하나씩 하나씩 따로 계산할 수 는 있지만 두 값이 모두 필요할 때 더 빠른 방법이 있는지 궁금합니다.

편집 :
지금까지 답변을 요약하려면 :

  • VladFSINCOS두 가지를 모두 계산하는 asm 명령이 있다고 말했습니다(FSIN혼자호출과 거의 동시에)

  • Chi가 알아 차린 것처럼 ,이 최적화는 때때로 컴파일러에 의해 이미 수행됩니다 (최적화 플래그를 사용할 때).

  • 카페는 기능이 있음을 지적sincos하고sincosf아마 가능하며 단지 포함하여 직접 호출 할 수 있습니다math.h

  • 조회 테이블을 사용하는 tanascius 접근 방식은 논란의 여지가 있습니다. (그러나 내 컴퓨터와 벤치 마크 시나리오에서는sincos32 비트 부동 소수점에 대해 거의 동일한 정확도보다 3 배 빠르게 실행됩니다.)

  • Joel Goodwin 은 매우 정확한 근사화 기법에 대한 흥미로운 접근 방식에 연결했습니다 (저에게는 테이블 조회보다 훨씬 빠릅니다).



답변

최신 Intel / AMD 프로세서에는 FSINCOS사인 및 코사인 함수를 동시에 계산하는 명령 이 있습니다. 강력한 최적화가 필요한 경우이를 사용해야합니다.

다음은 작은 예입니다. http://home.broadpark.no/~alein/fsincos.html

다음은 MSVC의 다른 예입니다. http://www.codeguru.com/forum/showthread.php?t=328669

다음은 또 다른 예입니다 (gcc 사용) : http://www.allegro.cc/forums/thread/588470

그들 중 하나가 도움이되기를 바랍니다. (이 지침을 직접 사용하지 않았습니다.)

프로세서 수준에서 지원되므로 테이블 조회보다 훨씬 빠를 것으로 기대합니다.

편집 :
WikipediaFSINCOS387 프로세서에 추가 되었다고 제안 하므로 지원하지 않는 프로세서를 거의 찾을 수 없습니다.

편집 :
인텔의 문서에 따르면 부동 소수점 분할 FSINCOS보다 약 5 배 정도 느립니다 FDIV.

편집 :
모든 최신 컴파일러가 사인 및 코사인 계산을 FSINCOS. 특히 내 VS 2008은 그렇게하지 않았습니다.

편집 :
첫 번째 예제 링크는 죽었지 만 Wayback Machine에 여전히 버전있습니다 .


답변

최신 x86 프로세서에는 사용자가 요청한 것을 정확히 수행하는 fsincos 명령어가 있습니다. sin과 cos를 동시에 계산합니다. 좋은 최적화 컴파일러는 같은 값에 대해 sin과 cos를 계산하는 코드를 감지하고이를 실행하기 위해 fsincos 명령을 사용해야합니다.

이것이 작동하려면 컴파일러 플래그를 약간 돌리는 것이 필요했지만 :

$ 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

Tada, fsincos 명령어를 사용합니다!


답변

성능이 필요할 때 미리 계산 된 sin / cos 테이블을 사용할 수 있습니다 (하나의 테이블이 가능하며 사전으로 저장 됨). 글쎄, 그것은 당신이 필요로하는 정확도에 달려 있지만 (아마도 테이블이 클 것입니다), 정말 빨라야합니다.


답변

기술적으로는 복소수와 오일러 공식 을 사용하여이를 달성 할 수 있습니다. 따라서 (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 의 헤더 는 sincosinside 에 대한 명시 적 계산을 사용 polar하므로 컴파일러가 마법을 수행하지 않는 한 최적화에 너무 좋지 않습니다 ( Chi의 답변에 작성된 -ffast-math-mfpmath스위치 참조 ).


답변

둘 중 하나를 계산 한 다음 ID를 사용할 수 있습니다.

cos (x) 2 = 1-sin (x) 2

그러나 @tanascius가 말했듯이 미리 계산 된 테이블이 갈 길입니다.


답변

GNU C 라이브러리를 사용하는 경우 다음을 수행 할 수 있습니다.

#define _GNU_SOURCE
#include <math.h>

sincos(), sincosf()sincosl()두 값을 함께 계산하는 함수의 선언을 얻을 수 있습니다. 아마도 대상 아키텍처에 대해 가장 빠른 방법 일 것입니다.


답변

이 포럼 페이지에는 빠른 근사치를 찾는 데 초점을 맞춘 매우 흥미로운 내용이 있습니다.
http://www.devmaster.net/forums/showthread.php?t=5784

면책 조항 :이 물건을 직접 사용하지 않았습니다.

2018 년 2 월 22 일 업데이트 : Wayback Machine은 현재 원본 페이지를 방문하는 유일한 방법입니다 : https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate- 사인 코사인