crypto_camp_exercise_1

fast_exp.cpp

#include <iostream>
#include <optional>
#include <cassert>

/*
 *  Fast exponentiation using iterative binary exponentiation.
 *  This efficiently computes (base ^ exponent) % modulo (if provided) in O(log exponent) time.
 *  When modulo is provided, intermediate values stay small and avoid overflow.
 *  Without modulo, results can quickly exceed the storage limits of the int type.
    INT_MAX is typically 2,147,483,647 for 32-bit int.

    For example: fast_exponent(10, 10) = 10,000,000,000 > INT_MAX
    This will result in integer overflow and undefined behavior in C++.
*/
int fast_exponent(int base, int exponent, std::optional<int> modulo = std::nullopt)
{
    // Edge case: Any number to the power of 0 is 1.
    // Even with modulo, we return 1 % modulo (to respect modulo when provided).
    if (exponent == 0) return 1 % modulo.value_or(2);

    // Edge case: 0 raised to any positive exponent is 0.
    if (base == 0) return 0;

    // Result accumulator: starts at 1 because it's the multiplicative identity.
    int result = 1;

    // Current base: we will repeatedly square this value.
    int current_base = base;

    // Loop while exponent is not zero.
    // Each iteration processes one bit of the exponent.
    while (exponent > 0) {
        // If the current least significant bit (LSB) is 1, the exponent is odd.
        // We multiply the result by the current base.
        if (exponent & 1) {
            result *= current_base;

            // Apply modulo if provided, to prevent integer overflow.
            if (modulo) result %= modulo.value();
        }

        // Square the base for the next bit position.
        current_base = current_base * current_base;

        // Apply modulo if provided, to keep numbers small and avoid overflow.
        if (modulo) current_base %= modulo.value();

        // Move to the next higher bit by right-shifting the exponent.
        exponent >>= 1;
    }

    return result;
}

void run_tests() {
    // ================================
    // Test without modulo (results within int range)
    assert(fast_exponent(3, 218, 1000) == 489);
    assert(fast_exponent(2, 10) == 1024);
    assert(fast_exponent(3, 3) == 27);
    assert(fast_exponent(5, 0) == 1);
    assert(fast_exponent(0, 5) == 0);
    assert(fast_exponent(0, 0) == 1); 

    // Test with modulo
    assert(fast_exponent(3, 2, 4) == 1);
    assert(fast_exponent(2, 10, 1000) == 24); // 1024 % 1000 = 24
    assert(fast_exponent(7, 4, 5) == 1);      // 2401 % 5 = 1
    assert(fast_exponent(10, 0, 6) == 1 % 6); // Should be 1 % 6 = 1
    assert(fast_exponent(0, 5, 7) == 0);      // Base zero, should return 0

    std::cout << "All safe test cases passed!" << std::endl;
}

int main() {
    run_tests();
    return 0;
}