Why is it printing a wrong answer?

Question

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

double** findminor(double** a, int n, int flag) {
    double** minor = malloc((n - 1) * sizeof(double*));
    int r = 1, c = 0;

    for (int i = 0; i < (n - 1); i++) {
        *(minor + i) = malloc((n - 1) * sizeof(double*));

        for (int j = 0; j < (n - 1); j++) {
            if (c != flag) {
                *(*(minor +i ) + j) = *(*(a + r) + c);
            }
            else {
                c++;
                *(*(minor+i)+j)=*(*(a+r)+c);
            }

            c++;
        }

        r++;
    }

    return minor;
}

void freeMinor(double** minor, int n) {
    for (int i = 0; i < (n - 1); i++) {
        free(*(minor + i));
    }

    free(minor);
}

double compute_det(double** a, int n) {
    if (n == 1) {
        return (double)**a;
    }
    
    double result = 0.0;
    double sign = 1.0;
    double** minor = malloc(n * sizeof(double*));

    for (int i = 0; i < n; i++) {
        minor = findminor(a, n, i);
        result += sign * *(*(a) + i) * compute_det(minor, n - 1 - i);
        sign = -1.0;
        freeMinor(minor, n);
    }
  
    return abs(result);
}

void freeMatrix(double** a, int n) {
    for (int i = 0; i < n; i++) {
        free(*(a + i));
    }
    
    free(a);
}

int main(void) {
    int n;
    printf("Input dimensions: ");
    scanf("%d", &n);
    double** a = malloc(n * sizeof(double*));

    for (int i = 0; i < n; i++) {
        *(a + i) = malloc(n * sizeof(double));

        for (int j = 0; j < n; j++) {
            scanf("%lf ", (*(a + i) + j));
        }
    }
    
    printf("%.lf\n", compute_det(a, n));
    freeMatrix(a, n);

    return 0;
}

Hey, so I'm trying to code a program that computes a determinant for any size. I'm not sure where I'm going wrong because when I pass in these values, which are in a .in file I'm getting 15 instead of 105

However, I'm also getting a memory leak. Is this what makes my code face errors?

==28233== Memcheck, a memory error detector
==28233== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==28233== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==28233== Command: ./det
==28233== 
==28233== Invalid read of size 8
==28233==    at 0x10929B: findminor (in /home/u6480784/a3/det/det)
==28233==    by 0x1093FE: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233==  Address 0x4a4c800 is 0 bytes after a block of size 32 alloc'd
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x109572: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== Invalid read of size 8
==28233==    at 0x10929B: findminor (in /home/u6480784/a3/det/det)
==28233==    by 0x1093FE: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233==  Address 0x4a4ca38 is 0 bytes after a block of size 24 alloc'd
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x10923B: findminor (in /home/u6480784/a3/det/det)
==28233==    by 0x1093FE: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== Invalid read of size 8
==28233==    at 0x1092F1: findminor (in /home/u6480784/a3/det/det)
==28233==    by 0x1093FE: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233==  Address 0x4a4ca38 is 0 bytes after a block of size 24 alloc'd
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x10923B: findminor (in /home/u6480784/a3/det/det)
==28233==    by 0x1093FE: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== Invalid read of size 8
==28233==    at 0x1092F1: findminor (in /home/u6480784/a3/det/det)
==28233==    by 0x1093FE: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233==  Address 0x4a4c800 is 0 bytes after a block of size 32 alloc'd
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x109572: main (in /home/u6480784/a3/det/det)
==28233== 
Input dimensions: 15
==28233== 
==28233== HEAP SUMMARY:
==28233==     in use at exit: 88 bytes in 8 blocks
==28233==   total heap usage: 48 allocs, 40 frees, 2,376 bytes allocated
==28233== 
==28233== 0 bytes in 1 blocks are definitely lost in loss record 1 of 4
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x1093DA: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== 16 bytes in 3 blocks are definitely lost in loss record 2 of 4
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x1093DA: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== 32 bytes in 1 blocks are definitely lost in loss record 3 of 4
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x1093DA: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== 40 bytes in 3 blocks are definitely lost in loss record 4 of 4
==28233==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28233==    by 0x1093DA: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x10943D: compute_det (in /home/u6480784/a3/det/det)
==28233==    by 0x1095E3: main (in /home/u6480784/a3/det/det)
==28233== 
==28233== LEAK SUMMARY:
==28233==    definitely lost: 88 bytes in 8 blocks
==28233==    indirectly lost: 0 bytes in 0 blocks
==28233==      possibly lost: 0 bytes in 0 blocks
==28233==    still reachable: 0 bytes in 0 blocks
==28233==         suppressed: 0 bytes in 0 blocks
==28233== 
==28233== For lists of detected and suppressed errors, rerun with: -s
==28233== ERROR SUMMARY: 34 errors from 8 contexts (suppressed: 0 from 0)

Is there anything I could do?

For any pointer (or array) `p` and index `i`, the expression `*(p + i)` is *exactly* equal to `p[i]`. The latter is much easier to read, write and undesrstand. — Some programmer dude, Jun 27 '22 at 17:47
Also build with debug info (add `-g` when building) and Valgrind will be able to report exact line numbers where it detects problems. Use it for further debugging sessions, where you for example check all indexes you use, and make sure they are in range. — Some programmer dude, Jun 27 '22 at 17:49
Also, you have `double **minor = malloc(...);` followed by `minor = findminor(...);`. What happens with the pointer returned by that initial call to `malloc`? — Some programmer dude, Jun 27 '22 at 17:51
This is often wrong: `scanf("%lf ", (*(a+i)+j));` please remove the trailing space so `scanf("%lf", (*(a+i)+j));` — Weather Vane, Jun 27 '22 at 17:52
The cast in `return (double) **a;` is superfluous; it might be better to write `return a[0][0];` to indicate the value returned is the zero/zero element of the matrix. — Jonathan Leffler, Jun 27 '22 at 17:53
@Someprogrammerdude, yeah, that was useless. I just fixed it. No leaks are possible. However, I'm still not getting the expected answer for some reason. I tried to trace it on paper, and it seems fitting to me for some reason. Is there something wrong with the way I'm adding? Kind of unsure about that. But I can't think of a solution. I even tried removing i, but I'm only getting 0. — James Andrews, Jun 27 '22 at 17:59
Should `sign = -1.0;` be `sign *= -1.0;` although the ouput is stil `15`? — Weather Vane, Jun 27 '22 at 18:04
Even for a pointer, `a[r][c]` is perfectly valid. Teachers that require explicit pointer-arithmetic syntax should have a stern talking to. — Some programmer dude, Jun 27 '22 at 18:05
@WeatherVane yeah just tried that after compiling it. Still getting the same output. However, it was a required change. — James Andrews, Jun 27 '22 at 18:09

score 1 · Answer 1 · edited Jun 28 '22 at 00:12

To get this working, I've changed the unreadable pointer notation to array notation, you can change it back. I've also made the assumption that a matrix is always at least 2x2 and set that as the recursion limit.

The code now outputs -105.000000 for the given input.

Some errors in findminor() were:

Allocation of sizeof(double*) in the loop. This will cause a fault with 32-bit pointers
The int c=0 should be inside the loop, was initialised once only
The loop control is off-by-one
You copy the array element whether or not it's the 'skipped' column
The wrong variable is used to index
c is incremented once or twice

Some changes in compute_det() were:

Fault with sign = -1.0 which should be sign *= -1.0
Remove memory leak of double** minor = malloc(n*sizeof(double*)); outside the loop
Incorrect matrix size passed to recursion
Removed the abs from return abs(result), even return fabs(result) gives the wrong answer

Finally in main() removed the trailing space in scanf. Please see What is the effect of trailing white space in a scanf() format string?

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

double** findminor(double** a, int n, int flag){
    double** minor = malloc((n-1)*sizeof(double*));
    int r = 1;
    for (int i=0;i<(n-1);i++){
        int c = 0;      // error here c reset outside of loop
        minor[i] = malloc((n-1)*sizeof(double));  // error *double
        for (int j=0;j<n;j++){
            if(j != flag){
                minor[i][c] = a[r][j];
                c++;
            }
        }
        r++;
    }
    return minor;
}

void freeMinor(double** minor, int n){
    for(int i=0;i<(n-1) ;i++){
        free(minor[i]);
    }
    free(minor);
}


double compute_det(double** a, int n) {
    if(n == 2)
        return a[0][0] * a[1][1] - a[1][0] * a[0][1];

    double result = 0.0;
    double sign = 1.0;
    for(int i=0;i<n;i++){
        double** minor = findminor(a, n, i);
        result += sign * a[0][i] * compute_det(minor, n-1); //here
        sign *= -1.0;
        freeMinor(minor, n);
    }
    return result;
}

void freeMatrix(double** a, int n){
    for(int i=0;i<n;i++){
        free(a[i]);
    }
    free(a);
}

int main(void) {
    int n;
    printf("Input dimensions: ");
    scanf("%d", &n);
    double** a = malloc(n*sizeof(double*));
    for (int i=0;i<n;i++){
        a[i]=malloc(n*sizeof(double));
        for (int j=0;j<n;j++){
            scanf("%lf", &a[i][j]);
        }
    }
    printf("%lf\n", compute_det(a, n));
    freeMatrix(a, n);
    return 0;
}

Why is it printing a wrong answer?

1 Answers1