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

Source: Dev.to

Fast Power Function Overview

Function Design: Negative Exponent and Base Cases

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

• If the current least‑significant bit of n is 1, multiply result by x.
• Always square x and halve n.
• Example: (x = 2, n = 5) (binary 101) → result = 32 after three iterations.

Main Interactive: Float Base and Integer Exponent Input

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

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

The script reads a floating‑point base and an integer exponent, computes the power using fast_power, and prints the result.

Summary and Reflections

• Bit check for multiply: n % 2 isolates the LSB.
• Always square: x *= x reduces the problem size each loop.
• Negative exponent handling: Simple reciprocal conversion.
• The same pattern extends to modular exponentiation (xⁿ mod m), a cornerstone of RSA and other cryptographic algorithms.
• Recursive alternatives exist (e.g., if n even: (x^{n/2})² else: x·x^{n‑1}), as do matrix‑based methods for Fibonacci numbers.

Next Steps and Resources

• Source Code for Challenge #76: scripts/binary_exponentiation.py
• Main Repository: 80-days-of-challenges
• Daily Updates: Twitter/X (@Shahrouzlogs)