from __future__ import division
import matplotlib.pyplot as plt
import numpy as np

strassen_leaf=2

def naive_algorithm_performance(n):
	multiplication=n**3
	return multiplication

def strassen_performance(n,strassen_leaf):
	multiplication=1
	check=n/2
	while (check >= strassen_leaf):
		multiplication=multiplication*7
		check=check/2
	if(n!=2):
		multiplication=multiplication*strassen_leaf**3
	return multiplication


print "Scalar multiplication with Strassen: "+str(strassen_performance(16,strassen_leaf))
print "Scalar multiplication with Naive: "+str(naive_algorithm_performance(13))


x0 = np.linspace(2, 32, 31)
x1 = [4,8,16,32]
y0=[]
y1=[]
for el1 in x1:
	y1=y1 +[strassen_performance(el1,strassen_leaf)]

for el0 in x0:
	y0=y0 +[naive_algorithm_performance(el0)]


plt.scatter(x0, y0,color='red', label='Naive Method')
plt.scatter(x1, y1,color='blue', label='Strassen, Leaf=2')
plt.yscale('log')
plt.ylabel('Number of scalar multiplication')
plt.xlabel('Dimension of Square Matrices')
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.grid()
#plt.xticks(np.arange(2, 33, step=1))
plt.savefig('samplefigure.pdf', bbox_inches='tight')
plt.show()