NO additional parameters for allowed.

PLEASE DO NOT use AI-generated sources.

C programming

#include "ex6q1.h" #define LEN 200000000 / / This function should be pure recursion - no dynamic programming allowed uint32_t exp_mod_1(uint32_t base, uint32_t exp, uint32_t modulo) { // This function should store the values of previous calls to exp_mod_2 in an / array and use them for later calculations. uint32_t exp_mod_2(uint32_t base, uint32_t exp, uint32_t modulo) { int main(void) { uint32_t base, exp, modulo; if (scanf ( "id id id", &base, &exp, &modulo) != 3) { return 1; uint32_t mod_1 = exp_mod_1 (base, exp, modulo) ; uint32_t mod_2 = exp_mod_2 (base, exp, modulo) ; fprintf(stdout, "exp_mod_1 calls: d\ ", EXP_MOD_1_CALL_COUNT) ; fprintf (stdout, "exp_mod_2 calls: :d\ ", EXP_MOD_2_CALL_COUNT) ; fprintf (stdout, ":d == :d\ ", mod_1, mod_2) ;Note that for both the example runs below, it's very likely the numbers of function calls made by your functions differ slightly from the shown results, due to different implementations in our solution. Your numbers should be on the same order of magnitude, though not necessarily exact. The remainder must be an exact match. Example input 1: 234 130 77 Example output 1: exp_mod_l calls: 259 exp_mod_2 calls: 25 67 == 67 Example input 2: 7 132343203 9 Example output 2: exp_mod_l calls: 264686405 exp_mod_2 calls: 105 1 == For input bounds, the base is positive and never exceeds 1000 . The exponent is non-negative and never exceeds 2 X 108 l (that's 1 less than 200 million). The modulo is positive and never exceeds 300. All inputs will be integers and you don't worry about handling invalid input. Use command gcc Wall std=c99 ex6ql.c to compile and test your program. You need to resolve any warning messages or notes during compilation, as always. H #ifndef LAB6_H 2 #define LAB6_H 3 #include 4 #include 6 int EXP_MOD_1_CALL_COUNT = 0; int EXP_MOD_2_CALL_COUNT = 0; 8 uint32_t exp_mod_1(uint32_t base, uint32_t exp, uint32_t modulo) ; 10 11 uint32_t exp_mod_2(uint32_t base, uint32_t exp, uint32_t modulo); 12 13 #endif 14Description Part 1: Program organization, recursive calls In this part, you'll implement both an inefficient and efficient implementations ofa common programming problem: modular exponentiation. Consider computing 7H132343203 % 9 (which is the remainder of "7 to the power of 132343203" divided bng I). The answer is 1, but running that in python on our lab machines takes about 4 minutes and 30 seconds! C can't even store the intermediary values. Instead, we can use recursion to make this computation under a second! We can immediately see that it's silly for us to compute 7H1323432o3 , when the answer is only 1. Instead we can be clever and geta much faster runtime. Recall that 7H7 == 7**(4+3) == 7H4 * 7H3 . Another point you may have seen in math is how the modulo operator distributes. For positive integers a, b,and c such that a == b * c we have a % d == ((b e d) * (c % d)) % d. When splitting our computations, it's most efficient to split them into as equal components as possible. So for 7H7 , we'd want to split the calculation into 7H4 and 7H3 not 7**6 and 7M1 , as the latter is linear time and the former is roughly logarithmic. Your task will be to write the definitions for two functions. Both functions will take 3 arguments and compute the modulo ofa base raised to a rather large power. The first function exp_mod_1 will do this via a brute-force recursion. You will need to count the number of times this function is called using the external variable EXP_MOD_1_CALL_COUNT . You'll need both the return value of this function and the number of calls in the final output. The second function exp_mod_2 must use a memoization approach (very similar to dynamic programming introduced in Lecture ll). This means every time the function is called, it should store the result of its computation in an array. That way, when the function is called again to make the same computation, it can immediately return the value it has already computed. You're provided with a header file ex6q1.h and some starting template code in ex6ql.c shown below. Do NOT modify the function prototypes for exp_mod_l and exp_mod_2, otherwise it won't compile when we're marking. Other than them, you can modify the program as required to meet the requirements, including declaring non-local variables