Exception error with Strassen Vinograd Algorithm (SOLVED)
Please help me with algorithm. I'm trying to make an Strassen Vinograd Algorithm and have this exception error. Also the output Matrix is not corrrect(when size is 2 everything is okay but OutPut Matrix is incorrect. The problem is in functions but I do not know how to repair it. I tried to find problem with debbuger but I failed.
Error message:
Exception thrown at 0x001B25F9 in Матричка когось там.exe: 0xC0000005: Access violation reading location 0xFDFDFDFD. occurred
It has to be recursive and it is but does not work:(
#include <iostream>
#include <ctime>
#include <time.h>
using namespace std;
int** add(int** a, int** b, int n)
{
int** q = new int* [n];
for (int i(0); i < n; i++) {
q[i] = new int[n];
}
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
q[i][j] = a[i][j] + b[i][j];
}
}
return q;
}
int** sub(int** a, int** b, int n)
{
int** q = new int* [n];
for (int i = 0; i < n * n; i++)
{
q[i] = new int[n];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{
q[i][j] = a[i][j] - b[i][j];
}
}
return q;
}
int** mul(int** a, int** b, int n)
{
int i, j, k;
int** q = new int* [n];
for (i = 0; i < n; i++)
{
q[i] = new int[n];
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
q[i][j] = 0;
for (k = 0; k < n; k++)
q[i][j] += a[i][k] * b[k][j];
}
return q;
}
int** str1(int** a, int** b, int n)
{
int** c = new int* [n];
for (int i = 0; i < n; i++)
{
c[i] = new int[n];
}
int** m1, ** m2, ** m3, ** m4, ** m5, ** m6, ** m7, ** w, ** t1, ** t2, ** s1, ** s2, ** s3, ** s4, ** s5, ** s6, ** s7, ** s8;
if (n <= 2)
{
mul(a, b, n);
}
else
{
int** C00 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
C00[i] = new int[n / 2];
}
int** C01 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
C01[i] = new int[n / 2];
}
int** C10 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
C10[i] = new int[n / 2];
}
int** C11 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
C11[i] = new int[n / 2];
}
int** A00 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
A00[i] = new int[n / 2];
}
int** A01 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
A01[i] = new int[n / 2];
}
int** A10 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
A10[i] = new int[n / 2];
}
int** A11 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
A11[i] = new int[n / 2];
}
int** B00 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
B00[i] = new int[n / 2];
}
int** B01 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
B01[i] = new int[n / 2];
}
int** B10 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
B10[i] = new int[n / 2];
}
int** B11 = new int* [n / 2];
for (int i(0); i < n / 2; i++) {
B11[i] = new int[n / 2];
}
int i, j;
m1 = new int* [n / 2];
for (int i = 0; i < n / 2; i++)
{
m1[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m1[i][j] = 0;
}
}
m2 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
m2[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m2[i][j] = 0;
}
}
m3 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
m3[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m3[i][j] = 0;
}
}
m4 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
m4[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m4[i][j] = 0;
}
}
m5 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
m5[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m5[i][j] = 0;
}
}
m6 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
m6[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m6[i][j] = 0;
}
}
m7 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
m7[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
m7[i][j] = 0;
}
}
s1 = new int* [n / 2];
for (int i = 0; i < n / 2; i++)
{
s1[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s1[i][j] = 0;
}
}
s2 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s2[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s2[i][j] = 0;
}
}
s3 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s3[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s3[i][j] = 0;
}
}
s4 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s4[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s4[i][j] = 0;
}
}
s5 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s5[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s5[i][j] = 0;
}
}
s6 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s6[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s6[i][j] = 0;
}
}
s7 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s7[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s7[i][j] = 0;
}
}
s8 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
s8[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
s8[i][j] = 0;
}
}
t1 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
t1[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++) {
t1[i][j] = 0;
}
}
t2 = new int* [n / 2];
for (i = 0; i < n / 2; i++)
{
t2[i] = new int[n / 2];
}
for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n / 2; j++)
{
t2[i][j] = 0;
}
}
int half = n / 2;
for (int i = 0; i < half / 2; i++)
{
for (int j = 0; j < half / 2; j++)
{
A00[i][j] = a[i][j];
A01[i][j] = a[i][j + n / 2];
A11[i][j] = a[i + n / 2][j];
A11[i][j] = a[i + n / 2][j + n / 2];
B00[i][j] = b[i][j];
B01[i][j] = b[i][j + n / 2];
B10[i][j] = b[i + n / 2][j];
B11[i][j] = b[i + n / 2][j + n / 2];
}
}
s1 = add(A10, A11, half);
s2 = sub(s1, A00, half);
s3 = sub(A00, A10, half);
s4 = sub(A01, s2, half);
s5 = sub(B01, B00, half);
s6 = sub(B11, s5, half);
s7 = sub(B11, B01, half);
s8 = sub(s6, B10, half);
m1 = mul(s2, s6, half);
m2 = mul(A00, B00, half);
m3 = mul(A01, B10, half);
m4 = mul(s3, s7, half);
m5 = mul(s1, s5, half);
m6 = mul(s4, B11, half);
m7 = mul(A11, s8, half);
t1 = add(m1, m2, half);
t2 = add(t1, m4, half);
w = new int* [n];
for (i = 0; i < n; i++)
{
w[i] = new int[n];
}
s1 = add(m2, m3, n);
for (i = 0; i < half; i++)
{
for (j = 0; j < half; j++)
{
w[i][j] = s1[i][j];
}
}
s1 = add(t1, m5, n);
s2 = add(s1, m6, n);
for (i = 0; i < half; i++)
{
for (j = 0; j < half; j++)
{
w[i][j + half] = s2[i][j];
}
}
s1 = sub(t2, m7, n);
for (i = 0; i < half; i++)
{
for (j = 0; j < half; j++)
{
w[i + half][j] = s1[i][j];
}
}
s1 = add(t2, m5, n);
for (i = 0; i < half; i++)
{
{
for (j = 0; j < half; j++)
w[i + half][j + half] = s1[i][j];
}
}
return w;
}
}
int main()
{
int N;
cout << "BE CAREFUL ROZMIR MATRUCI POVUNEN BYTU N^2 I DVI MATRUCI POVUNNI BYTU ODNAKOVOGO ROZMIRY" << endl;
cout << "Enter kil'kist' ryadkiv i stpvpciv dlya dvox matruc':" << endl;
cin >> N;
cout << "Let's create first matrix:" << endl;
int** Matr = new int* [N];
for (int i = 0; i < N; i++)
Matr[i] = new int[N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << "E[" << i << "][" << j << "]=";
cin >> Matr[i][j];
}
}
cout << "Your first Maatrix:" << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << Matr[i][j] << " ";
}
cout << endl;
}
cout << "Let's create second matrix:" << endl;
int** Matr1 = new int* [N];
for (int i = 0; i < N; i++)
Matr1[i] = new int[N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << "E[" << i << "][" << j << "]=";
cin >> Matr1[i][j];
}
}
cout << "Your second Maatrix:" << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << Matr1[i][j] << " ";
}
cout << endl;
}
int** Matr2 = new int* [N];
for (int i = 0; i < N; i++)
Matr2[i] = new int[N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
Matr2[i][j] = 0;
}
}
Matr2 = str1(Matr, Matr1, N);
for (int i = 0; i < N; i++)
{
cout << endl;
for (int j = 0; j < N; j++)
{
cout << Matr2[i][j];
}
system("pause");
return 0;
}
}
Sevka
0 Answers
Nobody has answered this question yet.
User contributions licensed under CC BY-SA 3.0