Ttykuu

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: