from math import ceil, log
import time
import random
import numpy as np
import matplotlib.pyplot as plt

def add(A, B):
    A = np.asarray(A)
    B = np.asarray(B)
    return A + B

def subtract(A, B):
    A = np.asarray(A)
    B = np.asarray(B)
    return A - B

def joinQuadrants(q11,q12,q21,q22):
    top = np.concatenate((q11, q12), axis=1)
    bottom = np.concatenate((q21, q22), axis=1)
    joinedMatrix = np.concatenate((top, bottom), axis=0)

    return joinedMatrix


def strassen_matrix_multiply(A, B):
    n = len(A)

    if n <= 2:
        return classic_matrix_multiply(A, B)
    else:
        mid = n // 2

        a11 = A[0:mid, 0:mid]
        a12 = A[mid:n, 0:mid]
        a21 = A[0:mid, mid:n]
        a22 = A[mid:n, mid:n]

        b11 = B[0:mid, 0:mid]
        b12 = B[mid:n, 0:mid]
        b21 = B[0:mid, mid:n]
        b22 = B[mid:n, mid:n]

        m1 = strassen_matrix_multiply(add(a11, a22), add(b11, b22))
        m2 = strassen_matrix_multiply(add(a21, a22), b11)
        m3 = strassen_matrix_multiply(a11, subtract(b12, b22))
        m4 = strassen_matrix_multiply(a22, subtract(b21, b11))
        m5 = strassen_matrix_multiply(add(a11, a12), b22)
        m6 = strassen_matrix_multiply(subtract(a21, a11), add(b11, b12))
        m7 = strassen_matrix_multiply(subtract(a12, a22), add(b21, b22))

        c12 = add(m3, m5)
        c21 = add(m2, m4)
        c11 = subtract(add(add(m1, m4), m7), m5)
        c22 = subtract(add(add(m1, m3), m6), m2)

        C = joinQuadrants(c11,c12,c21,c22)

        return C

def classic_matrix_multiply(A, B):
    C = [[0 for row in range(len(A))] for col in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                C[i][j] += A[i][k] * B[k][i]
    return C

def randomMatrix(n):
    return np.random.randint(100, size=(n, n))

def measure_time(n_values):
    strassen_times = []
    standard_times = []    
    for n in n_values:
        A = randomMatrix(n)
        B = randomMatrix(n)
        # Вимірюємо час для алгоритму Штрассена-Вінограда
        start_time = time.time()
        strassen_matrix_multiply(A, B)
        strassen_time = time.time() - start_time
        strassen_times.append(strassen_time)


        # Вимірюємо час для стандартного алгоритму множення
        start_time = time.time()
        classic_matrix_multiply(A, B)
        standard_time = time.time() - start_time
        standard_times.append(standard_time)

    return strassen_times, standard_times

# Число рядків матриць: 4, 16, 64, 256, 1024, 4096
n_values = [4, 16, 16, 64, 256, 1024, 4096]

strassen_times, standard_times = measure_time(n_values)

# Вивести результати у вигляді таблиці)
print("Розмір матриці (n) | Час виконання (с) (Strassen) | Час виконання (с) (Standard)")
print("-" * 65)
for i, n in enumerate(n_values):
  print(f"{n:<19} | {strassen_times[i]:<28.6f} | {standard_times[i]:.6f}")


# Побудова графіків
plt.figure(figsize=(10, 6))
plt.xscale('log', base=2)
plt.yscale('log', base=2)
plt.plot(n_values, strassen_times, label='Strassen Algorithm')
plt.plot(n_values, standard_times, label='Standard Algorithm')
plt.xlabel('log2(n) - Розмір матриці (n)')
plt.ylabel('log2(T(n)) - Час виконання (с)')
plt.legend()
plt.title('Порівняння алгоритмів множення матриць')
plt.grid(True)

# Відображення графіку
plt.show()