Strasse

#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stddef.h>
#include <time.h>

typedef struct Matrix{
    int ncolumns;
    int nrows;
    int **c;
} Matrix;

int randomazer (int min, int max){
    int random;
    random = rand();
    random = ((float)random / RAND_MAX)*(max-min)+min;
    return(random);
}

Matrix create (int n, int min, int max){
    Matrix A;
    int i=0,j=0;
    if (( A.c = malloc ( n * sizeof ( int *))) == NULL )
        exit (1);
    for (i = 0; i < n ; i++ ) {
        if (( A.c[i] = malloc ( n * sizeof ( int ))) == NULL )
            exit (2);
    }
    for (i = 0; i < n; i++){
        for ( j = 0; j < n; j++){
            A.c [i][j] = randomazer(min, max);
        }
    }
    A.nrows = n;
    A.ncolumns = n;
    return A;
}

Matrix sum (Matrix A, Matrix B){
    Matrix n;
    n = create (A.nrows, 0, 0);
    int i=0, j=0;
    for (i=0; i<A.nrows; i++){
        for ( j=0; j<A.ncolumns; j++){
            n.c[i][j]=A.c[i][j]+B.c[i][j];
        }
    }
    n.nrows;
    n.ncolumns;
    return n;
}

Matrix subtr (Matrix A, Matrix B){
    Matrix n;
    n = create (A.nrows, 0, 0);
    int i=0, j=0;
    for (i=0; i<A.nrows; i++){
        for ( j=0; j<A.ncolumns; j++){
            n.c[i][j]=A.c[i][j]-B.c[i][j];
        }
    }
    n.nrows;
    n.ncolumns;
    return n;
}

Matrix half1 (Matrix A){
    Matrix A11;
    int i, j;
    A11 = create (A.ncolumns/2, 0, 0);
    for (i = 0; i < A.ncolumns/2; i++){
        for (j = 0; j < A.ncolumns/2; j++){
            A11.c[i][j] = A.c[i][j];
        }
    }
    return A11;
}

Matrix half2 (Matrix A){
    Matrix A12;
    int i, j;
    A12 = create (A.ncolumns/2, 0, 0);
    for (i = 0; i < A.ncolumns/2; i++){
        for (j = 0; j < A.ncolumns/2; j++){
            A12.c[i][j] = A.c[i][j+A.ncolumns/2];
        }
    }
    return A12;
}

Matrix half3 (Matrix A){
    Matrix A21;
    int i, j;
    A21 = create (A.ncolumns/2, 0, 0);
    for (i = 0; i < A.ncolumns/2; i++){
        for (j = 0; j < A.ncolumns/2; j++){
            A21.c[i][j] = A.c[i+A.ncolumns/2][j];
        }
    }
    return A21;
}

Matrix half4 (Matrix A){
    Matrix A22;
    int i, j;
    A22 = create (A.ncolumns/2, 0, 0);
    for (i = 0; i < A.ncolumns/2; i++){
        for (j = 0; j < A.ncolumns/2; j++){
            A22.c[i][j] = A.c[i+A.ncolumns/2][j+A.ncolumns/2];
        }
    }
    return A22;
}

void output (Matrix A){
    int i=0, j=0;
    for (i=0; i<A.nrows; i++){
        for ( j=0; j<A.ncolumns; j++){
            printf ("%d ", A.c [i][j]);
        }
    printf (" \n" );
    }
    printf ("\n");
}

void delete_mass (Matrix A){
    int i=0;
    for (i = 0; i < A.nrows ; i++ )
    free(A.c[i]) ;
    free (A.c);
}

Matrix simple_multiply (Matrix A, Matrix B){
        Matrix c;
        c = create (A.ncolumns, 0, 0);
        c.c [0][0] = A.c [0][0] * B.c [0][0] + A.c [0][1] * B.c [1][0];
        c.c [1][0] = A.c [1][0] * B.c [0][0] + A.c [1][1] * B.c [1][0];
        c.c [0][1] = A.c [0][0] * B.c [0][1] + A.c [0][1] * B.c [1][1];
        c.c [1][1] = A.c [1][0] * B.c [0][1] + A.c [1][1] * B.c [1][1];
        return c;
}

Matrix connect (Matrix C11, Matrix C12, Matrix C21, Matrix C22){
    Matrix C;
    C = create (C11.ncolumns*2, 0, 0);
    int i, j;
    for (i = 0; i < C11.ncolumns; i++){
        for (j = 0; j < C11.ncolumns; j++){
            C.c[i][j] = C11.c[i][j];
        }
    }
    printf ("%d\n", C11.ncolumns/2);
    for (i = 0; i < C11.ncolumns; i++){
        for (j = C11.ncolumns; j < C.ncolumns; j++){
            C.c[i][j] = C12.c[i][j-C11.ncolumns];
        }
    }
    for (i = C11.ncolumns; i < C.ncolumns; i++){
        for (j = 0; j < C11.ncolumns; j++ ){
            C.c[i][j] = C21.c[i - C11.ncolumns][j];
        }
    }
    for (i = C11.ncolumns; i < C.ncolumns; i++){
        for (j = C11.ncolumns; j < C.ncolumns; j++ ){
            C.c[i][j] = C22.c[i-C11.ncolumns][j-C11.ncolumns];
        }
    }
    return C;
}

Matrix mult (Matrix A, Matrix B){
    if (A.ncolumns == 2){
        Matrix c;
        c = simple_multiply (A, B);
        return c;
    }
    else{
        Matrix A11;
        Matrix A12;
        Matrix A21;
        Matrix A22;
        Matrix B11;
        Matrix B12;
        Matrix B21;
        Matrix B22;
        A11 = half1 (A);
        A12 = half2 (A);
        A21 = half3 (A);
        A22 = half4 (A);
        B11 = half1 (B);
        B12 = half2 (B);
        B21 = half3 (B);
        B22 = half4 (B);
        Matrix P1;
        Matrix P2;
        Matrix P3;
        Matrix P4;
        Matrix P5;
        Matrix P6;
        Matrix P7;
        Matrix X1;
        Matrix X2;
        X1 = sum (A11, A22);
        X2 = sum (B11, B22);
        P1 = mult (X1, X2);
        delete_mass(X1);
        delete_mass(X2);
        Matrix X3;
        X3 = sum (A21, A22);
        P2 = mult (X3, B11);
        delete_mass(X3);
        Matrix X4;
        X4 = subtr (B12, B22);
        P3 = mult (A11, X4);
        delete_mass(X4);
        Matrix X5;
        X5 = subtr (B21, B11);
        P4 = mult (A22, X5);
        delete_mass(X5);
        Matrix X6;
        X6 = sum (A11, A12);
        P5 = mult (X6, B22);
        delete_mass(X6);
        Matrix X7;
        Matrix X8;
        X7 = subtr (A21, A11);
        X8 = sum (B11, B12);
        P6 = mult (X7, X8);
        delete_mass(X7);
        delete_mass(X8);
        Matrix X9;
        Matrix X10;
        X9 = subtr (A12, A22);
        X10 = sum (B21, B22);
        P7 = mult (X9, X10);
        Matrix C11;
        Matrix C12;
        Matrix C21;
        Matrix C22;
        Matrix C;
        Matrix tmp1;
        Matrix tmp2;
        Matrix tmp3;
        Matrix tmp4;
        tmp1 = sum (P1, P4);
        tmp2 = subtr (tmp1, P5);
        C11 = sum (tmp2, P7);
        C12 = sum (P3, P5);
        C21 = sum (P2, P4);
        tmp3 = subtr (P1, P2);
        tmp4 = sum (tmp3, P3);
        C22 = sum (tmp4, P6);
        delete_mass(tmp1);
        delete_mass(tmp2);
        delete_mass(tmp3);
        delete_mass(tmp4);

        C = connect (C11, C12, C21, C22);

        return C;
    }
}

int main (void) {
    srand(time(NULL));
    Matrix A;
    Matrix B;
    Matrix D;
    int n = 4;
    A = create (n, 0, 10);
    B = create (n, 0, 10);
    output (A);
    output (B);
    D = mult (A, B);
    output (D);

    return 0;
}