MATLAB

Problem Part MATLAB-A

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

Problem Part MATLAB-B

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.

Problem Part MATLAB-C

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?

Problem Part MATLAB-D

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! 

Problem Part MATLAB-E

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, … .

Solution Part MATLAB-A, B, C

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.

Solution Part MATLAB-D, E

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
Python

Problem Part Python-A

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

Problem Part Python-B

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.

Problem Part Python-C

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?

Solution Part Python-A, B, C

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] = 0;
            FibSeq[1] = 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.

Comments