Discussion :

[GuillaumeRosa]

Bonjour à tous !

J'en viens à votre aide et je vous explique mon problème.
Je suis débutant en C++ et pour un ours je dois implémenter l'algorithme de Strassen avec des objets Matrice.

Aussitôt dit aussitôt fait ! Quelques recherches sur le net m'ont permis de voir que le projet était déjà fait par un certain Martin Thomas
cf https://martin-thoma.com/strassen-al...thon-java-cpp/

Je me suis inspiré par conséquent de son code en réécrivant à ma sauce avec mes objets matrices.

Cependant après exécution vérification avec Matlab, le calcul ne se fait pas correctement et je dois louper une étape, un truc tout bête
à n'en pas douter, mais le fait est que après 2 h dessus je ne vois rien.

Si des habitués de ce genre d'algo en c++ passaient par là, pourriez vous m'indiquez quelle (grosse ) bêtise j'ai faite ?

J'ai placé en PJ mes fichiers de code.

mon main ne fait que de creer trois matrice A,B,C et lancer Strassen

Strassen.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "Strassen.h"
 
int leafsize=1;
 
void ikjalgorithm(Matrice  A,
                                   Matrice  B,
                                   Matrice  &C, int n) {
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
 
 
            }
        }
    }
}
 
void strassenR(Matrice &A,
              Matrice &B,
              Matrice &C, int tam) {
    if (tam <= leafsize) {
 
        ikjalgorithm(A, B, C, tam);
        return;
    }
 
    // other cases are treated here:
    else {
 
        int newTam = tam/2;
 
        Matrice
            a11(newTam), a12(newTam), a21(newTam), a22(newTam),
            b11(newTam), b12(newTam), b21(newTam), b22(newTam),
              c11(newTam), c12(newTam), c21(newTam), c22(newTam),
            p1(newTam), p2(newTam), p3(newTam), p4(newTam),
            p5(newTam), p6(newTam), p7(newTam),
            aResult(newTam), bResult(newTam);
 
 
 
        //dividing the matrices in 4 sub-matrices:
        for (int i = 0; i < newTam; i++) {
            for (int j = 0; j < newTam; j++) {
                a11.ajouterElement(i,j,A.Element(i,j));
                a12.ajouterElement(i,j,A.Element(i,j+newTam));
                a21.ajouterElement(i,j,A.Element(i+newTam,j));
                a22.ajouterElement(i,j,A.Element(i+newTam,j+newTam));
 
                b11.ajouterElement(i,j,B.Element(i,j));
                b12.ajouterElement(i,j,B.Element(i,j+newTam));
                b21.ajouterElement(i,j,B.Element(i+newTam,j));
                b22.ajouterElement(i,j,B.Element(i+newTam,j+newTam));
 
            }
        }
 
        // Calculating p1 to p7:
 
        sum(a11, a22, aResult, newTam); // a11 + a22
        sum(b11, b22, bResult, newTam); // b11 + b22
        strassenR(aResult, bResult, p1, newTam); //p1 = (a11+a22) * (b11+b22)
 
        sum(a21, a22, aResult, newTam); // a21 + a22
        strassenR(aResult, b11, p2, newTam); // p2 = (a21+a22) * (b11)
 
        subtract(b12, b22, bResult, newTam); // b12 - b22
        strassenR(a11, bResult, p3, newTam); // p3 = (a11) * (b12 - b22)
 
        subtract(b21, b11, bResult, newTam); // b21 - b11
        strassenR(a22, bResult, p4, newTam); // p4 = (a22) * (b21 - b11)
 
        sum(a11, a12, aResult, newTam); // a11 + a12
        strassenR(aResult, b22, p5, newTam); // p5 = (a11+a12) * (b22)
 
        subtract(a21, a11, aResult, newTam); // a21 - a11
        sum(b11, b12, bResult, newTam); // b11 + b12
        strassenR(aResult, bResult, p6, newTam); // p6 = (a21-a11) * (b11+b12)
 
        subtract(a12, a22, aResult, newTam); // a12 - a22
        sum(b21, b22, bResult, newTam); // b21 + b22
        strassenR(aResult, bResult, p7, newTam); // p7 = (a12-a22) * (b21+b22)
 
        // calculating c21, c21, c11 e c22:
 
        sum(p3, p5, c12, newTam); // c12 = p3 + p5
        sum(p2, p4, c21, newTam); // c21 = p2 + p4
 
        sum(p1, p4, aResult, newTam); // p1 + p4
        sum(aResult, p7, bResult, newTam); // p1 + p4 + p7
        subtract(bResult, p5, c11, newTam); // c11 = p1 + p4 - p5 + p7
 
        sum(p1, p3, aResult, newTam); // p1 + p3
        sum(aResult, p6, bResult, newTam); // p1 + p3 + p6
        subtract(bResult, p2, c22, newTam); // c22 = p1 + p3 - p2 + p6
 
        // Grouping the results obtained in a single matrix:
        for (int i = 0; i < newTam ; i++) {
            for (int j = 0 ; j < newTam ; j++) {
                C.ajouterElement(i,j,c11.Element(i,j));
                C.ajouterElement(i,j+newTam,c12.Element(i,j));
                C.ajouterElement(i+newTam,j,c21.Element(i,j));
                 C.ajouterElement(i+newTam,j+newTam,c22.Element(i,j));
            }
        }
    }
}
 
unsigned int nextPowerOfTwo(int n) {
    return pow(2, int(ceil(log2(n))));
}
 
void strassen(Matrice &A,
              Matrice &B,
              Matrice &C, unsigned int n) {
    //unsigned int n = tam;
    unsigned int m = nextPowerOfTwo(n);
 
    Matrice APrep(m), BPrep(m), CPrep(m);
    CPrep.initialiser();
 
    for(unsigned int i=0; i<n; i++) {
        for (unsigned int j=0; j<n; j++) {
            APrep.ajouterElement(i,j,A.Element(i,j));
 
            BPrep.ajouterElement(i,j,B.Element(i,j));
        }
    }
 
    strassenR(APrep, BPrep, CPrep, m);
    for(unsigned int i=0; i<n; i++) {
        for (unsigned int j=0; j<n; j++) {
            C.ajouterElement(i,j,CPrep.Element(i,j));
        }
    }
}
 
void sum(Matrice &A,
         Matrice &B,
         Matrice &C, int tam) {
    int i, j;
 
    for (i = 0; i < tam; i++) {
        for (j = 0; j < tam; j++) {
            C.ajouterElement(i,j,A.Element(i,j)+B.Element(i,j));
        }
    }
}
 
void subtract(Matrice &A,
              Matrice &B,
              Matrice &C, int tam) {
    int i, j;
 
    for (i = 0; i < tam; i++) {
        for (j = 0; j < tam; j++) {
            C.ajouterElement(i,j,A.Element(i,j)-B.Element(i,j));
        }
    }
}

Et mon Matrice.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <iostream>
#include "Matrice.h"
#include <math.h>
#include <cmath>
#include <sstream>
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#define N_MAX 20
 
using namespace std;
 
int Matrice::rand_a_b(int a, int b){
    return rand()%(b-a) +a;
}
 
Matrice::Matrice()
{
}
 
 
 
Matrice::Matrice(int taille) : m_tailleMatrice(taille)
{
 
 
 
    for (int i=0 ; i<m_tailleMatrice ;i++)
    {
        for (int j=0 ; j<m_tailleMatrice ;j++)
        {
            m_colonne.push_back(rand_a_b(0,10));
 
        }
    m_ligne.push_back(m_colonne);
    m_colonne.clear();
 
    }
 
}
 
Matrice::~Matrice()
{
 
}
 
 
void Matrice::initialiser()
{
     for (int i=0 ; i<m_tailleMatrice ;i++)
    {
        for (int j=0 ; j<m_tailleMatrice ;j++)
        {
           m_ligne[i][j]=0;
 
        }
 
 
    }
 
}
 
void Matrice::afficher()
{
 
    for (int i=0 ; i<m_tailleMatrice ;i++)
    {
        for (int j=0 ; j<m_tailleMatrice ;j++)
        {
           cout<< m_ligne[i][j] <<" ";
        }
   cout << endl ;
 
 
    }
 
}
 
 
void Matrice::ajouterElement(int i, int j, int element)
{
            m_ligne[i][j]= element;
}
 
int Matrice::Element (int i, int j)
{
 
    return m_ligne[i][j];
}

Bien cordialement,
Je vous souhaite une excellente journée.