[프로그래밍 일반] 한 권으로 읽는 컴퓨터 구조와 프로그래밍_ch11 성능 향상을 위한 알고리즘 기법

계산을 효율적으로 하는 것보다 더 나은 것은 바로 계산을 전혀 하지 않는 것이다.
이번 장에서는 계산을 피하는 두 가지 방법을 살펴본다.
지름길shortcut과 근삿값 계산approximating이다.


ㅁ 표 찾기

표 찾기는 어떤 계산을 많이 하는 경우, 그 결과를 미리 계산해서 반복 사용하는 편이 합리적이라는 측면에서
8장에서 설명한 루프 불변값 최적화와 비슷하다.

- 텍스처 매핑
텍스처 매핑에서 표 찾기 기법이 중요한 역할을 한다.
텍스처 매핑은 거리에 따라 텍스처를 조정하는 일이 필요하지만 복잡하다.
뷰포인트가 텍스처가 멀어지면 인접한 픽셀을 서로 합쳐서 평균을 내야 한다.

랜스 윌리엄스는 MIP 매핑이라는 접근 방법을 고안 했다.
픽셀은 세 가지 8비트 값으로 이뤄진다.
32비트 시스템에서 이를 정사각형으로 나열하면 공간 중 1/4이 낭비된다는 점에 주목하였다.
RGB를 제외한 나머지 1/4 공간에 이미지의 1/4 크기 복사본을 넣는다.
윌리엄스는 이런 방식의 이미지를 MIP 맵이라고 불렀다.

시점에 따라 실제 텍스처 이미지를 계산해야 하는 경우, MIP맵에서 가장 가까운 계층에 있는
이미지를 사용해 계산하면 시간을 상당히 절약할 수 있다.
자주 사용할 정보를 미리 계산해두는 것은 루프 불변값 최적화와 비슷하다.

ㅁ 정수를 사용한 계산 방법

정수 덧셈이나 뺄셈은 비용이 싸고, 곱셈이나 나눗셈은 비용이 더 많이 든다.
부동소수점 연산은 더더욱 비싸다. 따라서 비싼 연산을 피할 수 있는 방법을 찾아내는 것이 바람직하다.

ㅁ 재귀적 분할

재귀적 분할을 쓸모가 많은 기법이다.
최소한의 작업으로 원하는 목적을 달성할 수 있다.

- 나선 : 가장 일반적으로 사용하는 방법은 라디안이다. 

ㅁ 계산을 회피하는 그 밖의 수학적 기법들

- 멱급수 근삿값 계산 : 충분히 가까움이라는 개념을 활용한다.
- CORDIC 알고리즘 : 좌표회전 디지털 컴퓨터 알고리즘이다.

ㅁ 무작위성과 관련있는 예제들

컴퓨터에서 완전한 난수를 계산하기는 어렵다.
난수를 만드려면 어떤 공식을 기반으로 생성해야하는데,
정해진 공식으로 생성한 난수는 반복적일 수밖에 없다.
그러나 대부분의 계산작업에서는 이런 유형의 의사난수로도 충분하다.