modular_exponentiation.cpp File Reference

C++ Program for Modular Exponentiation Iteratively. More...

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for modular_exponentiation.cpp:

Go to the source code of this file.

Namespaces
namespace	math
	for assert

Functions
uint64_t	math::power (uint64_t a, uint64_t b, uint64_t c)
	This function calculates a raised to exponent b under modulo c using modular exponentiation.
static void	test ()
int	main ()
	Main function.

Detailed Description

C++ Program for Modular Exponentiation Iteratively.

The task is to calculate the value of an integer a raised to an integer exponent b under modulo c.

Note

The time complexity of this approach is O(log b).

Example: (4^3) % 5 (where ^ stands for exponentiation and % for modulo) (4*4*4) % 5 (4 % 5) * ( (4*4) % 5 ) 4 * (16 % 5) 4 * 1 4 We can also verify the result as 4^3 is 64 and 64 modulo 5 is 4

Author

Shri2206

Definition in file modular_exponentiation.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 86 of file modular_exponentiation.cpp.

           {
    test();  // execute the tests
    return 0;
}

test()

static void test ( )

static

Function for testing power function. test cases and assert statement.

Returns

void

Definition at line 60 of file modular_exponentiation.cpp.

                   {
    uint32_t test_case_1 = math::power(2, 5, 13);
    assert(test_case_1 == 6);
    std::cout << "Test 1 Passed!" << std::endl;
 
    uint32_t test_case_2 = math::power(14, 7, 15);
    assert(test_case_2 == 14);
    std::cout << "Test 2 Passed!" << std::endl;
 
    uint64_t test_case_3 = math::power(8, 15, 41);
    assert(test_case_3 == 32);
    std::cout << "Test 3 Passed!" << std::endl;
 
    uint64_t test_case_4 = math::power(27, 2, 5);
    assert(test_case_4 == 4);
    std::cout << "Test 4 Passed!" << std::endl;
 
    uint16_t test_case_5 = math::power(7, 3, 6);
    assert(test_case_5 == 1);
    std::cout << "Test 5 Passed!" << std::endl;
}