Matrix determinant program in C++ and C. Executable 25 times larger than the other.

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

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;
}

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.

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?

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

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..

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.

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.

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.

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).

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.