Gfrktyl

It is my first use of classes in Python. I wanted to create something useful and try some new things as I learn this cool language: strategy pattern, testing with nanoseconds precision, curve/poly fitting, and making a graphic presentation. The budget was 150 lines of code: 50 for five Fibonacci number calculations, 50 for testing and checking the results, 50 for presentation. PyCharm was my mentor and strict format enforcer: 22 blank lines. I made it in 149
lines and then added one comment line. Could be a better “curve fit” and “poly fit” string formulas, but it will force me to go over 150 lines.

Here is what this program does:

1. Calculates Fibonacci numbers from 2 to 30 by five different methods. Tests if all methods produce the same results and keep the shortest runtime from 10 tries.


2. Plots all best times in nanoseconds at four subplots: regular axes, log Y, zoom to 30000 nSec, and zoom+ to 3000 nSec.


3. It uses curve_fit from scipy and polyfit from numpy to find the best parameters for math formulas describing the time complexity of these Fibonacci algorithms.

I was happy to see the recursion as (446 * 1.62 ** n) just after the first tests and bug fixing - that is a theoretical O(φ**n) or 1.6180339887…

Critique and suggestion on how to write a better code are welcome.

Should I put all import statement at the top?

Here is the code:

from abc import ABCMeta, abstractmethod

from cachetools import cached, TTLCache





class Fibonacci(metaclass=ABCMeta):  # Abstract prototype ######################

    def fibonacci(self, n):

        if isinstance(n, int) and n >= 0:

            return self._fibonacci(n) if n >= 2 else [0, 1][n]

        raise ValueError



    @abstractmethod

    def _fibonacci(self, n):

        pass





class FibonacciRecursion(Fibonacci):  # 1. Classic and also naive computation ##

    def _fibonacci(self, n):

        return self.fibonacci(n - 1) + self.fibonacci(n - 2)





class FibonacciCacheTools(Fibonacci):  # 2. The cache fixes bad algorithm choice

    cache = TTLCache(maxsize=1500, ttl=3600)



    @cached(cache)

    def _fibonacci(self, n):

        return self.fibonacci(n - 1) + self.fibonacci(n - 2)





class FibonacciAddition(Fibonacci):  # 3. It is O(n), not O(2**n) as before ####

    def _fibonacci(self, n):

        f0, f1 = 0, 1

        for _ in range(1, n):

            f0, f1 = f1, f0 + f1

        return f1





class FibonacciAdditionPlus(FibonacciAddition):  # 4. Exploiting the test: O(1)

    def __init__(self):

        self._n = 2

        self._f0 = 1

        self._f1 = 1



    def _fibonacci(self, n):

        if n == self._n:

            return self._f1

        if n < self._n:

            self.__init__()

        for _ in range(self._n, n):

            self._f0, self._f1 = self._f1, self._f0 + self._f1

        self._n = n

        return self._f1





class FibonacciFormula(Fibonacci):  # 5. Formula of Binet, Moivre, and Bernoulli

    # Exact integer until Fibonacci(71)

    # Float error at Fibonacci(1475)  OverflowError: (34, 'Result too large')

    S5 = 5.0 ** 0.5  # Square root of 5



    def _fibonacci(self, n):

        phi = (1.0 + FibonacciFormula.S5) / 2.0  # φ Python speaks greek!

        psi = (1.0 - FibonacciFormula.S5) / 2.0  # ψ PyCharm doesn't like it ;-(

        return int((phi ** n - psi ** n) / FibonacciFormula.S5)





if __name__ == '__main__':  # Testing ... ######################################

    import platform

    import time

    import numpy as np

    import matplotlib.pyplot as plt

    from scipy.optimize import curve_fit



    def func1(x, a, b):  # function to fit exponential Fibonacci

        return '%f * %f**x' % (a, np.exp(b)) if x is None else a*np.exp(b*x)



    def func2(x, a, b, c):  # function to fit with cubic curve

        return '%f + %f*x + %f*x**2' % (a, b, c) if x is None else a+x*(b+c*x)



    def first_test(fibonacci_max, repeat):  # Collect times, curve fit, and plot

        methods = [  # Function to test, color, poly fit, curve fit

            [FibonacciRecursion(),    'blue',   2, func1],

            [FibonacciCacheTools(),   'orange', 1, func2],

            [FibonacciAddition(),     'green',  1, func2],

            [FibonacciAdditionPlus(), 'red',    1, func2],

            [FibonacciFormula(),      'purple', 1, func2],

        ]

        print('Number,Fibonacci,Times for all methods in nanoseconds')

        n_max = fibonacci_max - 1  # we start from n=2 (0, 1 - the same time)

        y = [[0 for _ in range(n_max)] for _ in methods]

        for j in range(n_max):  # Run tests and collect times in array y #######

            n = j + 2

            old = None

            for i, method in enumerate(methods):

                best = None

                for k in range(repeat):

                    start = time.perf_counter_ns()

                    result = method[0].fibonacci(n)

                    stop = time.perf_counter_ns()

                    duration = stop - start

                    if best is None or duration < best:

                        best = duration

                    if old is None:

                        old = result

                    elif result != old:

                        print(

                            'Error: different results %d and %d for function %s'

                            ' F(%d) in call # %d,' %

                            (old, result, method[0].fibonacci.__name__, n, k+1))

                        exit(1)

                if i == 0:

                    print(n, ',', old, sep='', end='')

                print(',', best, sep='', end='')

                y[i][j] = best

            print()

        plt.figure(1)  # Start plotting ########################################

        plt.suptitle('Time(n) Complexity of Fibonacci Algorithms. n = 2,3,...,'

                     '%d,%d' % (n_max, fibonacci_max))

        x = np.array([i + 2 for i in range(n_max)])

        plt.subplots_adjust(hspace=0.3)

        for i in range(4):

            plt.subplot(221 + i)

            for j, m in enumerate(methods):

                s = str(m[0].__class__.__name__)[len('Fibonacci'):]

                plt.plot(x, y[j], 'tab:' + m[1], label=s)

            plt.title(['time in nanoseconds', 'log(Time)', 'zoom', 'zoom+'][i])

            plt.grid(True)

            if i == 0:

                plt.legend()

            elif i == 1:

                plt.semilogy()

            else:

                x_min, x_max, _, _ = plt.axis()

                plt.axis([x_min, x_max, 0.0, 30000.0 if i == 2 else 3000.0])

        for i, m in enumerate(methods):  # Curve and poly fitting ##############

            plt.figure(2 + i)

            name = str(m[0].__class__.__name__)[len('Fibonacci'):]

            plt.plot(x, y[i], 'ko', label=name)

            c, _ = curve_fit(m[3], x, y[i])

            c_name = 'curve fit:' + m[3](None, *c)

            plt.plot(x, m[3](x, *c), 'y-', label=c_name)

            p = np.poly1d(np.polyfit(x, y[i], m[2]))

            p_name = 'poly fit: ' + str(p)

            plt.plot(x, p(x), m[1], label=p_name)

            plt.legend()

            print('%sn%sn%sn' % (name, c_name, p_name))

        plt.show()



    print('Python version  :', platform.python_version())

    print('       build    :', platform.python_build())

    print('       compiler :n', platform.python_compiler())

    first_test(fibonacci_max=30, repeat=10)

The output:

$ python fibonacci.py

Python version  : 3.7.3

       build    : ('v3.7.3:ef4ec6ed12', 'Mar 25 2019 16:52:21')

       compiler :

 Clang 6.0 (clang-600.0.57)

Number,Fibonacci,Times for all methods in nanoseconds

2,1,1027,2598,731,526,874

3,2,1638,2516,769,523,956

4,3,2818,2470,806,532,904

5,5,4592,2413,840,526,902

6,8,7571,2531,936,562,955

7,13,12376,2490,909,538,999

8,21,20528,2588,972,551,973

9,34,33349,2628,1074,581,1037

10,55,60107,2782,1116,581,997

11,89,85465,2421,1056,534,939

12,144,137395,2429,1101,534,942

13,233,222623,2411,1136,539,955

14,377,360054,2476,1216,551,938

15,610,600066,2736,1332,563,1006

16,987,971239,2529,1323,541,937

17,1597,1575092,2479,1359,552,937

18,2584,2565900,2632,1464,563,962

19,4181,4071666,2583,1485,555,953

20,6765,6630634,2503,1481,532,914

21,10946,10843455,2527,1571,522,930

22,17711,18277770,2617,1646,548,952

23,28657,28838223,2620,1739,573,967

24,46368,47167582,2481,1713,543,932

25,75025,77326177,2481,1709,531,909

26,121393,126154837,2587,1799,546,944

27,196418,205083621,2527,1857,548,942

28,317811,329818895,2444,1822,531,952

29,514229,533409650,2493,1932,551,946

30,832040,866064386,2509,1967,553,947

Recursion

curve fit:448.753271 * 1.619991**x

poly fit:            2

1.751e+06 x - 4.225e+07 x + 1.829e+08



CacheTools

curve fit:2492.458456 + 7.778994*x + -0.252776*x**2

poly fit:  

-0.3099 x + 2539



Addition

curve fit:636.162562 + 42.475661*x + 0.074421*x**2

poly fit:  

44.86 x + 622.3



AdditionPlus

curve fit:528.372414 + 2.642894*x + -0.076063*x**2

poly fit:  

0.2089 x + 542.5



Formula

curve fit:920.230213 + 5.076194*x + -0.163003*x**2

poly fit:  

-0.1399 x + 950.5

Graphics: