#4-6-3 The Art of Computer Programming - 준수치적 알고리즘

이번 절은 거듭제곱의 평가에 대한 내용이다.

x와 양의 정수 n이 주어졌을 때 x^n을 계산하는 것에 대한 내용이다.

 

임의의 양의 정수 n에 대해 일반화하면 (n을 2진수 체계로 표현)

1을 SX로 치환

0을 S로 치환

가장 왼쪽에 나타난 "SX"를 삭제하면,

S를 제곱하기로 해석

X를 x로 곱하기로 해석한다.

 

예를 들어 n = 23인 경우 (이진수 10111)

S와 SX로 치환하면

SX S SX SX SX

그중 가장 왼쪽의 SX를 삭제하면

S SX SX SX = 제곱, 제곱, x곱, 제곱, x곱, 제곱, x곱

x^2, x^4, x^5, x^10, x^11, x^22, x^23

으로 n이 23 임을 구할 수 있다.

 

상기의 방법은 이론적으로는 유용하나

실제 컴퓨터 연산에서는 오른쪽에서 왼쪽으로 진행하므로 조금 변형된 방법을 안내한다.

N = n, Y = 1, Z = x로 초기화하고

N이 0이 될 때까지 N mod 2를 하고,

그 값이 짝수면 Z를 제곱하고

그 값이 홀수면 Y에 Z를 곱한다.

N이 0이 되면 Y를 출력해주면 된다.

 

상기의 방법도 유용하나 완전히 최적화된 횟수의 mod 연산을 수행하지는 않는다.

n = 15인 경우 상기의 예로는 6번 수행해야 하나, 실제로는 5번 수행으로 가능하다.

 

인수법(n의 인수분해에 근거한 방법)을 사용하면 된다.

 

또한 거듭제곱 트리 및 덧셈 사슬을 활용하는 방법도 소개한다.

 

덧셈 사슬은 유향 그래프와 대응되는데, 각 정점들을 부여하고 각 호를 그리면 구성이 완료된다.