순환-거듭제곱 계산 알고리즘(2)

https://sysouthelloworld.tistory.com/81

순환-거듭제곱 계산

위 글에 적지 않은 다른 방법이 더 있다.

double pow(int x, int n) {
	int res = 1;
	int a = x;

	while (n > 0) {
		if (n % 2 == 1) {	//excluded when remainder is 0
			res = res * a;
		}

		a *= a;
		n /= 2;	//quotient when n is divided by 2
	}

	return res;
}//O(logN)

 

e.g., x^29 = x^16 * x^8 * x^4 * x에 대해

a	current value of n	n % 2	res	n/2
x	29	1	x	14
x^2	14	0	-	7
x*4	7	1	x * x^4 = x^5	3
x^8	3	1	x^5 * x^8 = x^13	1
x^16	1	1	x^13 * x&16 = x^29	0

 

십진수↔이진수 변환 알고리즘에서 차용?