지수는 어떻게 계산됩니까?

StackOverflow https://stackoverflow.com/questions/164964

  •  03-07-2019
  •  | 
  •  

문제

지수를 사용하는 알고리즘 중 하나의 점근 런 타임을 결정하려고하지만 지수가 프로그래밍 방식으로 어떻게 계산되는지 잘 모르겠습니다.

특히 이중 정제, 부동 소수점 번호에 사용되는 POW () 알고리즘을 찾고 있습니다.

도움이 되었습니까?

해결책

FDLIBM의 구현을 볼 기회가있었습니다. 의견은 사용 된 알고리즘을 설명합니다.

 *                    n
 * Method:  Let x =  2   * (1+f)
 *      1. Compute and return log2(x) in two pieces:
 *              log2(x) = w1 + w2,
 *         where w1 has 53-24 = 29 bit trailing zeros.
 *      2. Perform y*log2(x) = n+y' by simulating muti-precision
 *         arithmetic, where |y'|<=0.5.
 *      3. Return x**y = 2**n*exp(y'*log2)

처리 된 모든 특별 케이스 (0, 1, INF, NAN)의 목록이 이어집니다.

코드의 가장 강렬한 섹션은 모든 특수 사례 처리 후 log2 그리고 2** 계산. 그리고 그 중 어느 쪽에도 루프가 없습니다. 따라서 부동 소수점 프리미티브의 복잡성에도 불구하고 비대칭 적으로 일정한 알고리즘처럼 보입니다.

플로팅 포인트 전문가 (그 중 하나가 아님)는 의견을 환영합니다. :-)

다른 팁

그들이 더 나은 방법을 발견하지 않았다면, 나는 트리그, 로그 및 지수 함수에 대한 대략적인 값 (예 : 지수 성장 및 붕괴)에 대한 대략적인 값이 산술 규칙과 일반적으로 계산된다고 생각합니다. 테일러 시리즈 요청 된 정밀도 내에서 정확한 대략적인 결과를 생성하기위한 확장. (Power Series, Taylor Series 및 MacLaurin Series의 기능 확장에 대한 자세한 내용은 미적분학 서적을 참조하십시오.) 예를 들어, 계산 방법과 정확히 말할 수 없었기 때문에 시간이 오래 걸렸습니다. 시리즈의 용어 횟수는 이중 공정 계산에서 무시할 수있을 정도로 작은 오류를 보장해야합니다.

예를 들어, E^x의 Taylor/MacLaurin 시리즈 확장은 다음과 같습니다.

      +inf [ x^k ]           x^2    x^3      x^4        x^5
e^x = SUM  [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
      k=0  [  k! ]           2*1   3*2*1   4*3*2*1   5*4*3*2*1

모든 용어를 사용하는 경우 (0에서 무한대로)이 확장은 정확하고 완전합니다 (오류 없음).

그러나 모든 용어를 무한대로 가져 가지 않으면 5 가지 용어 또는 50 용어 또는 그 밖의 말을 중단하면 근사치를 내다 결과를 계산하기가 상당히 쉬운 나머지에 의해 실제 e^x 함수 값과 다른 결과.

지수에 대한 좋은 소식은 그것이 훌륭하게 수렴하고 다항식 확장의 용어는 반복적으로 코딩하기가 상당히 쉽다는 것입니다. ~할 것 같다 (반복하다, 할 것 같다 - 오랜 시간이 걸렸다는 것을 기억하십시오.) 각 반복에서 기여도 크기를 테스트하고 0에 가까워지면 중지 할 수 있기 때문에 오류가 정밀도보다 적지 않도록 보장하는 데 필요한 용어를 사전 계산할 필요조차 없습니다. 실제로, 나는이 전략이 실행 가능한지 아닌지 모른다. 나는 그것을 시도해야 할 것이다. 오랫동안 잊어 버린 중요한 세부 사항이 있습니다. 마찬가지 : 기계 정밀, 기계 오류 및 반올림 오류 등

또한 e^x를 사용하지 않지만 2^x 또는 10^x와 같은 다른베이스로 성장/붕괴를하는 경우 근사화 된 다항식 기능이 변경됩니다.

정수 지수를 위해 A를 B로 올리는 일반적인 접근 방식은 다음과 같이됩니다.

result = 1
while b > 0
  if b is odd
    result *= a
    b -= 1
  b /= 2
  a = a * a

일반적으로 지수 크기의 로그입니다. 알고리즘은 변하지 않는 "a^b*result = a0^b0"을 기반으로하며, 여기서 a0과 b0은 a와 b의 초기 값입니다.

부정적 또는 비 지수의 경우 로그 및 근사치 및 수치 분석이 필요합니다. 실행 시간은 사용 된 알고리즘과 라이브러리가 조정되는 정밀도에 따라 다릅니다.

편집 : 관심이있는 것으로 보이므로 여기에 추가 곱셈이없는 버전이 있습니다.

result = 1
while b > 0
  while b is even
    a = a * a
    b = b / 2
  result = result * a
  b = b - 1

인텔을 타겟팅하는 POW 함수를 작성하는 경우 exp2 (log2 (x) * y)를 반환합니다. Log2에 대한 인텔의 마이크로 코드는 첫해 미적분학과 대학원 수치 분석을 기억할 수 있어도 코딩 할 수있는 것보다 확실히 빠릅니다.

x를 계산하기 위해 Exp (n*ln (x))를 사용할 수 있습니다.N. X와 N은 모두 이중 정제, 부동 소수점 번호 일 수 있습니다. 천연 로그 및 지수 함수는 Taylor 시리즈를 사용하여 계산할 수 있습니다. 여기에서 공식을 찾을 수 있습니다. http://en.wikipedia.org/wiki/taylor_series

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top