[C] 제곱 구하기

 

C언어 기반 제곱 구하는 방식 정리

 

1. 정수 지수 제곱 (정수^정수, 실수^정수)

1-1. for문

가장 기초적인 방식? 이라고 생각한다.
아 뭐 2 * 2 * 2 * 2... 이것도 있지만 이건 제외한다.

⭐ 장점 : 가장 단순하고 직관적이다? 쉽게 생각할 수 있는 방식이라고 생각한다. ㅎ
😑 단점 : 지수가 크면 클수록 성능이 떨어지고 오버플로우 위험이 존재한다. (시간복잡도 O(n))

 

#include <stdio.h>

int power_for(int base, int exp) { // base^exp
    int result = 1;
    
    for(int i = 0; i < exp; i++) {
        result *= base;
    }
    
    return result;
}

 

1-2. Exponentiation by Squaring(Binary Exponentiation)

❌ 거듭제곱을 순서대로? 하지 않고
      ex) 2^13 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 
 
👍 지수를 이진수로 표현한 후
      ex) 13 → 1101

✌ 각 자리의 비트가 1일 때만 제곱값을 포함해서 곱하는 방식이다.
      ex) 2^13 = 2^8 * 2^4 * 2*1 

즉, 필요한 제곱 값들만 선택적으로 곱하는 방식이라 매우 빠르다.

⭐ 장점 : for문에 비해 매우 빠른 성능을 가지며 지수가 클수록 효율?이 좋다. (시간복잡도 O(log n))
😑 단점 : 오버플로우 위험이 있긴 하다.

 

#include <stdio.h>

int fast_power(int base, int exp) {
    int result = 1;
    
    while(exp > 0) {
        if(exp % 2 == 1) { result *= base; }
    
        base *= base;
        exp /= 2;
    }
    
    return result;
}

 

1-3. Modular Exponentiation

Exponentiation by Squaring + 오버플로우 방지 알고리즘 이다.
주어진 mod 값을 이용하여 계산값을 계속 나눠주어 오버플로우를 방지한다.

⭐ 장점 : mod로 값을 계속 나눠주기 때문에 오버플로우를 방지한다. 안정성 ↑
😑 단점 : mod 연산으로 인해 성능이 떨어지긴 한데 무시할 정도긴 하다. (시간복잡도 O(log n))

 

#include <stdio.h>

int fast_power(int base, int exp, int mod) {
    int result = 1;
    base %= mod;
    
    while(exp > 0) {
        if(exp % 2 == 1) { result = (result * base) % mod; }
    
        base = (base * base) % mod;
        exp /= 2;
    }
    
    return result;
}

 

1-4. pow() 함수

표현식 : pow(base, exp)
C 표준 수학 라이브러리 <math.h> 에 정의된 함수이며 double형을 반환한다.


⭐ 장점 : 함수 사용으로 코드가 간결하다. 한 줄로 끝 (라이브러리까지 2줄)
😑 단점 : 지수가 커지면 정확도와 성능이 떨어진다. (시간복잡도 O(1)) (단, 내부 연산 무거움)
                실수값으로 반환한다. (정수계산 시 정확도 손실 위험이 있다.)              

 

#include <stdio.h>
#include <math.h>

int main(void) {
    double result = pow(2.5, 3) // 2.5^3
    
    printf("%.3f\n", result);
    
    return 0;
}

 

2. 실수 지수 제곱 (정수^실수, 실수^실수)

2-1. pow() 함수

지수가 실수인 경우 pow() 함수를 사용한다.
직접 코드를 작성할 순 있으나 효율이 너무 떨어질것 같음... 

⭐ 장점 : 실수 지수 지원 및 직접 구현하는것 보다 빠르고 안정적이다.
😑 단점 : double 기반이라 소수점 오차 발생 가능 하다. (특히 비교 연산 시 주의가 필요함)

 

#include <stdio.h>
#include <math.h>

int main(void) {
    double result = pow(2.5, 3.5) // 2.5^3.5
    
    printf("%.3f\n", result);
    
    return 0;
}