DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 76: Python Binary Exponentiation – O(log n) Fast Power Calculation Without Built-Ins

#challenge #python #algorithms #programming

Welcome to Day 76 of the #80DaysOfChallenges journey! This intermediate challenge implements binary exponentiation to compute x^n in O(log n) time, using bit manipulation and iterative squaring to avoid slow naive multiplication loops or recursion. It handles positive/negative exponents and floats, making it a versatile math tool for algorithms, cryptography, or simulations. If you're optimizing power calculations or prepping for interviews with fast expo questions (LeetCode #50 style), this "Python binary exponentiation" script demonstrates a function that's efficient, handles edges, and easy to adapt for modular expo in crypto.

💡 Key Takeaways from Day 76: Fast Power Function

This task features a function that reduces exponent by half each step, squaring base and multiplying on odd bits. It's a divide-and-conquer pattern: halve exponent, square base. We'll detail: function with negative handling and result init, loop for bit-based multiply and square, and main with float input.

1. Function Design: Negative Expo and Base Cases

The fast_power function takes base x and exponent n, returns float:

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^0 = 1

    if n < 0:
        x = 1 / x                     # invert base for negative exponent
        n = -n

    result = 1.0
Enter fullscreen mode Exit fullscreen mode

Handles n=0 as 1. For negative, invert x and make n positive. Result starts 1 for multiply accumulation.

2. Loop Processing: Square and Multiply on Bits

Core while halves n:

    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
Enter fullscreen mode Exit fullscreen mode

If n odd (LSB 1), multiply result by x. Always square x, halve n. For x=2 n=5 (101b): result*2 (bit1), square to 4, n=2; square to 16, n=1; result*16 (bit1), n=0 → 32. O(log n) steps.

3. Main Interactive: Float Base and Int Expo Input

Script prompts x/n, computes:

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

value = fast_power(base, exponent)
print(f"{base}^{exponent} = {value}")
Enter fullscreen mode Exit fullscreen mode

Float base for decimals, int expo. Simple, assumes valid.

🎯 Summary and Reflections

This binary expo halves work for fast powers. It reinforced:

  • Bit check for multiply: n%2 for LSB.
  • Square always: x*=x halves problem.
  • Negative invert: Simple reciprocal.

Reflections: Modular version (x^n mod m) key for crypto (RSA). Handles large n without overflow via Python bigints.

Advanced Alternatives: Recursive: if n even (x^{n/2})^2 else x*(x^{n-1}). Matrix for Fibonacci. Your expo trick? Share!

🚀 Next Steps and Resources

Day 76 powered math efficiently. In #80DaysOfChallenges? Modular? Post!

Top comments (0)