거듭제곱(Power) 함수는 동일한 수를 여러 번 곱하는 연산입니다. 예를 들어 5의 n제곱(5n)은 5를 n번 곱한 값, 즉 5 × 5 × 5 × … (n번)과 같습니다. 이러한 거듭제곱 계산을 곱셈(*)과 나눗셈(/) 연산자 없이 구현하려면 중첩 루프(nested loop)를 활용하여 숫자를 지정된 횟수만큼 반복해서 더하는 방식을 사용할 수 있습니다.
동작 원리
곱셈은 본질적으로 덧셈의 반복입니다. 예를 들어 4 × 4는 4를 4번 더한 값과 같으므로, 덧셈만으로도 곱셈 결과를 얻을 수 있습니다. 이 원리를 확장하면 거듭제곱 역시 덧셈 연산만으로 계산할 수 있습니다.
- 지수가 0인 경우 → 결과는 항상 1
- 그 외의 경우 → 중첩 루프를 통해 덧셈을 반복하여 계산
예제 코드
#include <iostream>
using namespace std;
int main() {
int a = 4, b = 2; // 4의 2제곱 계산
if (b == 0)
cout << "The answer is " << 1;
int answer = a; // 초기값: 밑수
int increment = a; // 반복해서 더해질 값
int i, j;
for(i = 1; i < b; i++) { // 지수만큼 반복
for(j = 1; j < a; j++) { // 밑수만큼 덧셈 반복
answer += increment;
}
increment = answer; // 다음 단계에서 더할 값 갱신
}
cout << "The answer is " << answer;
return 0;
}실행 결과
The answer is 16
코드 설명
위 예제는 4의 2제곱(4² = 16)을 계산하는 과정입니다.
- 초기화: answer와 increment를 모두 밑수(a = 4)로 설정합니다.
- 외부 루프: 지수(b)에서 1을 뺀 횟수만큼 반복합니다. 첫 번째 값은 이미 answer에 저장되어 있기 때문입니다.
- 내부 루프: 현재 누적된 값(answer)을 밑수(a)에서 1을 뺀 횟수만큼 더합니다. 이렇게 하면 매 단계마다 answer = answer × a와 동일한 효과를 얻을 수 있습니다.
- 갱신: increment를 새로운 answer 값으로 업데이트하여 다음 반복에 사용합니다.
이 알고리즘의 시간 복잡도는 O(a × b)로, 밑수와 지수가 커지면 연산 횟수가 빠르게 늘어난다는 점을 유의해야 합니다. 그럼에도 불구하고 곱셈 연산자를 전혀 사용하지 않고도 거듭제곱 값을 정확하게 계산할 수 있다는 것이 이 방식의 핵심입니다.