C help needed

[aneeshm]

For some reason, the following code doesn't work. The point is, it should.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

/* float determinant(float *a, int n) {{{1 */
float determinant(float *a, int n)
{
	float *b, det=0;

	if(n<2)
		return 0;

	if(n==2)
		det=( (*a)*(*(a+3)) - (*(a+1))*(*(a+2)));
	else
	{
		b=malloc((n-1)*(n-1)*sizeof(float));

		int i,j,k,m=0,l=0;

		for(i=0;i<n;i++)
		{
			for(j=1;j<n;j++)
				for(k=0;k<n;k++)
					if(k!=i)
					{
						*(b + (n-1)*l + m)=
							*(a + n*j+ k);
						m++;
						l+=m/(n-1);
						m%=(n-1);
					}

			det+=(*(a+i))*determinant(b, n-1)*pow(-1,i);
		}

		free(b);
	}

	return det;
}
/* 1}}} */

int main()
{
	float *a, det;
	int n,i,j;

	printf("Enter the no. of rows\n# ");
	scanf("%d", &n);
	printf("\n\n");

	a=malloc(n*n*sizeof(float));

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			printf("Enter element (%d,%d)# ", (i+1), (j+1));
			scanf("%f", (a + i*n + j));
		}

	det=determinant(a, n);

	free(a);

	printf("\n\nThe determinant is: %f\n\n", det);

	return 0;
}

The errors it is giving:

*** glibc detected *** ./a.out: free(): invalid next size (fast): 0x0000000000601040 ***
======= Backtrace: =========
/lib/libc.so.6[0x2ab41ff97b23]
/lib/libc.so.6(cfree+0x8c)[0x2ab41ff9b26c]
./a.out[0x400877]
./a.out[0x40095a]
/lib/libc.so.6(__libc_start_main+0xf4)[0x2ab41ff458e4]
./a.out[0x4005e9]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:04 4014120                            /home/aneeshm/work/se/pl-ass/mat/a.out
00600000-00601000 rw-p 00000000 08:04 4014120                            /home/aneeshm/work/se/pl-ass/mat/a.out
00601000-00622000 rw-p 00601000 00:00 0                                  [heap]
2ab41fa89000-2ab41faa5000 r-xp 00000000 08:04 8880137                    /lib/ld-2.5.so
2ab41faa5000-2ab41faaa000 rw-p 2ab41faa5000 00:00 0 
2ab41fca4000-2ab41fca6000 rw-p 0001b000 08:04 8880137                    /lib/ld-2.5.so
2ab41fca6000-2ab41fd27000 r-xp 00000000 08:04 8912908                    /lib/libm-2.5.so
2ab41fd27000-2ab41ff26000 ---p 00081000 08:04 8912908                    /lib/libm-2.5.so
2ab41ff26000-2ab41ff28000 rw-p 00080000 08:04 8912908                    /lib/libm-2.5.so
2ab41ff28000-2ab42006f000 r-xp 00000000 08:04 8880190                    /lib/libc-2.5.so
2ab42006f000-2ab42026f000 ---p 00147000 08:04 8880190                    /lib/libc-2.5.so
2ab42026f000-2ab420272000 r--p 00147000 08:04 8880190                    /lib/libc-2.5.so
2ab420272000-2ab420274000 rw-p 0014a000 08:04 8880190                    /lib/libc-2.5.so
2ab420274000-2ab42027a000 rw-p 2ab420274000 00:00 0 
2ab42027a000-2ab420287000 r-xp 00000000 08:04 8880139                    /lib/libgcc_s.so.1
2ab420287000-2ab420487000 ---p 0000d000 08:04 8880139                    /lib/libgcc_s.so.1
2ab420487000-2ab420488000 rw-p 0000d000 08:04 8880139                    /lib/libgcc_s.so.1
2ab424000000-2ab424021000 rw-p 2ab424000000 00:00 0 
2ab424021000-2ab428000000 ---p 2ab424021000 00:00 0 
7fff8b00c000-7fff8b021000 rw-p 7fff8b00c000 00:00 0                      [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vdso]
Aborted (core dumped)

I've not been able to make head or tail of it.

A quick GDB session tells me it is breaking the first time that free is called within the determinant function.

 

[Asher]

I think you would cry if you discovered how easy this program would be in C#.

Also, consider documenting your code.

The code is so messy and inconsistently formatted that I can't be bothered to read it thoroughly.

Why are people still writing code like this? This is hideous. There's no reason to use C for this today with malloc/free.

 

[Comraddict]

do you really need to use heap for this?

 

[Perfection]

I have a feeling that we're doing someone's homework.

 

[ParadigmShifter]

Holy no error checking Batman!

What if you enter 0 or a negative number for the number of rows?
What if you enter non-numerical data for the number of rows?
How many times did the loop run before the crash at free?
What if malloc returns NULL?
What if n*n*sizeof(float) exceeds heap memory limit? Not to mention the other allocations in the recursive determinant function.

Yikes.

It's possible to write code that is robust involving user input and dynamic memory allocation in C but it is a lot of effort. The effort part is what is missing from the code shown. It looks like example code from a book that isn't meant to be used in a serious situation to me.

Yikes again.

EDIT: Read the code and the OP a bit more thoroughly (my brain hurts now). If it is crashing "at the first call to free in the determinant function" this means that a valid number of rows >2 has been entered.

The calculation of the sub-determinant looks like it could be the problem to me. Are you sure that the matrix pointed to by b is correct and all the writes through the b pointer are to valid memory ranges? I'd sprinkle lots and lots and lots of assert() or printfs in the loop and check this. The usage of variables l and m look a bit suspect to me. Those would be the first things I would look at. Also, don't call variables "l" unless you really want to annoy people (and if you do that, call all your variables l, l1, l1l, l11l, l1l1, etc., that will annoy them the most).

I'd also use array notation for dereferencing the pointers rather than cryptic pointer arithmetic. I'd have a row pointer which advances 1 row at a time pointing at the subrows of the matrix.

You can probably calculate the subdeterminant matrix better by using the "crossing out" method but cross out ROWS rather than columns. You will make the inner loop easier to understand. Crossing out columns is not good for simplicity of the algorithm since the data is stored one row at a time. (EDIT: Because you could memcpy a row and save a nested loop rather than copying column data and skipping a column entry here and there).

Abother brainwave: The "crossing out" method doesn't care which row or column is crossed out either, if you cross out the LAST row or column you will find the whole world is a much easier and saner place for this algorithm.

EDIT2: Definitely do the above. Use the last column as the pivot values and cross out rows to generate the subdeterminant matrix. Miles easier to implement and would make the code alot more readable. Use memcpy to fill the allocated submatrix one row at a time. Use a row pointer and just advance it an extra row if the row you were about to copy is the row with the pivot value. Your method is far too complicated and hard to debug.

I wouldn't use pow(-1, i) either, I'd use ((i%2)?-1:1) instead. The compiler (or you) could optimise that to ((i&1)?-1:1) as well.

Another thing: If the value n passed to the determinant function is 1, you should be returning the value of the only entry in the 1x1 matrix and not 0 as the determinant. And, don't use single letter variable names. Use "numRowsColumns" or "size" or something. I can accept single letter variables for loop counters but even then I'd prefer row, column in the above code.

 

[aneeshm]

I have a feeling that we're doing someone's homework.

I have a feeling someone is not very intuitive.