i dont know how to fix need help

Pages: 12
mattryca (11)
hey im new here and sorry for my english

i have small problem whit my project in school.

Determination of the matrix determinant 4x4 / 8x8 / 16x16 with a set range of integers, e.g. from 0 to 100 (may be different) so that the determinant is a 1-iterative method and using a pseudorandom number generator - saving the obtained solutions to a file without duplicates.

and i made it but it crashing. i think it crashing when memory of checking duplicates is full.

any solution or any idea ?? would be great :)

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
double ** L;
double ** U;
int ** A;
int N;

//funkcje pomocnicze do obliczenia wyznacznika
double suma1(int i , int j ){
double ret=0;

for(int k=0;k<i;k++){

ret+=L[i][k]*U[k][j];

}
return ret;
}

double suma2(int i , int j ){
double ret=0;

for(int k=0;k<i;k++){

ret+=L[j][k]*U[k][i];

}
return ret;
}

double wyznacznik(int ** A){ //funkcje liczaca wyznacznik z podanej macierzy metoda LU
double w=1.0; //wyznacznik
for(int i=0;i<N;i++){

for(int j=0;j<N;j++){

U[i][j]=0;
L[i][j]=0;
}

}

for(int i=0;i<N;i++){

L[i][i]=1;

}




for(int i=0;i<N;i++){

for(int j=i;j<N;j++){



U[i][j]=A[i][j]-suma1(i,j);

}


for(int j=i+1;j<N;j++){


L[j][i]=(1/U[i][i])*(A[j][i]-suma2(i,j));

}

}
for(int i=0;i<N;i++)w*=U[i][i]; // wyznacznik = iloczynowi elementów na przek¹tnej macierzy U


return w;

}

struct powtorzenie{// element przechowujacy macierze zapisane do pliku

int **A;

};
bool sprawdz(int **A,powtorzenie *B,int k){//funkcja sprawdza czy macierz sie nie powtorzyla

for(int x=0;x<k;x++){

bool c=true;
for(int i=0;i<N;i++){

for(int j=0;j<N;j++){
if(B[x].A[i][j]!=A[i][j])c=false;
}
}
if(c)return true;
}
return false;
}


int main(){
int ilosc;
printf ("Podaj rozmiar tablicy(4,8,16):");

scanf("%i",&N);



L=new double*[N];
for(int i=0;i<N;i++)L[i]=new double[N];
U=new double*[N];
for(int i=0;i<N;i++)U[i]=new double[N];
A=new int*[N];
for(int i=0;i<N;i++)A[i]=new int[N];
powtorzenie *B=new powtorzenie[30000];
int k=0;

FILE *f;

if ((f=fopen("p1_wynik.txt", "w"))==NULL) {
printf ("Nie mogê otworzyæ pliku test.txt do zapisu!\n");
exit(1);
}


fprintf (f, "Wygenerowane macierze ktorych wyznacznik wynosi 1: \n \n ");
ilosc=0;
for(int t=1;t<1000000000;t++){// liczba obrotów oznacz ilosc wygenerowanych i sprawdzonych tablic

for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
A[i][j]=rand()%15; //zakres od zera do podanej liczby
}
}

if(wyznacznik(A)==1 ){

if(!sprawdz(A,B,k)){


B[k].A=new int*[N];
for(int i=0;i<N;i++)B[k].A[i]=new int[N];
fprintf (f, "\n ");
printf ( "\n ");


for(int i=0;i<N;i++){
for(int j=0;j<N;j++){

fprintf (f, "%i ", A[i][j]);
printf ( "%i ", A[i][j]);

B[k].A[i][j]=A[i][j];

}

fprintf (f, "\n ");
printf ( "\n ");
}
fprintf (f, "\n ");
printf ( "\n ");
k++;
ilosc++;
}
}
}
printf("Znaleziono %d macierzy",ilosc);
fclose (f);

return 0;
}


in know its in c++ but looks like c

pls dont ask why :P
ne555 (10692)
cannot reproduce.
show the backtrace and the content of the A matrix when you get a crash.

t<1000000000
too much

> in know its in c++ but looks like c
> pls dont ask why :P
the problem is with the globals and the manual memory management (not deleting anything)
mattryca (11)
my teacher what to run program all night to saw how many matrix we gona get for 8x8 det=1; loop for (;;).


show the backtrace and the content of the A matrix when you get a crash.<=== what u mean ?
jonnin (11438)
new will tell you if it fails due to no memory etc. Put in a check if you think you ran out of memory. Or, you can be lazy and watch the task manager when its running (or whatever unix memory show command is, top maybe? Im rusty and not feeling the google tonight).


mattryca (11)
i didnt sleep 30h looking for my mistake.
maybe i need use "delete" some where ? but where?
im runing out of time tomorrow i need give program to teaccher ;/ andd need do paper work ;/
MikeyBoy (5631)
i didnt sleep 30h looking for my mistake.

That's a mistake. You will never be able to work properly if you're sleep-deprived.

Go to sleep, and then look at the problem with a clear head.

EDIT: I strongly recommend using a debugger to step through your code, and to find out exactly where it's crashing.
Last edited on
mattryca (11)
used gdb online (never worked whit gbd lerning for 5 months). and when i used command bt (number) i get no stack. when i use "run" and press any number i get [Inferior 1 (process 32310) exited with code 01] no such file (my matrix need to be save in file)
dhayden (5798)
It doesn't crash for me, but it doesn't do much of anything either. Here is your code with my modifications. Search for "dmh" in the comments.
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
161
162
163
164
165
166
167
168
169
 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
double **L;
double **U;
int **A;
int N;

//funkcje pomocnicze do obliczenia wyznacznika
double
suma1(int i, int j)
{
    double ret = 0;

    for (int k = 0; k < i; k++) {
	ret += L[i][k] * U[k][j];
    }
    return ret;
}

double
suma2(int i, int j)
{
    double ret = 0;

    for (int k = 0; k < i; k++) {
	ret += L[j][k] * U[k][i];
    }
    return ret;
}

double
wyznacznik(int **A)
{						 //funkcje liczaca wyznacznik z podanej macierzy metoda LU
    double w = 1.0;		//wyznacznik
    for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	    U[i][j] = 0;
	    L[i][j] = 0;
	}
    }

    for (int i = 0; i < N; i++) {
	L[i][i] = 1;
    }

    for (int i = 0; i < N; i++) {
	for (int j = i; j < N; j++) {
	    U[i][j] = A[i][j] - suma1(i, j);
	}

	// DMH: Is this code right? You're assigning values to L and those
	// values are used in suma1() and suma2(). Is that okay?
	for (int j = i + 1; j < N; j++) {
	    L[j][i] = (1 / U[i][i]) * (A[j][i] - suma2(i, j));
	}
    }
    for (int i = 0; i < N; i++)
	w *= U[i][i];				 // wyznacznik = iloczynowi elementów na przek¹tnej macierzy U

    // The values are usually pretty big, which makes me thing something
    // is wrong with the math.
    printf("result = %g\n", w);
    return w;

}

struct powtorzenie
{				// element przechowujacy macierze zapisane do pliku
    int **A;
};
bool
sprawdz(int **A, powtorzenie * B, int k)
{						 //funkcja sprawdza czy macierz sie nie powtorzyla

    for (int x = 0; x < k; x++) {

	bool c = true;
	// dmh: added "&& c& tests below for efficiency
	for (int i = 0; i < N && c; i++) {
	    for (int j = 0; j < N && c; j++) {
		if (B[x].A[i][j] != A[i][j])
		    c = false;
	    }
	}
	if (c)
	    return true;
    }
    return false;
}

int
main()
{
    int ilosc;
    printf("Podaj rozmiar tablicy(4,8,16):");

    scanf("%i", &N);

    L = new double *[N];
    for (int i = 0; i < N; i++)
	L[i] = new double[N];
    U = new double *[N];
    for (int i = 0; i < N; i++)
	U[i] = new double[N];
    A = new int *[N];
    for (int i = 0; i < N; i++)
	A[i] = new int[N];
    powtorzenie *B = new powtorzenie[30000];
    int k = 0;

    FILE *f;

    if ((f = fopen("p1_wynik.txt", "w")) == NULL) {
	printf("Nie mogê otworzyæ pliku test.txt do zapisu!\n");
	exit(1);
    }

    fprintf(f, "Wygenerowane macierze ktorych wyznacznik wynosi 1: \n \n ");
    ilosc = 0;
    for (int t = 1; t < 1000000000; t++) {	 // liczba obrotów oznacz ilosc wygenerowanych i sprawdzonych tablic
	// DMH: Here is some debugging code to let you know it's doing something
	if (t%100 == 0) {
	    printf(".");
	    fflush(stdout);
	}
	for (int i = 0; i < N; i++) {
	    for (int j = 0; j < N; j++) {
		A[i][j] = rand() % 15;		 //zakres od zera do podanej liczby
	    }
	}

	if (wyznacznik(A) == 1) {

	    if (!sprawdz(A, B, k)) {

		B[k].A = new int *[N];
		for (int i = 0; i < N; i++)
		    B[k].A[i] = new int[N];
		fprintf(f, "\n ");
		printf("\n ");

		for (int i = 0; i < N; i++) {
		    for (int j = 0; j < N; j++) {
			fprintf(f, "%i ", A[i][j]);
			printf("%i ", A[i][j]);
			B[k].A[i][j] = A[i][j];
		    }

		    fprintf(f, "\n ");
		    printf("\n ");
		}
		fprintf(f, "\n ");
		printf("\n ");
		fflush(stdout);
		fflush(f);
		k++;
		ilosc++;
	    }
	}
    }
    printf("Znaleziono %d macierzy", ilosc);
    fclose(f);

    return 0;
}

mattryca (11)
suma1 and sume are ok algorytm is ok

its dispersion LU
matrix A= matrix L*matrix U. whit this metod i get det==1.


try at 2 or 3 or 4 it will crush


was trying your code but still same
Last edited on
lastchance (6980)
@mattryca,
Please could you explain what you are actually trying to do? You may need a better translator.

You appear to be trying to LU factorise at one point (in routine wyznacznik(int **A)) and then multiplying the diagonal elements of U to get the determinant. That's strictly true ... but it's quite a long-winded way of finding a determinant. If you want an LU factoriser you can try here:
http://www.cplusplus.com/forum/general/235545/#msg1059501
(Turn the partial-pivoting off if you want straight LU factorisation, but expect the factorisation to fail occasionally if you do so - you don't account for that in your code: watch out for cases where U[i][i] is near zero, since you divide by that.)

Are you aware that there are an infinite number of matrices with determinant 1? Any rotation matrix will do, but there are plenty of others.
Last edited on
mattryca (11)
i need fill matrix whit rand (range from 1-5 or any other) numbers whitout duplicates. then it isnt infinite number of matrix
Last edited on
mattryca (11)
bool
sprawdz(int **A, powtorzenie * B, int k)
{ //funkcja sprawdza czy macierz sie nie powtorzyla

for (int x = 0; x < k; x++) {

bool c = true;
// dmh: added "&& c& tests below for efficiency
for (int i = 0; i < N && c; i++) {
for (int j = 0; j < N && c; j++) {
if (B[x].A[i][j] != A[i][j])
c = false;
}
}
if (c)
return true;
}
return false;
}
powtorzenie *B=new powtorzenie[30000];


i think here is problem

my program crash

i dont know where and how delete duplicate matrix or delete matrix in memory. I think when memory full program crash not maybe crash but stop in 1 place if i do for(int t=1;t<1000000000;t++) or for(int t=1;t<1000000;t++) resualts are same

sry im new in c++ 3 months learning
lastchance (6980)
Well, I used @dhayden's version because I couldn't read your original. It didn't crash (although I'm quite surprised, given the amount of memory it could use.)

I can guarantee that your LU algorithm WILL fail occasionally (when you divide by U[i][i] = 0). It certainly ought to fail if the determinant is zero. This is NOT a good way of finding a determinant.

Rather than having to store many preceding matrices to check for duplicates, have you not considered sequentially permuting them? That will ensure no duplicates. Or if you just want a lot of matrices with determinant 1 then set up a succession of rotation matrices. You really aren't explaining exactly what you want.
mattryca (11)
my fault
not crashig but stoping and return 0 every thing is ok

but when i do for( int t=1;t<1000000;t++) i gate same matrix and same numbers of matrix when i use for (;;).

maybe this when when he get u[i][j]=0 then program will stop and return 0 or he will skip this matrix ?
lastchance (6980)
At the moment, when you divide by U[i][i] = 0 (that's the diagonal element) your program is probably returning inf (an overflow value). Your problem is that dividing by a diagonal element of zero can happen because either the determinant IS zero or because your LU algorithm is NOT failsafe - you need at least partial pivoting (https://en.wikipedia.org/wiki/LU_decomposition) to ensure that the algorithm works.

I take it that you have CHECKED that multiplying L by U actually gives you A?
You need to test that function on its own, with a known matrix, not a randomly-generated one.

I really don't like this line:
if (wyznacznik(A) == 1)
That function is returning a double (i.e. a floating-point value). You are trying to compare it for EXACT EQUALITY. Floating-point numbers are only stored to a finite precision, and you are creating it by multiplying between 4 and 16 numbers together, each of which is created in turn by some gaussian-elimination-like sums. I really wouldn't be surprised if it NEVER came back as 1.000000000000. Even without the problems in your determinant routine you should be deciding if it is "within a small distance from 1.0", not "exactly 1.0". This would probably be sufficient, given that your original matrix was made of integers and hence its determinant should actually be a whole number.

You need to put more debugging lines in your code and test each stage of the process. @dhayden has put some examples in to show you how to do this. Ideally, you need to see the matrices at some point (which means that you should keep them small and not do a large number of trials).
Last edited on
mattryca (11)
it not "crashing" at small

i add to my code


const double eps = 1e-12;

if(fabs(U[i][i]) < eps) return w=0;
for (int j = i + 1; j < N; j++) {
L[j][i] = (1 / U[i][i]) * (A[j][i] - suma2(i, j));
lastchance (6980)
I edited my post @mattryca. Please see my comments about your line
if (wyznacznik(A) == 1)

Also, note that the LU algorithm you are using CAN fail, even for perfectly legitimate matrices. Why don't you try to LU-factorise the matrix
0 -1
1  0

(which has determinant 1). Your algorithm will fail.
Last edited on
mattryca (11)
#include <iomanip>

under int main cout << setprecision(4) << fixed;?


we do matrix from 1 to 100
Last edited on
lastchance (6980)
@mattryca,

The problem is your maths, not the way you are writing your output.
Pages: 12