Trying to multiply two large matrixes of dimension 1000*1000 causes Segmentation Fault

Question

Trying to multiply two matrices of the dimension 1000*1000 . However, trying to do so causes Segmentation fault. what is possibly causing this and how to resolve it?

#include <stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
clock_t t;
    t = clock();
   long int a[1000][1000], b[1000][1000], result[1000][1000], r1=1000, c1=1000, r2=1000, c2=1000, i, j, k;

   // Column of first matrix should be equal to column of second matrix and
  /*  while (c1 != r2)
    {
        printf("Error! column of first matrix not equal to row of second.\n\n");
        printf("Enter rows and column for first matrix: ");
        scanf("%d %d", &r1, &c1);
        printf("Enter rows and column for second matrix: ");
        scanf("%d %d",&r2, &c2);
    }
*/

    // Storing elements of first matrix.
    printf("\nEnter elements of matrix 1:\n");
    for(i=0; i<r1; ++i)
        for(j=0; j<c1; ++j)
        {
          a[i][j]=rand()%20;
        }

    // Storing elements of second matrix.
    printf("\nEnter elements of matrix 2:\n");
    for(i=0; i<r2; ++i)
        for(j=0; j<c2; ++j)
        {
            b[i][j]=rand()%20;
        }

    // Initializing all elements of result matrix to 0
    for(i=0; i<r1; ++i)
        for(j=0; j<c2; ++j)
        {
            result[i][j] = 0;
        }

    // Multiplying matrices a and b and
    // storing result in result matrix
    for(i=0; i<r1; ++i)
        for(j=0; j<c2; ++j)
            for(k=0; k<c1; ++k)
            {
                result[i][j]+=a[i][k]*b[k][j];
            }
 // Displaying the result
    printf("\nOutput Matrix:\n");
    for(i=0; i<r1; ++i)
        for(j=0; j<c2; ++j)
        {
            printf("%ld  ", result[i][j]);
            if(j == c2-1)
                printf("\n\n");
        }
t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds

    printf("\n \nfunction took %f seconds to execute \n", time_taken);
    return 0;
}

The `if(j == c2-1)` bit in the printing routine isn't needed - you can move `printf("\n\n");` to just after the inner loop and it'll do the same thing — Chris Turner, Aug 06 '18 at 10:37

anoopknr · Answer 1 · 2018-08-06T13:14:56.197

3

You need to use dynamic memory allocation in the case of there large memory allocations. Stack memory cannot handle these large memory requirements.

You can solve this using Dynamic memory allocation. Try :-

int (*a)[r1][c1] = malloc(sizeof *a);
int (*b)[r2][c2] = malloc(sizeof *b);
int (*result)[r1][c2] = malloc(sizeof *result);

And access elements using :-

(*result)[i][j] ;
(*a)[i][k] ;
(*b)[k][j] ;

Try this code :-

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
    clock_t t;
    t = clock();
    int r1 = 1000, c1 = 1000, r2 = 1000, c2 = 1000, i, j, k;

    // Dynamic allocation.

    int(*a)[r1][c1] = malloc(sizeof *a);
    int(*b)[r2][c2] = malloc(sizeof *b);
    int(*result)[r1][c2] = malloc(sizeof *result);

    // Storing elements of first matrix.
    printf("\nEnter elements of matrix 1:\n");
    for (i = 0; i < r1; ++i)
    {
        for (j = 0; j < c1; ++j)
        {
            (*a)[i][j] = rand() % 20;
        }
    }

    // Storing elements of second matrix.
    printf("\nEnter elements of matrix 2:\n");

    for (i = 0; i < r2; ++i)
    {
        for (j = 0; j < c2; ++j)
        {
            (*b)[i][j] = rand() % 20;
        }
    }
    // Initializing all elements of result matrix to 0
    for (i = 0; i < r1; ++i)
    {
        for (j = 0; j < c2; ++j)
        {
            (*result)[i][j] = 0;
        }
    }
    // Multiplying matrices a and b and
    // storing result in result matrix
    for (i = 0; i < r1; ++i)
        for (j = 0; j < c2; ++j)
            for (k = 0; k < c1; ++k)
            {
                (*result)[i][j] += (*a)[i][k] * (*b)[k][j];
            }
    // Displaying the result
    printf("\nOutput Matrix:\n");
    for (i = 0; i < r1; ++i)
        for (j = 0; j < c2; ++j)
        {
            printf("%d  ", (*result)[i][j]);
            if (j == c2 - 1)
                printf("\n\n");
        }
    t = clock() - t;
    double time_taken = ((double)t) / CLOCKS_PER_SEC; // in seconds

    printf("\n \nfunction took %f seconds to execute \n", time_taken);

    free(a);
    free(b);
    free(result);
    return 0;
}

Output :-

.......................................................................
 91717  92211  96529  90328  89167  88774  90433  88320  93834  89054  92225  92226  89919  88005  90772  90436  89091  92446  88477  94143  95777  88805  88487  89082  92528  88899  93436  90423  88637  90254  91569  87516  89079  91309  93554  86422  90069  91096  86981  95437  92805  88638  89828  88568  89607  88025  91700  88144  90401  91147  88284  92998  90959  85520  92640  92247  95616  90006  87248  89726  91751  90077  90543  91489  92399  90828  89026  92866  91548  87131  88450  93247  87748  90734  90228  91972  93300  92444  91592  85842  91167  89554  91144  90536  91256  89646  92815  91476  91863  94836  95462  87122  91735  96059  91312  90480  93306  



function took 6.060788 seconds to execute

Note : Full output can't be included since too large.

Don't forget to free allocated memory.

edited Aug 06 '18 at 13:14

answered Aug 06 '18 at 10:53

anoopknr

3,177
2
23
33

In your example you are not freeing the memory properly. – Osiris Aug 06 '18 at 11:08
*Stack memory cannot handle these large memory requirements*. Yes it can. You simply must pass the appropriate option to the compiler. – Serge Ballesta Aug 06 '18 at 11:40
This does not allocate a matrix (aka 2D array). A pointer is not an array. Why not use a 2D array, but use a much more complicated jagged array? – too honest for this site Aug 06 '18 at 12:19
@Osiris In my code freeing is there at last part – anoopknr Aug 06 '18 at 12:34
@toohonestforthissite yes I am allocating for 2D matrix . You might not noticed the line `a[i] = (int *)malloc(c1 * sizeof(int));` in for-loops – anoopknr Aug 06 '18 at 12:35
@anoopknr Yes but you are not freeing everything you have allocated. You have to free every `a[i]`, `b[i]` and `result[i]` too. – Osiris Aug 06 '18 at 12:36
@anoopknr: I said that's not a 2D array and it's true! A 2D array is an array of arrays, not an array of pointers. If a pointer was an array, it would be called "array", not "pointer". Please consult your C book. As you are at it,: don't cast `void *` to pointers. It's strongly discouraged like every other unnecessary cast, as it can keep your compiler from reporting bugs. – too honest for this site Aug 06 '18 at 12:39
@toohonestforthissite So how could I dynamically allocate array of arrays ? – anoopknr Aug 06 '18 at 12:44
using the correct types. Read about VLAs. – too honest for this site Aug 06 '18 at 12:45
@toohonestforthissite Sir , I have modified my answer. Is that a good method ? – anoopknr Aug 06 '18 at 12:59
@chux that is from the question code. Removed that. – anoopknr Aug 06 '18 at 13:15
Very elegant solution! – Paul Ogilvie Aug 06 '18 at 13:42
This answer is mostly correct, though the complicated array pointer syntax could be simplified. Those who left comments might want to read up on [Correctly allocating multi-dimensional arrays](https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays). – Lundin Aug 06 '18 at 14:02
@anoopknr I didn't check everything, but the types seem to be ok now. Just use the correct type for array indexes, not `int`. – too honest for this site Aug 06 '18 at 14:52

0___________ · Answer 2 · 2018-08-06T11:17:45.260

1

First of all do not allocate such a huge amounts of memory as the local function variables. Their storage location (usually the stack) is relatively small comparing to the size of the heap You just run out of the automatic variables storage.. Instead allocate it dynamically

int *a = malloc(r1 * c1 * sizeof(*a));
int *b = malloc(r2 * c2 * sizeof(*b));
int *result = malloc(r2 * c2 * sizeof(*result));

printf("\nEnter elements of matrix 1:\n");
for(i=0; i<r1; ++i)
    for(j=0; j<c1; ++j)
    {
      a[i * c1 + j]=rand()%20;
    }


....

You can have another allocation strategy to have more natural indexing.

edited Aug 06 '18 at 11:17

answered Aug 06 '18 at 10:32

0___________

60,014
4
34
74

Not the comlete sentence – 0___________ Aug 06 '18 at 10:38
Can you please post a complete answer? Trying the pointer allocation causes errors in other segments of the code, please rectify it ! – OBX Aug 06 '18 at 10:39
1

result should be `malloc()`ed as `r1 * c2` and the assignment sphould be `result[i * c2 + j]` (the latter should be the same for `b` (not `ba` :-) ) – Ingo Leonhardt Aug 06 '18 at 10:50
1

@OBX - I am not a free program writing service. You have the direction - follow it. – 0___________ Aug 06 '18 at 11:17
This does not allocate a matrix (aka 2D array). – too honest for this site Aug 06 '18 at 12:18
Subtle note: There is an advantage of `sizeof(*a) * r1 * c1` vs. `r1 * c1 * sizeof(*a)`. Example: Consider `int r1, c1`. `sizeof(*a) * r1 * c1` insures that the math is done with the wider of `size_t` and `int`. – chux - Reinstate Monica Aug 06 '18 at 13:05
@chux all indexing variables should be size_t. But I am not goint to write the entire program for him. To be honest I have not even taken a look. But I have changed it. Thanks – 0___________ Aug 06 '18 at 13:07

Trying to multiply two large matrixes of dimension 1000*1000 causes Segmentation Fault

2 Answers2