In C++, you will write code to empirically compare the performance of a naive an
ID: 2246877 • Letter: I
Question
In C++, you will write code to empirically compare the performance of a naive and a fast 2 × 2 matrix exponentiation method. The naive matrix exponentiation method consists of successive computation of matrix products: mn = Qn i=1 m = m × m × m × · · · × m | {z } n times . The fast matrix exponentiation algorithm involves successive squaring.
Sample Run:
Enter the top-left, top-right, bottom-left and bottom-right entries of the first matrix: 52 45 87 95 'Enter the top-left, top-right, bottom-left and bottom-right entries of the second matrix: 452 789 654 123
m1 = [[52, 45], [87, 95]]
m2 = [[452, 789], [654, 123]]
(m1 - m2)(m1 + m2) = ........
|(m1 - m2)(m1 + m2)| = ........
Which Fibonacci number do you wish to compute? 250 Fib(250) = ........
Empirical Analysis of Naive vs Fast Matrix Exponentiation in Generating 19 Terms of the Fibonacci Sequence
Explanation / Answer
Hi..
// C++ program to find value of f(n) where f(n)
// is defined as
// F(n) = F(n-1) + F(n-2) + F(n-3), n >= 3
// Base Cases :
// F(0) = 0, F(1) = 1, F(2) = 1
#include<bits/stdc++.h>
using namespace std;
// A utility function to multiply two matrices
// a[][] and b[][]. MultipicaResult result is
// stored back in b[][]
void multiply(int a[3][3], int b[3][3])
{
// Creating an auxiliary matrix to store elements
// of the MultipicaResult matrix
int mul[3][3];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
mul[i][j] = 0;
for (int k = 0; k < 3; k++)
mul[i][j] += a[i][k]*b[k][j];
}
}
// storing the muliplication resul in a[][]
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
a[i][j] = mul[i][j]; // Updating our matrix
}
// Function to compute F raise to power n-2.
int power(int F[3][3], int n)
{
int M[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}};
// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1
if (n==1)
return F[0][0] + F[0][1];
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1
return F[0][0] + F[0][1] ;
}
// Return n'th term of a series defined using below
// recurrence relation.
// f(n) is defined as
// f(n) = f(n-1) + f(n-2) + f(n-3), n>=3
// Base Cases :
// f(0) = 0, f(1) = 1, f(2) = 1
int findNthTerm(int n)
{
int F[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}} ;
return power(F, n-2);
}
// Driver code
int main()
{
int n = 5;
cout << "F(5) is " << findNthTerm(n);
return 0;
thanks