Overflow multiplying matrices

This is a discussion on Overflow multiplying matrices within the C Programming forums, part of the General Programming Boards category; Hello, I seem to have an overflow that is giving me negative numbers instead of positive numbers. I tried using ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    12

    Overflow multiplying matrices

    Hello, I seem to have an overflow that is giving me negative numbers instead of positive numbers. I tried using long long int arrays and it is an overflow. The program works for multiplying matrices when they are small numbers and low dimensions but not when I do a 100 x 150 matrix with numbers that are in the ten thousands.

    Code:
    #include<stdio.h>
    #include"global.h"
    #include<string.h>
    
    void read_array(FILE *fp, FILE *fp2, long int array1[][NUM_COLUMN], long int array2[][NUM_COLUMN],
    				int row1, int column1, int row2, int column2);
    void print_array(long int array3[][NUM_COLUMN], int row1, int column1, int row2, int column2);
    void multiply_array(long int array1[][NUM_COLUMN], long int array2[][NUM_COLUMN], long int array3[][NUM_COLUMN],
    					int row1, int column1, int row2, int column2);
    
    int main(int argc, char **argv){
    	char txt[]=".txt";
    	long int ia[NUM_ROW][NUM_COLUMN];
    	long int ib[NUM_ROW][NUM_COLUMN];
    	long int ic[NUM_ROW][NUM_COLUMN];
    	FILE *fp;
    	FILE *fp2;	
    	int col1,col2, rowa,rowb;
    	/* checks for 3 arguments example [lab8 matrix_a.txt matrix_b.txt] */
    	if(argc!=3){
    		/*if(strstr(argv[1],txt)!=0){
    			printf("Usage: &#37;s matrix_(letter).txt\n", argv[1]);
    		}else{*/
    			printf("Usage: %s filename2.txt\n", argv[1]);
    			return -1;
    		//}
    	}	
    	/* checks for .txt extension */
    	if((strstr(argv[1],txt)!=0) && (strstr(argv[2],txt)!=0)){
    		fp = fopen(argv[1], "r");
    		fp2 = fopen(argv[2], "r");
    		if((fp!=0)&&(fp!=0)){
    				fseek(fp, 0, SEEK_SET);
    				fseek(fp2, 0, SEEK_SET);
    				fscanf(fp, "%d %d", &rowa, &col1);
    				fscanf(fp2, "%d %d", &rowb, &col2);	
    				read_array(fp, fp2, ia, ib, rowa, col1, rowb, col2);
    				multiply_array(ia, ib, ic, rowa, col1, rowb, col2);
    				if(col1==rowb)
    					print_array(ic, rowa, col1,rowb, col2);
    				fclose(fp);
    				fclose(fp2);
    		}else{
    			printf("%s and %s Not Open\n", argv[1], argv[2]);
    			exit(-1);
    		}		
    	}
    	else
    		printf("Unrecognized Arguments, files require *.txt extension");
    
    	return 0;
    }/* main()*/
    
    void read_array(FILE *fp, FILE *fp2, long int array1[][NUM_COLUMN], long int array2[][NUM_COLUMN],
    				int row1, int column1, int row2, int column2){
    	int i,j;
    	//printf("row1 = %d\n", row1);
    	//printf("row2 = %d\n", row2);
    	//printf("column1 = %d\n", column1);
    	//printf("column2 = %d\n", column2);
    
    	for(i=0;i<row1;i++){
    		for(j=0;j<column1;j++)		
    			fscanf(fp,"%d", &array1[i][j]);	
    		fscanf(fp,"\n");
    	}
    	for(i=0;i<row2;i++){
    		for(j=0;j<column2;j++)
    			fscanf(fp2,"%d", &array2[i][j]);				
    		fscanf(fp2,"\n");
    	}
    }
    void print_array(long int array3[][NUM_COLUMN], int row1, int column1, int row2, int column2){
    	int i,j;
    	for(i=0;i<row1;i++){
    		for(j=0;j<column2;j++)
    			printf("%d ", array3[i][j]);
    		printf("\n");
    	}
    
    }
    
    void multiply_array(long int array1[][NUM_COLUMN], long int array2[][NUM_COLUMN], long int array3[][NUM_COLUMN],
    					int row1, int column1, int row2, int column2){
    
    	int i, j, k;
    	long int sum;
    	if(column1==row2){
    		for (i = 0; i < row1; i++) {
    			for (j = 0; j < column2; j++) {
    				sum = 0;
    				for (k = 0; k < row2; k++) {
    					sum += array1[i][k] * array2[k][j];
    				}
    				array3[i][j] = sum;
    			}
    		}
    	}else{
    		printf("Error in Matrix Multiplication\n");
    		printf("Cannot multiply when Column1 does not match with Row2 A[%d][%d] B[%d][%d]\n", row1, column1, row2, column2);
    	}
    }

    NUM_ROW and NUM_COLUMN defined in global.h as 250 for each.

    Could anyone help? Thanks in advance.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    				for (k = 0; k < row2; k++) {
    					sum += array1[i][k] * array2[k][j];
    				}
    Yes, I expect that if the numbers are in the 10's of thousands, this will overflow - after all, you are adding up numbers that are in the 10-100M range, and you only need a bit beyond 2000M to overflow.

    My solution would be to use double's instead of integers - they cope with a range of about +/-1E+/-300, so you should have a fair bit more margin.

    Long long int would work too, but it's likely that there will be little benefit from that (aside from a few more of the bottom digits being precise).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    unsigned never hurts, IF you know there won't be any negative numbers.

    So the question is: is overflow supposed to happen? Are the answers actually bigger than 2billion-and-change?

  4. #4
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Those arrays are getting pretty big for the stack,

    Assuming a long int is 4 bytes, then

    Code:
    long int ia[NUM_ROW][NUM_COLUMN];
    is (NUM_ROW * NUM_COLUMN) * 4 bytes on the stack. Which is like 244KB (when NUM_ROW, NUM_COLUMN = 250), and you have three of them. Perhaps use the heap (ie, malloc() / free()).

    Narrow the problem down, and try a couple of hard-coded matrices and see if that is the problem. Meaning, remove everything but void multiply_array() -- of course don't throw it away!

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by tabstop View Post
    unsigned never hurts, IF you know there won't be any negative numbers.

    So the question is: is overflow supposed to happen? Are the answers actually bigger than 2billion-and-change?
    100-150 numbers in the 10000 range, yes, I'd expect that to overflow. I'm a bit surprised it overflows on long long - that shouldn't be the case for those sort of numbers. But I still think that double would be a better solution.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by matsp View Post
    100-150 numbers in the 10000 range, yes, I'd expect that to overflow. I'm a bit surprised it overflows on long long - that shouldn't be the case for those sort of numbers. But I still think that double would be a better solution.

    --
    Mats
    He's using MSVisual Studio per the other thread -- he doesn't have a long long (which is why the example is using long). But int64 or whatever MS calls its 64-bit type might work.

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    12
    Double doesn't work, still have an overflow. I have a stack overflow when I use long long btw.
    I attached the input files that I am using, I forgot to attach them in my other post.

    As far as the malloc() and free(). I have not learned to use those, perhaps you could provide a good site or some info on how to use them? Thanks.
    Attached Files Attached Files

  8. #8
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > I have a stack overflow when I use long long btw.
    That's because the problem I outlined in my post,

    Assuming long long is 8 bytes, then you're using
    (250 * 250) * 8 bytes, which is like 488KB. And again, you have 3 arrays so that's like 1464KB (~1.4MB). The stack space is very limited, from memory it's about 1MB default.

    Use malloc()/free() to allocate and free the arrays.

  9. #9
    Registered User
    Join Date
    Nov 2008
    Posts
    12
    Quote Originally Posted by zacs7 View Post
    > I have a stack overflow when I use long long btw.
    That's because the problem I outlined in my post,

    Assuming long long is 8 bytes, then you're using
    (250 * 250) * 8 bytes, which is like 488KB. And again, you have 3 arrays so that's like 1464KB (~1.4MB). The stack space is very limited, from memory it's about 1MB default.

    Use malloc()/free() to allocate and free the arrays.
    Correct, I was trying to answer all the posts in my one post. I will have to look into malloc()/free() and get back to you, since I am not sure how to use them. Thanks for your input, any other suggestions?

  10. #10
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Either a BigNum library like gmp (http://gmplib.org/) or a different method of multiplication for matrices. I don't know of any nor how it'd work because you still need the final answer, but there might be some.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Making it only as big as required (150x200) with __int64 I just managed to squeeze it in. The numbers are in the 44.5B range, so you definitely need eight bytes.

  12. #12
    Registered User
    Join Date
    Nov 2008
    Posts
    12
    Here is my output for the matrices used in matrix_a.txt and matrix_b.txt. I am not even really sure if my output is right according to the what the actual result should be as far as being a 100 x 200 matrix. I will try the link you suggested, thanks
    Attached Files Attached Files

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow errors in 3 areas
    By ulillillia in forum C Programming
    Replies: 13
    Last Post: 04-29-2007, 04:20 PM
  2. Signed Char Overflow
    By coder8137 in forum C Programming
    Replies: 5
    Last Post: 11-17-2006, 08:25 AM
  3. multiplying matrices
    By RenderedAwake in forum C++ Programming
    Replies: 2
    Last Post: 03-22-2005, 11:36 PM
  4. Multiplying matrices
    By Star Lancer in forum C++ Programming
    Replies: 7
    Last Post: 05-22-2003, 07:07 AM
  5. Problem multiplying rotation matrices together
    By Silvercord in forum A Brief History of Cprogramming.com
    Replies: 20
    Last Post: 03-04-2003, 09:20 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21