main.cpp 3.27 KB
Newer Older
Mario Bajer's avatar
Mario Bajer committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include "matrix.h"
 
typedef pair<matrix, long> result;
 
int cut = 64;
 
matrix mult_std(matrix a, matrix b) {
        matrix c(a.dim(), false, false);
        for (int i = 0; i < a.dim(); i++)
                for (int k = 0; k < a.dim(); k++)
                        for (int j = 0; j < a.dim(); j++)
                                c(i,j) += a(i,k) * b(k,j);
       
        return c;
}
 
matrix get_part(int pi, int pj, matrix m) {
        matrix p(m.dim() / 2, false, true);
        pi = pi * p.dim();
        pj = pj * p.dim();
       
        for (int i = 0; i < p.dim(); i++)
                for (int j = 0; j < p.dim(); j++)
                        p(i,j) = m(i + pi,j + pj);
                       
        return p;
}
 
void set_part(int pi, int pj, matrix* m, matrix p) {
        pi = pi * p.dim();
        pj = pj * p.dim();
       
        for (int i = 0; i < p.dim(); i++)
                for (int j = 0; j < p.dim(); j++)
                        (*m)(i + pi,j + pj) = p(i,j);
}
 
matrix mult_strassen(matrix a, matrix b) {
        if (a.dim() <= cut)
                return mult_std(a, b);
 
        matrix a11 = get_part(0, 0, a);
        matrix a12 = get_part(0, 1, a);
        matrix a21 = get_part(1, 0, a);
        matrix a22 = get_part(1, 1, a);
       
        matrix b11 = get_part(0, 0, b);
        matrix b12 = get_part(0, 1, b);
        matrix b21 = get_part(1, 0, b);
        matrix b22 = get_part(1, 1, b);
       
        matrix m1 = mult_strassen(a11 + a22, b11 + b22);
        matrix m2 = mult_strassen(a21 + a22, b11);
        matrix m3 = mult_strassen(a11, b12 - b22);
        matrix m4 = mult_strassen(a22, b21 - b11);
        matrix m5 = mult_strassen(a11 + a12, b22);
        matrix m6 = mult_strassen(a21 - a11, b11 + b12);
        matrix m7 = mult_strassen(a12 - a22, b21 + b22);
       
        matrix c(a.dim(), false, true);
        set_part(0, 0, &c, m1 + m4 - m5 + m7);
        set_part(0, 1, &c, m3 + m5);
        set_part(1, 0, &c, m2 + m4);
        set_part(1, 1, &c, m1 - m2 + m3 + m6);
       
        return c;
}
 
pair<matrix, long> run(matrix (*f)(matrix, matrix), matrix a, matrix b) {
        struct timeval start, end;
       
        gettimeofday(&start, NULL);
        matrix c = f(a, b);
        gettimeofday(&end, NULL);
        long e = (end.tv_sec * 1000 + end.tv_usec / 1000);
        long s =(start.tv_sec * 1000 + start.tv_usec / 1000);
       
        return pair<matrix, long> (c, e - s);
}
 
int main() {
        /* test cut of for strassen
        /*
        for (cut = 2; cut <= 512; cut++) {
                matrix a(512, true, true);
                matrix b(512, true, true);
                result r = run(mult_strassen, a, b);
                cout << cut << " " << r.second << "\n";
        }
        */
       
        /* performance test: standard and strassen */
        for (int dim = 0; dim <= 1024; dim += 64) {
                matrix a(dim, true, false);
                matrix b(dim, true, false);
                result std = run(mult_std, a, b);
                matrix c(dim, true, true);
                matrix d(dim, true, true);
                result strassen = run(mult_strassen, c, d);
                cout << dim << " " << std.second << " " << strassen.second << "\n";
        }
}