LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 06-15-2008, 08:26 AM   #1
gregorian
Member
 
Registered: Apr 2006
Location: India
Posts: 473

Rep: Reputation: 33
Matrix determinant program in C++ and C. Executable 25 times larger than the other.


I wrote a program to calculate the determinant of a matrix in C++ and C. The C++ program produces an executable which is 466kB and the C program produces an executable 17kB in size. They both operate by recursion. However the C program treats the matrix as a single dimensional array while the C++ program treats the matrix as a two dimensional array. I don't know why there is such a huge difference in size of the executable and I want to reduce the size of the C++ executable.

determinant.cpp
Code:
#include <iostream>
#include <cmath>
using namespace std;

int** submatrix(int **matrix, int order, int i, int j);
int determinant(int **matrix, int order);

int main()
{
	int i, j, order;
	int **matrix;

	cout<<"Enter the order of the matrix: ";
	cin>>order;

	matrix = new int* [order];	//Allocate memory for pointers (each pointer represents a row)
    cout<<"Enter the elements of the matrix: \n";
	for(i = 0; i < order; i++) {
			matrix[i] = new int[order]; //Each row contains 'order' number of elements
		for(j = 0; j< order; j++)
			cin>>matrix[i][j];
	}

	cout<<"\nDeterminant:"<<determinant(matrix, order);
	
	return 0;
}

int** submatrix(int **matrix, int order, int i, int j)
{

	int **subm;
	int p, q;				// Indexes for matrix
	int a = 0, b;		// Indexes for subm
	subm = new int* [order - 1];

	for(p = 0; p < order; p++) {
		if(p==i) continue;				//Skip ith row
			subm[a] = new int[order - 1];

			b = 0;

		for(q = 0; q< order; q++) {
				if(q==j) continue;		//Skip jth column
			subm[a][b++] = matrix[p][q];
		}
		a++; //Increment row index
	}
	return subm;
}

int determinant(int **matrix, int order)
{
	if(order == 1)
		return **matrix; //Return the element if the matrix is of order one

	int i;
	int det = 0;
	for(i = 0; i < order; i++)
		det += static_cast<int>(pow(-1.0,(int)i)) * matrix[i][0] * determinant(submatrix(matrix, order, i, 0), order - 1);
	return det;
}
determinant.c
Code:
#include <stdio.h>
#include <conio.h>
#include <math.h>

int* submatrix(int mat[], int m, int k, int order);
int determinant(int mat[],int order);

int main()
{
    int i;
    int mat[] = {0,0,2,3,4,5,6,7,8};
    
    int det = determinant(mat,3);
    
    printf("%d",det);
         
    getch();
    return 0;
}

int* submatrix(int mat[], int m, int n, int order)
{
     int* sub = (int*)malloc(order*order*sizeof(int));
     int i,j;
     
     for(i = 0, j=0; i<(order+1)*(order+1) && j<order*order; i++)
     {
             if(i>=(order+1)*m && i< (order+1)*(m+1))
                               i = (order+1)*(m+1);
                          
             if(i>=n)
                     if((i-n)%(order+1)==0)        
                            continue;
                                                                  
             *(sub + j++) = mat[i];
     }     
    return sub;     
}     

int determinant(int mat[], int order)
{    
    if(order==1)
                return mat[0];
    
    int i,d = 0;
        
    for(i=0; i< order; i++)
             d += (int)pow(-1,i)*mat[i]*determinant(submatrix(mat, 0, i,order -1), order-1 );
       
    return d;
}
 
Old 06-15-2008, 01:55 PM   #2
osor
HCL Maintainer
 
Registered: Jan 2006
Distribution: (H)LFS, Gentoo
Posts: 2,450

Rep: Reputation: 70
Quote:
Originally Posted by gregorian View Post
I don't know why there is such a huge difference in size of the executable and I want to reduce the size of the C++ executable.
It’s probably because the size of the extra code required to handle iostreams rather than plain-old stdio. Besides which, the two code samples are not exactly “equal” in terms of verbosity. If you really wanted to know, you could examine the assembly output of each one (gcc -S).

Btw, the algorithm you are using for determinants (I believe) scales as O(n!) (i.e., damn slow). There are many better algorithms out there.
 
Old 06-15-2008, 02:56 PM   #3
knudfl
LQ 5k Club
 
Registered: Jan 2008
Location: Copenhagen, DK
Distribution: pclos2014.08, Slack14.1 DebWheezy, +50+ other Linux OS, for test only.
Posts: 14,284

Rep: Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664
'g++ determinant.cpp' ==> I get 9.2KB ( 5KB stripped )
Used gcc-c++ 4.1.1-4pclos2007.
'./a.out' : "Enter the order of the matrix:"

Rgds
 
Old 06-15-2008, 11:45 PM   #4
Dan04
Member
 
Registered: Jun 2006
Location: Texas
Distribution: Ubuntu
Posts: 207

Rep: Reputation: 37
Quote:
Originally Posted by osor View Post
Btw, the algorithm you are using for determinants (I believe) scales as O(n!) (i.e., damn slow). There are many better algorithms out there.
Yeah. IIRC, doing an LU factorization makes it only O(n³).
 
Old 06-16-2008, 09:39 AM   #5
gregorian
Member
 
Registered: Apr 2006
Location: India
Posts: 473

Original Poster
Rep: Reputation: 33
I don't really know the big O notation yet, but doesn't that decide the speed of the algorithm? It's not that I'm looking for a better algorithm, I just wanted to know why two programs with the same logic resulted in such a large difference in size.
Quote:
It’s probably because the size of the extra code required to handle iostreams rather than plain-old stdio
That's right. I just replaced cout and cin with equivalent printf and scanf statements and the size dropped to 47k.
Quote:
'g++ determinant.cpp' ==> I get 9.2KB
I used Dev C++ on windows which uses g++ using the MinGW port. May I know why is there such a large difference in size between the Linux binary and the Windows executable? Is the Linux binary dependent on some libraries in Linux?

Thank you all for your help.
 
Old 06-16-2008, 09:43 AM   #6
huwnet
Member
 
Registered: Jan 2006
Location: England
Distribution: Arch
Posts: 119

Rep: Reputation: Disabled
I believe there are additional windows libraries which dev-c++ includes by default, some of which you may be able to remove. Should be in the linker settings somewhere
 
Old 06-16-2008, 12:18 PM   #7
gregorian
Member
 
Registered: Apr 2006
Location: India
Posts: 473

Original Poster
Rep: Reputation: 33
I found an option called "Strip executable" which reduced the size of the executable to about half of it's original size, but that's still pretty large compared to 9kb. Why is linux binary much smaller? Besides what do you lose if you enable the option "Strip executable"? I couldn't find much by googling the option..
 
Old 06-16-2008, 11:42 PM   #8
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,455

Rep: Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172
Lots of things can affect the size of an executable-file.

Quite honestly... ask yourself... "why do I care?"

Okay, if it's intellectual-curiosity, go ahead and be curious. But otherwise, the physical size of an executable file makes precious little difference. High-level languages often include a fairly large "foundation" of code that they put into most things, and trying to minimize the size of this is usually just not an implementation priority for the language-designers; it offers no practical payback.
 
Old 06-17-2008, 01:14 AM   #9
gregorian
Member
 
Registered: Apr 2006
Location: India
Posts: 473

Original Poster
Rep: Reputation: 33
It's out of intellectual curiosity that I want to know the answer. I want to know why the Linux binary is so much smaller than even the stripped executable under windows. And also what do I lose if it's a stripped executable.
 
Old 06-17-2008, 02:19 AM   #10
knudfl
LQ 5k Club
 
Registered: Jan 2008
Location: Copenhagen, DK
Distribution: pclos2014.08, Slack14.1 DebWheezy, +50+ other Linux OS, for test only.
Posts: 14,284

Rep: Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664Reputation: 2664
'man strip' has a very short explanation.
There are a few more words in Wikipedia :
http://en.wikipedia.org/wiki/Strip_%28Unix%29
Quote:
In Unix and Unix-like operating systems, the strip program removes all debugging and symbol information from executable binary programs and object files, thus potentially resulting in better performance and sometimes significantly less disk space usage.
It is part of the GNU Binary Utilities (binutils), and has been ported to other operating systems including Microsoft Windows.
Rgds
 
Old 06-17-2008, 01:44 PM   #11
gregorian
Member
 
Registered: Apr 2006
Location: India
Posts: 473

Original Poster
Rep: Reputation: 33
Thank you knudfl. Could you answer this query too? Why is the Linux binary is much smaller than even the stripped executable under windows?

Last edited by gregorian; 06-17-2008 at 01:45 PM.
 
Old 06-17-2008, 07:52 PM   #12
fantas
Member
 
Registered: Jun 2007
Location: Bavaria
Distribution: slackware, xubuntu
Posts: 143

Rep: Reputation: 22
AFAIK, mingw always links system libraries statically (compiled into the binary), where under Linux gcc defaults to linking them dynamically (loaded from dll/so when running, so smaller size, but, FWIW, more dependencies).
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
awk convert column matrix to square matrix? johnpaulodonnell Programming 4 04-30-2008 02:45 PM
Matrix linux program Kyrocera Linux - General 1 02-07-2007 04:51 AM
Running a program at specific times only i666an Suse/Novell 4 04-02-2006 08:49 AM
help - Renaming a program executable to another name. kaydknight Linux - Software 3 12-08-2005 05:09 AM
program loading times kibitzer99 Linux - Software 1 01-24-2005 12:03 PM


All times are GMT -5. The time now is 03:22 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration