Write a program in C++ that reads the integer n (n should be larger than 8) and

Question

Write a program in C++ that reads the integer n (n should be larger than 8) and measures the maximum number of modulus operations to compute the gcd of two integers in the range 8 to n. Your program must print out the following data: (1) at each i from 8 until n, print the combination of two integers a, b within 1 through i, that incurs the maximum number of modulus operations. In other words: for every b between 8 and 15, there will be a set of corresponding a's going between 1 and b. (2) the gcd of these two integers a and b; and (3) the modulus operations to obtain this gcd of a and b (a and b are going to be every combination of two integers up until I, then you will print the combination of two integers that took the most amount of modulus operations) For example, if n=15; then you have to print out the followings: ======================================================== At i=8; gcd (5,8) = 1 took 4 modulus operations At i=9; gcd (5,8) = 1 took 4 modulus operations At i=10; gcd (5,8) = 1 took 4 modulus operations At i=11; gcd (5,8) = 1 took 4 modulus operations At i=12; gcd (5,8) = 1 took 4 modulus operations At i=13; gcd (8, 13) = 1 took 5 modulus operations At i=14; gcd (8, 13) = 1 took 5 modulus operations At i=15; gcd (8, 13) = 1 took 5 modulus operations ======================================================== Plot the maximum number of modulus operations as increasing n from 8 to 3,000 in a graph. You don't have to plot such number every increment of n. Choose an appropriate increment of n to view the growth of modulus operations. Plot log3/22n/3 in the same graph and compare your empirical data with this worse-case function. Are your empirical outputs always below this Big-O? Use the following formula to compute log3/22n/3: logaB = log10B / log10a If you don't have a calculator that computes log10, use the linux calculator. Part 2 Measure the total running time of your program itself. For this purpose, you should use the following linux system function: #include int gettimeofday( struct timeval *tv, struct timezone *tz ); The second argument to this function must be NULL. To understand the usage of this function, type man gettimeofday from the linux shell prompt. Estimate the Big-O of your program using plots: record the actual growth time of your program with increasing n, and define it as T(n), i.e., time your program. In other words, time and collect the data for each i, for example: At i=14; gcd (8, 13) = 1 took 5 modulus operations time = 7ms where the i is going to be the x-axis, and the time the y-axis. Then, using the table and plots like the ones in the following picture Estimate the Big-Oh function of T(n) Define the estimated Big-O function as F(n). Verify your estimation is correct by showing T(n)/F(n) is (or nearly) constant, i.e., T(n)/F(n) <= c, where c is a constant.

Explanation / Answer

#include <iostream>
using namespace std;
#include<bits/stdc++.h>

int number_of_computations(int a, int b){
//function to compute number of modulus operations
// for finding gcd of two numbers
int ans = 0;
int c;

if(a < b){
int temp = a;
a = b;
b = temp;

}

while(a > 0 && b > 0){

int c = a%b;
ans +=1;

if(c == 0){
// cout << "gcd is " << b << endl;

}

a = b;
b = c;
}
  
return ans;
}

int find_maximum_number_of_modulus_operations(int n)
{

int maximum = INT_MIN;
for (int i = 8; i <= n; ++i)
{
for (int j = 1; j <= 8 ; ++j)
{
//cout << j << " " << i << " " << number_of_computations(j,i) << endl;
maximum = max(maximum, number_of_computations(j,i));
}
}

cout << maximum << " for n = " << n << endl;

// cout << number_of_computations(8 ,13 ) << endl;
//cout << number_of_computations(16 , 2) << endl;

return maximum;
}

int main()
{
  
for (int i = 8; i < 16; ++i)
{
//cout << "-------------------- " << i << endl;
find_maximum_number_of_modulus_operations(i);
//cout << endl;
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.