Wyznaczając złożoność obliczeniową otrzymujemy wynik czyli w przybliżeniu
Implementacja algorytmu w języku C /*------------------------------------------------------------------------------*/
/* Program kompilować bez konsolidacji */ /* Zakładając, że nazwa pliku to Strassen.c to przy użyciu gcc kompilacja powinna wyglądać: */ /* gcc -c Strassen.c */
#include <stdio.h> #include <stdlib.h>
void strassen(double **a, double **b, double **c, int tam); void sum(double **a, double **b, double **result, int tam); void subtract(double **a, double **b, double **result, int tam); double **allocate_real_matrix(int tam, int random); double **free_real_matrix(double **v, int tam);
void strassen(double **a, double **b, double **c, int tam) {
// najprostszy przypadek: kiedy macierz ma rozmiar 1 na 1: if (tam == 1) { c = a * b; return;
// pozostałe przypadki: else { int newTam = tam/2; double **a11, **a12, **a21, **a22; double **b11, **b12, **b21, **b22; double **c11, **c12, **c21, **c22; double **p1, **p2, **p3, **p4, **p5, **p6, **p7;
// alokacja pamięci: a11 = allocate_real_matrix(newTam, -1); a12 = allocate_real_matrix(newTam, -1); a21 = allocate_real_matrix(newTam, -1); a22 = allocate_real_matrix(newTam, -1);