Question

Write a C++ program In this assignment you will complete the definition of two functions that implement the repeated squaring algorithm described in the Stamp textbook on pages 98-99. Note that your implementation should not use the pow() function, the powl() functions, or any other built-in exponentiation functions. program4-driver.cpp - This file contains a completed main() function that serves as the driver to parse the command line, pass the values to the powerModN() function, and print the result. Make no changes to this file. powerUtility.h - This file contains the function prototype for the powerModN() function. Make no changes to this file. student4.cpp - This file contains two stubbed-out functions. This is the file where you will put your source code additions.

What would you use instead of the pow() functions, or any other built-in exponentiation functions?

This is what I have so far.

#include <iostream>
#include <math.h>
#include <assert.h>
#include "powerUtility.h"

using namespace std;

// Function Prototypes
void displayUsageMessage(void);

// ##################################################################
int main(int argc, char *argv[])
{
long baseValue;
long exponentValue;
long modulusValue;
long result;

if (argc == 4)
{
baseValue = atoi(argv[1]);
exponentValue = atoi(argv[2]);
modulusValue = atoi(argv[3]);

result = powerModN(baseValue, exponentValue, modulusValue);

cout << endl;
cout << " " << baseValue << '^' << exponentValue << " mod "
<< modulusValue << " = " << result << endl;
cout << endl;

return 0;
} // End if

else
{
displayUsageMessage();
return 1;
} // End else

return 0;
} // End main

// ##################################################################
void displayUsageMessage(void)
{
cout << endl;
cout << "Usage: a.exe <base value> <exponent value> <modulus value>" << endl;
cout << endl;
} // End displayUsageMessage

#ifndef POWER_UTILITY_HEADER
#define POWER_UTILITY_HEADER

#endif // POWER_UTILITY_HEADER// Function Prototypeslong powerModN(long base, long exponent, long modulus);

#endif

#include "powerUtility.h"

#define MAX_BITS 1000

// Function Prototypes
void binary(long decimalValue, int bits[], int &bitCount);

// ##########################################################
// Implements the repeated squaring algorithm
long powerModN(long base, long exponent, long modulus)
{
int bits[MAX_BITS];
int bitCount;
long result = 0;

binary(exponent, bits, bitCount);

return result;
} // End powerModN

// ##########################################################
// Converts the exponent into its binary number representation
void binary(long decimalValue, int bits[], int &bitCount)
{

} // End binary

Answer 1

long powerModN(long base, long exponent, long modulus){
   int bits[MAX_BITS];
   int bitCount;   
   long result = 1; //Initial Result is 1 not 0
   binary(exponent, bits, bitCount);
   for(int i = 0;i<bitCount;i++){
       result = (result*result)%modulus; //repeated squaring
       if(bits[i])
       result = (result * base)%modulus;
   }
   return result;
}

void binary(long decimalValue, int bits[], int &bitCount){
   int count = 0;
   long temp = decimalValue;   
   while(temp){
       temp = temp/2; //finding the total number of bits
       count++;
   }
   bitCount = count;
   temp = decimalValue;
   while(temp){ //Finding the bit array
       bits[--count] = temp%2;
       temp = temp/2;
   }
}