정밀도 손실을 피하기위한 최상의 알고리즘?

Question

내가받은 숙제 중 컴퓨터에서 수행 할 때 정확도가 떨어질 수있는 표현을 사용하도록 요청하고 이러한 손실을 피할 수 있도록 변경합니다.

불행히도이 작업을 수행하는 방법은 분명하지 않습니다. 다양한 예제가 수행되는 것을 보면서, 테일러 시리즈를 사용하거나, 제곱근이 포함되어있을 때 공액을 사용하거나, 두 분수를 뺄 때 공통 분모를 찾는 방법이 있음을 알고 있습니다.

그러나 정밀도의 손실이 발생할 때 정확히 알 수있는 몇 가지 문제가 있습니다. 지금까지 내가 알고있는 유일한 사실은 동일한 숫자에 가까운 두 숫자를 빼면 높은 자리 숫자가 중요하기 때문에 정밀도의 손실이 발생한다는 것입니다.

내 질문은 내가 찾고 있어야하는 다른 일반적인 상황이 무엇인지, 그리고 그들에게 접근하는 '좋은'방법으로 간주되는 것은 무엇인가?

f(x) = tan(x) − sin(x) when x ~ 0 

이 세 가지 선택에서이를 평가하는 최고와 최악 알고리즘 무엇입니까 : 예를 들어

는 여기에서 문제가

(a) (1/ cos(x) − 1) sin(x), 
(b) (x^3)/2 
(c) tan(x)*(sin(x)^2)/(cos(x) + 1). 

이해가 x는 가까운 때 tan (x)와 sin (x)는 거의 같습니다. 나는이 알고리즘 중 어떤 것이 어떻게 또는 왜 문제를 해결하기 위해 더 좋든 나쁘 든 이해하지 못한다.

Answer 1

일반적으로 사용되는 또 다른 규칙은 다음과 같습니다. 긴 일련의 숫자를 추가 할 때는 0에 가장 가까운 숫자부터 더하고 가장 큰 숫자로 끝납니다.

이것이 좋은 이유를 설명하는 것은 까다로운 일입니다. 큰 숫자에 작은 숫자를 추가 할 때 큰 숫자의 현재 가수에서 가장 작은 숫자보다 작기 때문에 완전히 버려 질 가능성이 있습니다. 예를 들어이 상황을 : 0.01가 가장 낮은 가수의 자리보다 작은

a = 1,000,000; 
do 100,000,000 time: 
    a += 0.01; 

경우, 다음 루프는 아무것도하지 않고 최종 결과는 == 1,000,000 하지만이 같은이 작업을 수행 할 경우 :

a = 0; 
do 100,000,000 time: 
    a += 0.01; 
a += 1,000,000; 

낮은 숫자가 천천히 커지면 옳은 대답 인 == 2,000,000에 가깝게됩니다.
극단적 인 예는 물론이지만 아이디어를 얻길 바랍니다.

Answer 2

내가 학부생이었을 때 숫자 수업을 다시 받아야했고, 그것은 완전히 고통 스러웠습니다. 어쨌든 IEEE 754은 일반적으로 현대 CPU에서 구현되는 부동 소수점 표준입니다. 기본적인 내용을 이해하는 것이 유용합니다. 이렇게하면하지 말아야 할 것에 대한 많은 직관이 생깁니다. 컴퓨터의 단순화 된 설명은 부동 소수점 숫자를 지수 및 가수에 대한 고정 자릿수 (비트)를 가진 2 진수 표기법과 같은 것으로 저장한다는 것입니다. 즉, 숫자의 절대 값이 클수록 정확하게 표현할 수 없습니다. IEEE 754의 32 비트 부동 소수점의 경우 가능한 비트 패턴의 절반은 -1과 1 사이의 값을 나타내지 만 약 10^38까지의 숫자는 32 비트 부동 소수점으로 표현할 수 있습니다. 2^24보다 큰 값 (약 1670 만)의 경우 32 비트 부동 소수점은 모든 정수를 정확하게 나타낼 수 없습니다.

1. 최종 해답이 작은 것으로 예상되는 경우 중간 값이 크게 갖는이 당신을 위해 무엇을 의미

   는 일반적으로 다음과 같은 피하고 싶은 것입니다.

2. 큰 숫자에 작은 숫자를 더하거나 빼기. 예를 들어, 같은 것을 쓴 경우 :

   에 대한 (플로트 지수 = 17000000; 인덱스를 < 17000001, 인덱스 ++) {}

17000000 + 1 17000000로 내림됩니다 becuase이 루프는 종료하지 않을 것입니다. 당신이 뭔가를 가지고 있다면 :

float foo = 10000000 - 10000000.0001 

foo에 대한 값으로 인해 오류를 반올림, 0,하지 -0.0001 될 것이다.

Answer 3

피할 수있는 또 다른 사항은 거의 동일한 수를 빼는 것입니다. 이로 인해 반올림 오류에 대한 민감도가 높아질 수 있습니다. 0에 가까운 값의 경우, cos (x)는 1에 가깝습니다. 따라서 1/cos (x) - 1은 가능하면 피해야하는 빼기 중 하나이므로, (a)는 피해야합니다. .

Answer 4

내 질문은 내가 무엇을 보고해야 다른 일반적인 상황이며, 무엇을 접근 방법 '좋은'로 간주됩니다입니까?

심각한 또는 심각한 재현 손실이 발생할 수있는 몇 가지 방법이 있습니다.

가장 중요한 이유는 부동 소수점 숫자가 제한된 자릿수를 가지고 있기 때문입니다. 예를 들어, 두 배는 53 비트입니다. 즉, 솔루션의 일부가 아니지만 저장해야하는 "쓸모없는"숫자가 있으면 정확도가 떨어집니다.

예를 들어

(우리는 데모 진수 형식을 사용하는) :

2.598765000000000000000000000100 -

2.598765000000000000000000000099

흥미로운 부분은 100-99 = 1 대답이다. 두 경우 모두 2.598765가 동일하기 때문에 은 결과를 변경하지 않지만 8 자리를 낭비합니다. 컴퓨터가 에 숫자가 쓸모 없다는 것을 알지 못하기 때문에 컴퓨터를 저장하지 않아서 더 이상 0을 채우지 못합니다. 모두 29 자리를 낭비합니다. 불행히도 차이를 피할 수있는 방법은 없습니다. 하지만 다른 경우가 있습니다. exp (x) -1 이것은 물리학에서 자주 발생하는 함수입니다.

0에 가까운 exp 함수는 거의 선형이지만 선행 숫자로 1을 적용합니다. 12 개 유효 숫자 특급 (0.001)에 따라서 -1 = 1.00100050017-1 = 1.00050017e-3 우리가 대신 함수 expm1를 (사용하는 경우

), 테일러 시리즈를 사용

1 + X + X^2/2 + x^3/6 ...-1 =

X + X^2/2 + X^6분의 3 = expm1 (X)

expm1 (0.001) = 1.00500166667e -3-

훨씬 더.

두 번째 문제는 pi/2 근처에서 x의 탄젠트처럼 매우 가파른 경사가있는 함수입니다. tan (11)의 기울기는 50000입니다. 즉, 반올림 오류 으로 인한 작은 편차가 계수 50000으로 증폭됩니다! 또는 예를 들어 특이점이 있습니다. 결과는 0/0에 접근합니다. 즉, 모든 값을 가질 수 있음을 의미합니다.

두 경우 모두 대체 함수를 만들어 원래 함수를 시뮬레이트합니다. 교육을받지 않으면 처음에는 문제를 단순히 "보지"않을 것이기 때문에 다양한 솔루션 접근법을 강조하는 것은 유용하지 않습니다.

배우고 훈련 할 수있는 아주 좋은 책 : Forman S. Acton : Real Computing made real