Bug programma determinante matrice c++

[Super Squirrel]

Ciao a tutti!

Premetto che di informatica ho pochissime conoscenze(basi di c++).
Ho creato un programma in c++ che per una matrice di dimensioni nXm qualsiasi ti calcola (sfruttando il metodo di Gauss http://it.wikipedia.org/wiki/Metodo_di_ ... e_di_Gauss) rango e, se la matrice è quadrata, determinante.
Ho implementato inoltre che gli elementi della matrice siano frazioni in cui numeratore e denominatore sono interi. Inizialmente ho usato il tipo int e il programma funzionava alla perfezione.
Finchè non ho dovuto calcolare il determinante di una matrice 5X5. Inseriti i valori non me la riduceva a gradini e il determinante era sbagliato. Inserita infatti la matrice in un programma online, essa veniva ridotta a gradini normalmente e il determinante(pari al prodotto dei pivot, ossia degli elementi della diagonale principale nel caso di rango massimo) era diverso da quello trovato dal mio programma.
Ho pensato subito che si trattasse di un problema di overflow e quindi ho sostituito "int" con "int64_t"(long long).
A questo punto la stessa matrice 5x5 mi dava un altro problema...nel momento in cui confermo l'ultimo valore della matrice il programma si blocca. Con lo stesso programma ho provato matrici con valori più piccoli e funziona bene, con valori grandi invece mi da' risultati sballati, ma cmq non si blocca.
Ho letto che int64_t è supportato solo dai sistemi operativi a 64 bit e il mio è a 32 bit. Ho scritto quindi un programmino che moltiplica due numeri del tipo int64_t e inserendo da tastiera fattori di 12 cifre il prodotto era corretto.

Qualcuno saprebbe aiutarmi?

in allegato un file.rar con all'interno l'exe, il file sorgente.cpp e l'immagine della matrice 5x5 in questione.

[vict85]

Perché non c'è

#include<cstdint>

per la definizione di int64_t?

La riga

int64_t v[p][p][2];

è un codice contrario allo standard C++ anche se è accettato come estesione da alcuni compilatori (in quanto il C te lo permette, ma un suo uso pseudocasuale è altamente sconsigliabile).

Detto questo se il tuo scopo è quella di creare una matrice di numeri razionali allora il modo migliore è usare un array multidimensionale di strutture. Inoltre rende molto più comprensibile il tutto.

Non ho invece capito tutto il tuo discorso sull'int64_t che non penso sia il tuo problema (a meno di problemi con le frazioni[nota]Problemi che si potrebbero probabilmente risolvere approssimando le frazioni problematiche.[/nota]).

[Super Squirrel]

Innanzitutto grazie mille per la disponibilità.

Perché non c'è
CODICE:
#include
per la definizione di int64_t?

aggiunto (#include).Utilizzo Code::Blocks e per compilare ho dovuto spuntare l'opzione del compilatore
(-std=c++11).

La riga
CODICE:
int64_t v

[2];
è un codice contrario allo standard C++ anche se è accettato come estesione da alcuni compilatori (in quanto il C te lo permette, ma un suo uso pseudocasuale è altamente sconsigliabile).

Detto questo se il tuo scopo è quella di creare una matrice di numeri razionali allora il modo migliore è usare un array multidimensionale di strutture. Inoltre rende molto più comprensibile il tutto.

come premesso le mie conoscenze di informatica sono ridotte, sono andato di logica sfruttando le poche conoscenze a disposizione. non so cosa sia un array multidimensionale di strutture, ma farò qualche ricerca e nel caso modificherò il programma.

Non ho invece capito tutto il tuo discorso sull'int64_t che non penso sia il tuo problema (a meno di problemi con le frazioni1).

nonostante l'aggiunta della libreria da te indicata il problema persiste. La matrice 5x5 nell'immagine fa crashare il programma quando confermo il denominatore dell'ultimo valore. Inoltre per testare il tipo int64_t ho fatto dei tentativi su matrici 2x2: per valori non molto grandi la matrice risulta ridotta a scalini e il determinante esatto, se invece i valori inseriti sono dell'ordine delle 6-7 cifre (ovviamente a patto che la frazione non si semplifichi troppo) il programma mi mostra una matrice non ridotta a scalini nonostante il rango sia pari a 2 e ciò mi fa pensare che il problema non sia di programmazione, ma di calcolo...non so ora se dovuto ad overflow o cosa.

Mi sono rivisto il codice non so quante volte, ma non riesco a trovare errori, a cosa potrebbe essere dovuto il mal funzionamento?

[vict85]

Perché non cominci scrivendo la funzione con i double e poi eventualmente la modifichi per usare i razionali? Per lo meno hai un migliore feedback su cosa succede, il codice è più immediato (e lo trovi in giro) e sei sicuro che non ci siano problemi di overflow. Una volta che funziona per i double cambiare il tipo è una operazione non troppo difficile.

Comunque il pivoting e il controllo della divisione per 0 lo fai? Perché l'algoritmo di Gauss richiede il pivoting a meno di matrici sufficientemente buone (ricorda inoltre che il pivoting influisce sul determinate).

[Super Squirrel]

Perché non cominci scrivendo la funzione con i double e poi eventualmente la modifichi per usare i razionali? Per lo meno hai un migliore feedback su cosa succede, il codice è più immediato (e lo trovi in giro) e sei sicuro che non ci siano problemi di overflow. Una volta che funziona per i double cambiare il tipo è una operazione non troppo difficile.

Vorrei evitare di stravolgere il programma e sostituire coi double significa iniziare a controllare il programma da capo.
Quello che mi fa pensare che siano problemi di calcolo (overflow o simili), è il fatto che il programma, nel caso della matrice 5x5 in questione,con gli int non si blocca ma mi da' valori sballati, mentre con gli int64_t si blocca alla conferma dell'ultimo valore. forse con gli int i valori sballati non fanno crashare il programma, mentre con int64_t si, anche se ne ignoro il motivo.

Comunque il pivoting e il controllo della divisione per 0 lo fai? Perché l'algoritmo di Gauss richiede il pivoting a meno di matrici sufficientemente buone (ricorda inoltre che il pivoting influisce sul determinate).

SI, il programma fa proprio questo, riduce la matrice a scalini tramite operazioni riga elementari(in particolare sfrutto lo scambio di due righe e la sostituzione di una riga con la somma della stessa riga per un multiplo di un'altra. La seconda operazione non influisce sul determinante mentre la prima ne cambia il segno e di questo ne tengo conto nel programma).
Mi scuso se con pivoting tu intenda qualcos'altro.
Per quanto riguarda la divisione per 0 ho strutturato il programma in modo che questo non avvenga. l'unico modo in cui ciò era possibile era tramite inserimento da tastiera di un denominatore pari a zero, ma ho aggiustato anche questo facendo terminare il programma nel caso durante l'inserimento si immetta un denominatore uguale a 0. (in allegato il programma aggiornato)

So che forse chiedo molto, ma potresti controllare il codice per vedere se ci sono errori?
O cmq, ammesso che non ci siano errori nel codice, quale potrebbe essere il problema? non so, magari bisogna smanettare con le impostazioni del compilatore...

[Super Squirrel]

Credo di aver semplificato il problema.

Ho creato un programma che ti permette di inserire un numeratore e un denominatore interi e ti mostra poi la frazione ridotta.

#include <iostream>
#include <stdlib.h>
#include <cstdint>

using namespace std;

void normfrazione(int64_t &a,int64_t &b)
{
if(a==0)
{
b=1;
}
else
{
int64_t c,d,r;
if(a<0)c=-a;
else c=a;
if(b<0)d=-b;
else d=b;
r=c%d;
while(r!=0)
{
c=d;
d=r;
r=c%d;
}
if(a*b<0 && a<0 || a*b>0 && a>0)
{
a=a/d;
b=b/d;
}
if(a*b<0 && a>0 || a*b>0 && a<0)
{
a=-a/d;
b=-b/d;
}
}
return;
}

void outfrazione(int64_t a,int64_t b)
{
normfrazione(a,b);
if(b==1)
{
cout<<a;
}
else
{
cout<<a<<"/"<<b;
}
return;
}

int main()
{
int64_t x,y;
cout<<"Inserire numeratore ";
cin>>x;
if(x==0)y==1;
else
{
cout<<"Inserire denominatore ";
cin>>y;
}
if(y!=0)
{
cout<<"Frazione ridotta ";
outfrazione(x,y);
}
cout<<endl<<endl;
system("PAUSE");
}

per valori non troppo grandi funziona bene, ma se inserisco per esempio num = den = -13579246801 mi dà come risultato
0/0 !!

Come mai?

[apatriarca]

Immagino che il problema possa essere che a*b non è rappresentabile nel tuo caso in 64bit. Ma non ho provato il codice. Con numeri più piccoli funziona?

[vict85]

A parte un errore in

if(x==0)y==1;

che andrebbe cambiato in

if(x==0)y=1;

penso ci sia un problema con la funzione mcd.

Prova a vedere se cambiando l'mcd con questo

uint64_t mcd_u(uint64_t a, uint64_t b)
{
	if ((a == b) || (b == 0))
		return a;

	if (a == 0)
		return b;

	if (b > a)
		return mcd_u(b, a);

	if (a % 2 == 0)
	{
		if (b % 2 == 0)
		{
			return 2 * mcd_u(a / 2, b / 2);
		}
		else
		{
			return mcd_u(a / 2, b);
		}
	}
	else
	{
		if (b % 2 == 0)
		{
			return mcd_u(a, b / 2);
		}
		else
		{
			return mcd_u((a - b) / 2, b);
		}
	}
}

int64_t mcd(int64_t a, int64_t b)
{
	if (a < 0) a = -a;
	if (b < 0) b = -b;
	return static_cast<int64_t>(mcd_u(static_cast<uint64_t>(a), static_cast<uint64_t>(b)));
}

ti risolve il problema.

[Super Squirrel]

Immagino che il problema possa essere che a*b non è rappresentabile nel tuo caso in 64bit. Ma non ho provato il codice. Con numeri più piccoli funziona?

Si, per valori più piccoli funziona.

A parte un errore in
CODICE:
if(x==0)y==1;
che andrebbe cambiato in
CODICE:
if(x==0)y=1;
penso ci sia un problema con la funzione mcd.

Prova a vedere se cambiando l'mcd con questo
CODICE:
uint64_t mcd_u(uint64_t a, uint64_t b)
{
if ((a == b) || (b == 0))
return a;

if (a == 0)
return b;

if (b > a)
return mcd_u(b, a);

if (a % 2 == 0)
{
if (b % 2 == 0)
{
return 2 * mcd_u(a / 2, b / 2);
}
else
{
return mcd_u(a / 2, b);
}
}
else
{
if (b % 2 == 0)
{
return mcd_u(a, b / 2);
}
else
{
return mcd_u((a - b) / 2, b);
}
}
}

int64_t mcd(int64_t a, int64_t b)
{
if (a < 0) a = -a;
if (b < 0) b = -b;
return static_cast(mcd_u(static_cast(a), static_cast(b)));
}
ti risolve il problema.

Corretto l'errore e modificato il programmino precedente nel seguente modo:

#include <iostream>
#include <stdlib.h>
#include <cstdint>

using namespace std;

uint64_t mcd_u(uint64_t a, uint64_t b)
{
   if ((a == b) || (b == 0))
      return a;

   if (a == 0)
      return b;

   if (b > a)
      return mcd_u(b, a);

   if (a % 2 == 0)
   {
      if (b % 2 == 0)
      {
         return 2 * mcd_u(a / 2, b / 2);
      }
      else
      {
         return mcd_u(a / 2, b);
      }
   }
   else
   {
      if (b % 2 == 0)
      {
         return mcd_u(a, b / 2);
      }
      else
      {
         return mcd_u((a - b) / 2, b);
      }
   }
}

int64_t mcd(int64_t a, int64_t b)
{
   if (a < 0) a = -a;
   if (b < 0) b = -b;
   return static_cast<int64_t>(mcd_u(static_cast<uint64_t>(a), static_cast<uint64_t>(b)));
}

void normfrazione(int64_t &a,int64_t &b)
{
if(a==0)
{
b=1;
}
else
{
int64_t c=mcd(a,b);
if(a*b<0 && a<0 || a*b>0 && a>0)
{
a=a/c;
b=b/c;
}
if(a*b<0 && a>0 || a*b>0 && a<0)
{
a=-a/c;
b=-b/c;
}
}
return;
}

void outfrazione(int64_t a,int64_t b)
{
normfrazione(a,b);
if(b==1)
{
cout<<a;
}
else
{
cout<<a<<"/"<<b;
}
return;
}

int main()
{
int64_t x,y;
cout<<"Inserire numeratore ";
cin>>x;
if(x==0)y=1;
else
{
cout<<"Inserire denominatore ";
cin>>y;
}
if(y!=0)
{
cout<<"Frazione ridotta ";
outfrazione(x,y);
}
cout<<endl<<endl;
system("PAUSE");
}

num = den = -13579246801 mi dà ancora come risultato 0/0 !!

forse è passato in secondo piano, ma ho specificato di avere un sistema operativo a 32 bit, potrebbe entrarci?
magari potreste provare il codice del programmino che ho postato prima su un sistema a 64 bit e vedere cosa succede per
num = den = -13579246801.

[vict85]

normfrazione è eccessivamente complicato per i suoi scopi. Ciò che conta è che il denominatore non sia negativo. Pertanto andrebbe implementato così:

void normfrazione(int64_t &a, int64_t &b)
{
	if (a == 0) {
		b = 1;
	}
	else {
		if (b < 0)
		{
			b = -b;
			a = -a;
		}
		int64_t const c = mcd(a, b);
		b /= c;
		a /= c;
	}
}

Penso in fin dei conti che il mcd fosse corretto, o che per lo meno non fosse il problema.

[Super Squirrel]

Giusto, assodato che il numeratore sia negativo basta moltiplicare num e den per -1 per normalizzare la frazione dal punto di vista dei segni.

Cmq semplificando normfrazione il programmino per ridurre le frazioni funziona anche per valori più grandi. Ho modificato normfrazione anche nel programma del rango e determinante (e in un altro programma per trovare l'inversa di una matrice quadrata che mi dava problemi simili per valori grandi) e ora funziona alla perfezione anche per valori più grandi.

Alla fine il problema era questa parte di codice:

if(a*b<0 && a<0 || a*b>0 && a>0)
{
a=a/c;
b=b/c;
}
if(a*b<0 && a>0 || a*b>0 && a<0)
{
a=-a/c;
b=-b/c;
}

Grazie ancora della disponibilità.

Giusto per capire, quale potrebbe essere precisamente il motivo per cui questo pezzetto di codice va in conflitto col tipo int64_t per valori grandi?
so che in questo caso mi sono complicato la vita inutilmente, in quanto c'era una soluzione molto più semplice, ma mettiamo il caso che fosse stato necessario un controllo del genere(che peraltro non mi sembra pesantissimo per un calcolatore).