Day 76: Python 이진 지수법 – O(log n) 내장 함수 없이 빠른 거듭제곱 계산

Source: Dev.to

빠른 거듭 제곱 함수 개요

함수 설계: 음수 지수와 기본 경우

def fast_power(x: float, n: int) -> float:
    """Return x raised to the power n using binary exponentiation."""
    if n == 0:
        return 1.0                     # base case: x⁰ = 1

    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0
    while n > 0:
        if n % 2 == 1:
            result *= x               # multiply when current bit is 1

        x *= x                        # square the base
        n //= 2                       # shift exponent right (divide by 2)

    return result

• n의 현재 최하위 비트가 1이면 result에 x를 곱합니다.
• 항상 x를 제곱하고 n을 절반으로 줄입니다.
• 예시: (x = 2, n = 5) (이진수 101) → 세 번의 반복 후 result = 32.

메인 인터랙티브: 실수 기반과 정수 지수 입력

base = float(input("Enter base (x): ").strip())
exponent = int(input("Enter exponent (n): ").strip())

value = fast_power(base, exponent)
print(f"{base}^{exponent} = {value}")

스크립트는 부동소수점 기반과 정수 지수를 읽어 fast_power로 거듭 제곱을 계산하고 결과를 출력합니다.

요약 및 고찰

• 곱셈을 위한 비트 검사: n % 2는 LSB를 분리합니다.
• 항상 제곱: x *= x는 매 루프마다 문제 크기를 줄입니다.
• 음수 지수 처리: 단순히 역수 변환을 수행합니다.
• 같은 패턴이 모듈러 거듭 제곱(xⁿ mod m)에도 적용되며, 이는 RSA 및 기타 암호 알고리즘의 핵심입니다.
• 재귀적 대안도 존재합니다(예: if n even: (x^{n/2})² else: x·x^{n‑1}), 피보나치 수열을 위한 행렬 기반 방법도 있습니다.

다음 단계 및 자료

• 챌린지 #76 소스 코드: scripts/binary_exponentiation.py
• 메인 레포지토리: 80-days-of-challenges
• 일일 업데이트: Twitter/X (@Shahrouzlogs)