Consider the MATLAB function fib(). Modify this function using MATLAB’s built-in timeit() function such that fib() also returns the average runtime of the nested function getFib() inside fib(), right after giving the requested Fibonacci number. For example, here is an output from such modified code,

fib

Please enter a non-negative integer or type stop: 10
fib(10) = 55
average runtime: 1.0083e-05 seconds
Please enter a non-negative integer or type stop: 15
fib(15) = 610
average runtime: 8.8884e-05 seconds
Please enter a non-negative integer or type stop: 20
fib(20) = 6765
average runtime: 0.00095559 seconds
Please enter a non-negative integer or type stop: 25
fib(25) = 75025
average runtime: 0.010311 seconds
Please enter a non-negative integer or type stop: 30
fib(30) = 832040
average runtime: 0.11575 seconds
Please enter a non-negative integer or type stop: 35
fib(35) = 9227465
average runtime: 1.2904 seconds
Please enter a non-negative integer or type stop: stop


Now copy this function to a new MATLAB M-file named fibLoop.m. Also modify the name of the function fib() in this file fibLoop(). Modify the nested function getFib() inside of fibLoop() such that instead of recursive function calls, it uses a for-loop to find the requested Fibonacci number.

Now time your new function fibLoop() for the same input integers as in the above example: $10,15,20,25,30,35$. How do the runtimes for fibLoop() compare with fib(). Which function is faster and more efficient: fib() or fibLoop()? Why is there such huge difference in the performance of the two functions?

Write two new MATLAB functions timeFib(n) and timeFibLoop(n) based on your MATLAB functions fib() and fibLoop(), such that both take an integer and output a structure whose fields are,

output.n
output.fib
output.runtime


Note that the function should take as input only an integer variable, so you need to modify your old codes to only check whether the input ~ischar(), and isreal() and n>=0 and round(n)==n. Here is an example output from the two functions,

timeFib(20)

ans =
n: 20
fib: 6765
runtime: 9.6568e-04

timeFib('amir')

Error using timeFib (line 8)
The input argument is not a non-negative integer!

timeFibLoop(20)

ans =
n: 20
fib: 6765
runtime: 4.4076e-06

timeFibLoop('amir')

Error using timeFibLoop (line 8)
The input argument is not a non-negative integer!


Now write a script named writeFibResult.m that calls these two functions for a range of input $n={10,2,3,\ldots,35}$ values, and then write the output of these two functions in a formatted way in two files like these fibOutput.txt and fibLoopOutput.txt. You can use any of MATLAB IO methods to create the output file with any file extension you prefer: .txt, .csv, .xlsx, .tab, … .

Here is an implementation of the modified fib() and fibLoop(),

function fibModified()

n = input('Please enter a non-negative integer or type stop: ','s');
if strcmp(n,'stop')
return
else
n = str2double(n);
if isreal(n)
if n>=0 && round(n)==n
disp([char(9), 'fib(',num2str(n),') = ',num2str(getFib(n))]);
runtime = timeit( @()getFib(n) );
disp([char(9), 'average runtime: ',num2str(runtime), ' seconds']);
fib()
return
end
end
disp('The input argument is not a non-negative integer!');
fib()
end

function fib = getFib(n_int)
if n_int == 0
fib = 0;
elseif n_int == 1
fib = 1;
else
fib = getFib(n_int-1) + getFib(n_int-2);
end
end

end

function fibLoop()

n = input('Please enter a non-negative integer or type stop: ','s');
if strcmp(n,'stop')
return
else
n = str2double(n);
if isreal(n)
if n>=0 && round(n)==n
disp([char(9),'fib(',num2str(n),') = ',num2str(getFib(n))]);
runtime = timeit( @()getFib(n) );
disp([char(9),'average runtime: ',num2str(runtime), ' seconds']);
fibLoop()
return
end
end
disp('The input argument is not a non-negative integer!');
fibLoop()
end

function fib = getFib(n_int)
if n_int == 0
fib = 0;
elseif n_int == 1
fib = 1;
else
fibSeq = zeros(n_int+1,1);
fibSeq(1) = 0;
fibSeq(2) = 1;
for iseq = 3:n_int+1
fibSeq(iseq) = fibSeq(iseq-1) + fibSeq(iseq-2);
end
fib = fibSeq(n_int+1);
end
end

end

fibLoop

Please enter a non-negative integer or type stop: 12
fib(12) = 144
average runtime: 4.3496e-06 seconds
Please enter a non-negative integer or type stop: 10
fib(10) = 55
average runtime: 4.5323e-06 seconds
Please enter a non-negative integer or type stop: 15
fib(15) = 610
average runtime: 4.5232e-06 seconds
Please enter a non-negative integer or type stop: 20
fib(20) = 6765
average runtime: 4.6357e-06 seconds
Please enter a non-negative integer or type stop: 25
fib(25) = 75025
average runtime: 4.6562e-06 seconds
Please enter a non-negative integer or type stop: 30
fib(30) = 832040
average runtime: 4.7624e-06 seconds
Please enter a non-negative integer or type stop: 35
fib(35) = 9227465
average runtime: 4.7889e-06 seconds
Please enter a non-negative integer or type stop: stop


As you see, the for-loop version of the function fibLoop() is far faster than the recursive function version fib(). The reason is that the recursive version is not well written and does a lot of redundant calculations. Ask me directly to explain to you why there is such a huge redundancy in this function calculations.

Here the two functions timeFib.m and timeFibLoop.m, and here is the script writeFibResult.m that creates the requested output file in the problem.

function output = timeFib(n)

if ~ischar(n) && isreal(n) && n>=0 && round(n)==n
output.n = n;
output.fib = getFib(n);
output.runtime = timeit( @()getFib(n) );
else
error('The input argument is not a non-negative integer!');
return
end

function fib = getFib(n_int)
if n_int == 0
fib = 0;
elseif n_int == 1
fib = 1;
else
fib = getFib(n_int-1) + getFib(n_int-2);
end
end

end

function output = timeFibLoop(n)

if ~ischar(n) && isreal(n) && n>=0 && round(n)==n
output.n = n;
output.fib = getFib(n);
output.runtime = timeit( @()getFib(n) );
else
error('The input argument is not a non-negative integer!');
return
end

function fib = getFib(n_int)
if n_int == 0
fib = 0;
elseif n_int == 1
fib = 1;
else
fibSeq = zeros(n_int+1,1);
fibSeq(1) = 0;
fibSeq(2) = 1;
for iseq = 3:n_int+1
fibSeq(iseq) = fibSeq(iseq-1) + fibSeq(iseq-2);
end
fib = fibSeq(n_int+1);
end
end

end


Consider the Python function fib(). Modify this function using process_time() from Python’s time module such that fib() also returns the average runtime of the nested function getFib() inside fib(), right after giving the requested Fibonacci number. For example, here is an output from such modified code,

fib()

Please enter a non-negative integer or type stop: 0
fib(0) = 0
average runtime: 0.015625 seconds
Please enter a non-negative integer or type stop: 1
fib(1) = 1
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 2
fib(2) = 1
average runtime: 0.046875 seconds
Please enter a non-negative integer or type stop: 3
fib(3) = 2
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 4
fib(4) = 3
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 8
fib(8) = 21
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 10
fib(10) = 55
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 15
fib(15) = 610
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 20
fib(20) = 6765
average runtime: 0.046875 seconds
Please enter a non-negative integer or type stop: 25
fib(25) = 75025
average runtime: 0.078125 seconds
Please enter a non-negative integer or type stop: 30
fib(30) = 832040
average runtime: 0.484375 seconds
Please enter a non-negative integer or type stop: 35
fib(35) = 9227465
average runtime: 4.703125 seconds


Now copy this function to a new Python file named fibLoop.py. Also modify the name of the function fib() in this file fibLoop(). Modify the nested function getFib() inside of fibLoop() such that instead of recursive function calls, it uses a for-loop to find the requested Fibonacci number.

Now time your new function fibLoop() for the same input integers as in the above example: $10,15,20,25,30,35$. How do the runtimes for fibLoop() compare with fib(). Which function is faster and more efficient: fib() or fibLoop()? Why is there such huge difference in the performance of the two functions?

Here is an implementation of the modified fib() and fibLoop(),

import time

def fib():

def getFib(n_int):
if n_int > 1:
fib = getFib(n_int-1) + getFib(n_int-2);
elif n_int == 1:
fib = 1
else:
fib = 0
return fib

n = input('Please enter a non-negative integer or type stop: ')
if n=="stop":
return None
else:
n = int(n);
tstart = time.process_time()
print( "fib({}) = {}".format(n,getFib(n)) );
tend = time.process_time()
print( "average runtime: {} seconds".format(tend-tstart) );
fib()
return None

import time
import numpy as np

def fibLoop():

def getFib(n_int):
if n_int > 1:
FibSeq = np.zeros(n_int+1)
FibSeq = 0;
FibSeq = 1;
for iseq in range(2,n_int+1):
FibSeq[iseq] = FibSeq[iseq-1] + FibSeq[iseq-2];
fib = FibSeq[n_int]
elif n_int == 1:
fib = 1
else:
fib = 0
return int(fib)

n = input('Please enter a non-negative integer or type stop: ')
if n=="stop":
return None
else:
n = int(n);
tstart = time.process_time()
print( "fib({}) = {}".format(n,getFib(n)) );
tend = time.process_time()
print( "average runtime: {} seconds".format(tend-tstart) );
fibLoop()
return None

fibLoop()

Please enter a non-negative integer or type stop: 0
fib(0) = 0
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 1
fib(1) = 1
average runtime: 0.015625 seconds
Please enter a non-negative integer or type stop: 2
fib(2) = 1
average runtime: 0.0 seconds
Please enter a non-negative integer or type stop: 3
fib(3) = 2
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 4
fib(4) = 3
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 8
fib(8) = 21
average runtime: 0.0 seconds
Please enter a non-negative integer or type stop: 10
fib(10) = 55
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 15
fib(15) = 610
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 20
fib(20) = 6765
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 25
fib(25) = 75025
average runtime: 0.015625 seconds
Please enter a non-negative integer or type stop: 30
fib(30) = 832040
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: 35
fib(35) = 9227465
average runtime: 0.03125 seconds
Please enter a non-negative integer or type stop: stop


As you see, the for-loop version of the function fibLoop() is significantly faster than the recursive function version fib(). The reason is that the recursive version is not well written and does a lot of redundant calculations (for example, the two Fibonacci function calls inside the function fib() have a lot of duplicate computations that are avoided in the loop version of the function.