# W5 Notes: Number Theory 3

[ToC]

## Binary Exponentiation: Non-modular and Modular

To exponentiate, i.e., to compute the power $base^{exponent}$ in C, C++ or Java, we usually use the builtin `pow(base, exponent)` function. This function's parameters `base`, `exponent` and the return are all of floating point types. That makes the function a bad candidate if we want our computation to be strictly restricted to integral types.

:::info
**Note:** When you can avoid using floating point types in favor of integral types for arithemtic operations, you should usually do so, because floating point types lose precision of value.
:::

The naive way to do the integral exponentiation would be to multiply $1$ with $base$ an $exponent$ number of times, making it a $O(exponent)$ computation. Obviously, this approach is not practical for large values of $exponent$.

Using the binary exponentiation (a.k.a exponentiation by repeated squaring) technique, we can accomplish the exponentiation in under $O(\log (exponent))$ multiplications.

## Explanation

You can conceptualize the binary exponentiation algorithm in two ways: as a [divide-and-conquer](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm) approach, or as a way of factoring out $base^{exponent}$ into several $base^{x_i}$ values where $x_i$ is a power of two and $\sum{x_i}=exponent$. However you imagine the algorithm's logic, the end results are essentially the same.

## Implementation

### Recursive

int power(int base, int expo) {
    if (expo == 0) return 1;
    int result = power(base, expo / 2);
    result *= result;
    if (expo % 2) result *= base;
    return result;
}

### Iterative

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

## Implementation: Modular Version