The Art of Computer Programming 2: 준수치적 알고리즘(개정 3판)

컴퓨터가 "수"를 다루는 최상의 방법

이 책은 알고리즘을 좀더 깊게 파고들 필요가 있는 독자를 위해 여러 권으로 이루어진 시리즈 도서 중 두번째 책이다. 2권에서는 컴퓨터가 수를 다루는 최상의 방법을 어떻게 찾는지를 다루고 있다. 1권처럼 대학 교재뿐만 아니라 독학도 가능하도록 충분한 연습문제를 제공하고 있어 배운 내용을 빠짐없이 복습하고 응용해볼 수 있다.

"이 책에서 논의하는 알고리즘들은 수를 직접적으로 다룬다. 그렇긴 해도 나는 그 알고리즘들을 준수치적(準-, seminumerical)이라고 부르는 게 합당하다고 믿는다. 왜냐하면 그것들은 수치적 계산과 기호적 계산의 경계선에 걸쳐 있기 때문이다. 모든 알고리즘은 단지 문제가 요구한 답을 계산할 뿐만 아니라 디지털 컴퓨터의 내부 작동과도 잘 조화되도록 만들어져 있다. 그러한 알고리즘의 완전한 미덕을 절실하게 느낄 수 있으려면 컴퓨터의 기계어에 대한 어느 정도의 지식이 필요한 경우가 많다. 해당 컴퓨터 프로그램의 효율성은 알고리즘 자체와는 떼어놓을 수 없는 필수적인 요소이다. 문제는 컴퓨터가 수를 다루는 최상의 방법을 찾는 것이고, 그러려면 수치적 측면뿐만 아니라 전술적인 측면도 고려해야 한다. 따라서 이 책의 주제가 수치적 수학뿐만 아니라 전산학의 일부임은 명백하다."
_저자 서문 중에서

주요 내용

• 균등 난수 생성
• 통계적 검증
• 다른 종류의 무작위 수량들
• 난수열
• 위수치체계
• 부동소수점 산술
• 다중 정밀도 산술
• 기수 변환
• 유리수 산술
• 다항식 산술
• 멱급수

"일전에 게이머들 사이에서 Culdcept Saga라는 콘솔용 게임의 버그가 작게나마 화제가 된 적이 있습니다. 이 게임은 기본적으로 주사위를 굴려서 보드 상의 말을 움직이고, 여러 종류의 카드를 통해서 특별한 행동이나 전투를 진행하는 보드 게임 형태입니다. 두 가지 버그가 특히 흥미로웠는데, 하나는 2인용으로 게임을 진행하면서 주사위를 굴릴 때 한 플레이어는 항상 홀수 눈금만, 다른 플레이어는 항상 짝수 눈금만 나온다는 버그이고, 또 하나는 카드들을 정렬할 때 게임이 죽은 것이 아닌가 싶을 정도로 긴 시간이 걸린다는 것입니다. 예, 바로 이 책의 한 주제인 난수와, 시리즈 제3권의 한 주제인 정렬에 대한 버그인 것입니다. 프로그래머가 이 시리즈를 읽었다면 그런 버그를 만들지는 않았을 것입니다."
_역자 서문 중에서