HW 1.1 Fibanocci Numbers

• In mathematics, the Fibonacci numbers, commonly denoted F(n), form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
  • F(0) = 0, F(1)= 1 and F(n) = F(n-1) + F(n-2_ for n>1.
• The beginning of the sequence is thus: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
• For more details, see https://www.mathsisfun.com/numbers/fibonacci-sequence.html

Fill in your codes at the places marked xxx

Algorithm A: Iterative Approach in Linear Time

• Use a iterative for-loop to compute the Fibonacci numbers with the following formula
  • F(0) = 0, F(1)= 1 and F(n) = F(n-1) + F(n-2_ for n>1.
• The pseudo code is provided below
• Your program should also count the number of operations (additions) used
• The number of operations used should be O(n) for computing F(n)

def fib_linear(n): F[0] = 0;
F[1] = 1; for i = 2 to n F[i] = F[i-1] + F[i-2]; # F[2]=1, F[3]= 2, F[4]=3, …. Return F[n];

In [9]:

# xxx you may add more function codes here

def fib_linear(n):

    """Compute by iteration the n_th term of Fibonacci sequence in linear Time

    input: integer n >=0

    output: 

            fibn :  the n_th term of Fibinacci sequence

            count:  number of the integer additions used.

    """

    count = 0

    fibn = 0

    # xxx fill in the codes below

    def fibonacci(n):

    return fibn , count

  File "<ipython-input-9-ab81bab06da4>", line 18
    return (0,0)
    ^
IndentationError: expected an indented block

Approach B: Recursive Matrix Approach in Logarithmic Time

• See details at https://mathworld.wolfram.com/FibonacciQ-Matrix.html

First, define 

Q = |F(2) F(1)|  =   | 1 1 |

    |F(1) F(0)|      | 1 0 |

Q^n  =  Q^(n-1) * Q

Q^n  = |F(n+1) F(n)  |  =   |F(n)   F(n-1) |  *  | 1 1 | =( | 1 1 | )**n

       |F(n)   F(n-1)|      |F(n-1) F(n-2) |     | 1 0 |    | 1 0 | 

Then, we can compute Q^n in T(n)=O(log n) time with the pseudocode below. 

Note that

    * F(n) is actully equal to (Q^n) [0][1]

    * the code does not work when n==0

    * your code should also count the number of operations (matrx multiplications) used

def pow (Q, n):           # T(n): total number of matrix multiplications used

    """compute Q^n         with O( log n) matrix multiplication

    """

    if n==1:

        return Q

x = pow (Q, n/2)      # T(n/2) matrix multiplications used

p = x * x;            # 1 more matrix multiplication used

if (n % 2): 

return p*Q;       # 1 more matrix multiplication used

else:

return p;

In [7]:

def pow (Q, n):           # T(n): total number of matrix multiplications used

    if n==1:

        return Q, 0

    x, count = pow (Q, n//2)     # T(n/2) matrix multiplications used

    p = x * x;            # 1 more matrix multiplication used

    count +=1

    if (n % 2): 

        count +=1

        return p*Q, count;       # 1 more matrix multiplication used

    else:

        return p, count;

pow (2,16)     # 2^16  = (2^8)^2  = ((2^4)^2)^2 = (((2^2)^2)^2 )^2

Out[7]:

(65536, 4)

In [55]:

# xxx you may add more function codes here

def fib_logrithm(n):

    """ Compute the n_th term of Fibinacci sequence in logarithmic time by recursive matrix-based approach.

    input: integer n >=0

    output: fibn = the n_th term of Fibinacci sequence

            count:  number of the maxtrix multiplication used.

    """

    fibn = 0

    count = 0

    # xxx fill in the code below

    return fibn, count

Testing and Grading

• Run the following testing code to test your work
• You gain 5 pt for passing each of the following testcases
• If the code does not use the specified algorithm, you would get zero credit.
• Total points = 30

In [56]:

import unittest

class MyTest(unittest.TestCase):

    def encode (s):

        s = str (s)

        return sum ( [ord(x) for x in s if x!=" "])

    @staticmethod

    def foo (n,*code):

        name = ["additions", "multiplications"]

        for i, f in enumerate([fib_linear,fib_logrithm]):

            x, count = f(n)

            s="{:}({})".format(f.__name__, n)

            s="{:20} = {}n".format(s, x)

            s += "Number of {} = {}".format(name[i], count )

            y = MyTest.encode( x+count )

            print (s, "n")

            if y==code[i]:

                print ("passed testcase!")

            else: 

                print ("failed testcase!")

        print ()

    def test_case1(self):

        MyTest.foo (0, 48, 48)

    def test_case2(self):

        MyTest.foo (1, 49, 49) 

    def test_case3(self):

        MyTest.foo (10, 106, 110) 

    def test_case4(self):

        # MyTest.foo (55, 634, 634)  # xxx typo here, correction below

        MyTest.foo (55, 643, 634)  # xxx corrected!

    def test_case5(self):

        MyTest.foo (100, 1101,1100)

    def test_case6(self):

        MyTest.foo (1000, 11037, 11042)

unittest.main(argv=[''], verbosity=0, exit=False);

. . .

Expected outputs

fib_linear(0)        = 0

Number of additions = 0 

passed testcase!

fib_logrithm(0)      = 0

Number of multiplications = 0 

passed testcase!

fib_linear(1)        = 1

Number of additions = 0 

passed testcase!

fib_logrithm(1)      = 1

Number of multiplications = 0 

passed testcase!

fib_linear(10)       = 55

Number of additions = 9 

passed testcase!

fib_logrithm(10)     = 55

Number of multiplications = 4 

passed testcase!

fib_linear(55)       = 139583862445

Number of additions = 54 

passed testcase!

fib_logrithm(55)     = 139583862445

Number of multiplications = 9 

passed testcase!

fib_linear(100)      = 354224848179261915075

Number of additions = 99 

passed testcase!

fib_logrithm(100)    = 354224848179261915075

Number of multiplications = 8 

passed testcase!

fib_linear(1000)     = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Number of additions = 999 

passed testcase!

fib_logrithm(1000)   = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Number of multiplications = 14 

passed testcase!

In [ ]:

In [ ]: