[C] 거듭제곱 함수 만들기

https://persestitan.tistory.com/130

[C] 팩토리얼 함수 만들기

이전 글에서 언급하였지만 제귀함수, 반복문 중 자신이 계산이 편하다고 느끼는 방식으로 작성하시면 됩니다.

해당 코드에서는 x의 n승을 구하는 코드로 작성하였습니다.

 

제귀함수

반복

n이 0이 될때까지 1씩 감소시키면서 x을 계속 곱하여 값을 구하는 방법입니다.

double power1(double x, int n) {
    if (n == 0) return 1;
    else return x * power1(x, n-1);
}

최적화 반복

제곱을 나누어 계산 길이를 줄이는 방법입니다.

짝수 예시

x^4일경우 (x^2)^2로 계산하여 본래 4번 반복하여 곱해야할 계산을 2번 계산으로 줄여서 계산을 하게 됩니다.

(x^2)^2 = (x * x)^2 = x * x * x * x = x ^ 4

홀수 예시

x^5일 경우 x * ((x ^ 2)^2)로 계산하여 5번 반복하여 곱해야하는 계산을 3번 계산으로 줄여서 계산을 하게 됩니다.

x * ((x^2)^2) = x * ((x * x) ^ 2) = x * x * x * x * x = x ^ 5

double power2(double x, int n) {
    if (n == 0) return 1;
    else if (n % 2 == 0) return power2(x * x, n / 2);
    else return x * power2(x * x, (n - 1) / 2);
}

 

반복문

for문

x를 n번 곱하여 계산된 값을 반환하는 방법입니다.

double power3(double x, int n) {
    double r = 1;
    for (int i = 1; i <= n; ++i) r *= x;
    return r;
}

while문

for문과 동일한 방법으로 x를 n번 곱하여 계산하는 방법입니다.

double power4(double x, int n) {
    double r = 1;
    while (--n >= 0) r *= x;
    return r;
}

최적화 반복

제귀함수에 작성한 최적화 반복의 반복문 버전입니다.

해당 코드 같은경우 코드길이를 줄이기 위해서 공통된 코드는 밖으로 빼다보니 아래와 같은 코드가 되었습니다.

n이 홀수일경우 n의 값을 1줄이고 결과값에 x를 곱하는 동작만 추가적으로 진행해주면 되기 때문에 아래와 같이 간결하게 변경이 가능합니다.

double power5(double x, int n) {
    double r = 1;
    while (n > 0) {
        if (n % 2 != 0) {
            r *= x;
            n--;
        }
        n /= 2;
        x *= x;
    }
    return r;
}