알고리즘 문제 해결 전략 I (2)

알고리즘 문제 해결 전략 I

p.75~

 

실수 자료형의 이해

컴퓨터가 사용하는 실수 표현방식과 그 장단점을 이해해야만 한다.

IEE 754 표준을 가장 많은 컴퓨터와 컴파일러들에서 사용되고 있다.

 

특징:

이진수로 실수를 표기

부동소수점 표기

무한대 비정규수 숫자가 아님 등의 특수값 존재.

 

가장많이 다룰 [실수의 이진법 표기]

실수표준에서는 소수점을 고정시키지 않고 옮길 수 있도록 만들어짐

따라서 큰수도 적확한 수도 다 커버가능

실수변수에서는 3가지의 정보를 저장하게 됨

1. 부호비트 2. 지수 (소수점을 몇칸 옮겼는지) 3. 가수 (소수점을 옮긴 실수의 최상위 X비트)

 

64비트의 경우 53비트의 가수를 표현할 수 있게 되는데, 이는 마지막 반올림 되고 버려지는 자리의 수의 비중은 9000조 분의 1 이므로 거의 전체 숫자에 영향이 없다

 

하지만 32비트의 경우에는 최대 7자리의 정확도밖에 제공하지 못하는데, 현실에서 사용하기란 너무나 부정확함.

따라서 대부분의 경우 64비트의 변수형을 사용하는것을 권장.

 

32비트 실수 유효자리수 : 6

64비트 실수 유효자리수 : 15

80비트 실수 유효자리수 : 18

 

이와같이 소수점을 움직이는 실수 표기법을 소수점이 둥둥 떠다닐수 있다는 의미에서 부동 소수점 표기방식이라고 부른다.

 

반대로 고정되어있는 실수 표기법은 고정소수점 실수 표기법이라고 부른다.

 

두 실수비교하기

 

두 실수값이 같은지를 비교할때는 항상 어느정도 오차를 염두에 두어야 한다.

(두 값의 차이가 매우 작은 경우 두 값이 같다고 판단해야 한다.)

bool absoluteEqual(double a, dobule b){
	return fabs(a-b) < 1e-10; //fabs() 함수는 주어진 실수의 절대값을 구해준다.
}

하지만 이 함수도 완전하고 안전한것은 아니다. (오차범위에 따른 에러 발생 가능성 있다)

해결방법 1 : 비교할 실수들의 크기에 비례한 오차 한도 정하기 (동적 오차 범위)

해결방법 2 : 상대 오차이용 (동적 오차 범위)

bool relativeEqual(double a, double b){
	return fabs(a-b) <=1e-8 * max (fabs(a), fabs(b));
}

큰수를 비교할때는 문제가 없지만 매우 작은 숫자들을 비교할떄는 문제가 될 수 있다. 

 

//절대오차 상대오차 둘다 사용
bool doubleEqual(double a,double b){
	double diff = fabs(a-b); 
    if(diff<1e-10) return true; //절대오차가 허용범위 안일경우 같다고 판단 
    return diff <= 1e-8 * max(fabs(a), fabs(b)); //그렇지 않을경우 상대오차사용한 판단 리턴
}

대소비교

 

대소를 판단할 때도 연산오차때문에 같은것임에도 불구하고 차이가 생겨 대소가 생길 수 있기 때문에 같은지 확인하는 과정이 먼저 필요하다.

 

정확한 사칙연산

실수변수라고 해서 그값이 항상 정확하지 않은것은 아님. 정확하게 표현할 수 있는 값은 항상 정확하게 저장되도록 구현됨. 

 

1. 가수부 안에 들어가는 정수들 : 절대값이 2의 52승보다 작은 모든 정수들

 

코드의 수치적 안정성 파악하기

 

실수연산은 제대로 하기 어렵다. 따라서 실수연산을 아예 하지 않는 방법이 있다.

1. 곱셈과 나눗셈의 순서를 바꾸기. 결과가 정수임을 알고 있을 때, 나눗셈을 나중에 하는 방법으로 실수연산을 하지 않을 수 있다.

2. 양변 제곱하기

3. 실수좌표를 써야하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘리는 방법

 

 

알고리즘 문제 해결 전략 I 中 

2020.07.07 (화)