Linking Problems :D

killer9012 · #1 28-Oct-2006, 15:02

CPP / C++ / C Code:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

int Binarysearch( int [], int, int, int, int);
void showheader( int );
void showrow( int[], int, int, int, int);

int main()
{
    const int tablewidth = 15;
    int a[ tablewidth ], cle, results;

    for( int i = 0; i < tablewidth; i++)
       a[i] = 2 * i; // places certain data in the table

    cout << "Enter a number between 0 and 28: ";
    cin >> cle;

    showheader(tablewidth);
    results = Binarysearch(a, cle, 0, tablewidth - 1, tablewidth);
    
    if(results != -1)
        cout << '\n' << cle << " found in element "
             << results << endl;
    else
        cout <<'\n' << cle << " not found" << endl;

    return 0;
}

    //Binarysearch
int Binarysearch( int b[], int clesearch, int bottom, int top, int width )
{
    int center;

    while( bottom<= top)
    {
     center = (bottom + top)/2;

     showrow(b, bottom, center, top, width);

     if(clesearch == b[center] )
        return center;
     else if (clesearch < b[center])
	top = center - 1;    // search bottom portion
     else
	bottom = center + 1; // search top portion
}

   return -1; //clesearch not found
}

// show header
void showheader( int width )
{
    cout << "\nHeader:\n";
    for( int i=0; i < width; i++)
	cout << setw(3) << i << ' ';

    cout <<  '\n';

    for(i=1; i<= 4*width; i++)
        cout << '-';

    cout << endl;
}

// show what line is currently being evaluated
void showrow(int b[], int bottom, int center, int top, int width)
{
   for(int i=0; i<width; i++)
	if(i<bottom || i > top)
	    cout << "     ";
	else if (i==center)
	    cout << setw(3) << b[i] << '*';
	else
	    cout << setw(3) << b[i] << ' ';

    cout << endl;
}

2 questions. What would be the maximum size of the array that the program would work with?
How can i count the ammount of comparaisons that the function Binarysearch does to complete its work, and how can i creat an average counter that would display the work it does in a huge array?

TurboPT · #2 28-Oct-2006, 15:44

Case difference: Binary(s)earch, vs. Binary(S)earch.

Make it one way or the other.

Iftikhar · #3 29-Oct-2006, 02:29

The memory is limit. However the amount of memory also depends on in which OS you are working. For e.g in DOS you will have only 640KB of extented memory while in windows you can have more.
For comparison to make intialize a counter before the loop and increment it one by one in comaprison block e.g

Code:

if (A[i] == A[i+1])
{
Swap(,);
counter++;
}

davekw7x · #4 29-Oct-2006, 12:18

Quote:

Originally Posted by killer9012

What would be the maximum size of the array that the program would work with?

Each implementation (compiler/linker/loader) has a default stack size that allows each program/process to have a certain total amount of storage for stack space. Stack space is used for automatic variables (variables, including structs, arrays and other data types declared within a function) and is also used to hold arguments and return addresses for function calls.

Sometimes there are command-line switches that allow the user to change the stack space at compile time. Sometimes this information is not easy to glean from compiler documentation.

You could try the following:

CPP / C++ / C Code:

#include <iostream>
using namespace std;

unsigned long depth   = 0;
double total = 0;

int main()
{
    void junk(void);

    junk();
    return 0; // actually will never return, since recursive calls will
              // cause abnormal program termination
}

void junk()
{
    cout << "Depth level = " << ++depth << flush;
    char array[100000];
    total += 100000;
    cout << ", Total allocated = " << total << endl;
    junk();
}

This little nonsense program calls a function recursively until it runs out of stack space. I put in a couple of global variables so that I could print out the progress and see how much memory could be accessed before the program bombed.

On Windows XP, Borland bcc32 and Microsoft Visual C++, version 6, compilers seem to have a stack space of about a megabyte. (They both get to level 10, with 1000000 bytes allocated before bombing). GNU gcc (version 3.4.4) gets as far as 2000000 bytes before the crash. On my Linux systems (32-bit with gcc version 4.1.1 and 64-bit with gcc version 4.1.1), the program gets to about 12.5 Megabytes before bombing. You can test it with your compiler. I would be mildly interested in knowing the results.

Notice that this has nothing to do with the amount of physical memory or swap space or anything else other than the amount of memory that the compiler is prepared to give to any program.

GNU gcc 4.0 on my Linux 32-bit and 64-bit workstations gets up to level 120 (12.5 Megabytes allocated) before bombing.

If you need arrays larger than these amounts, one way to handle it is with dynamic allocation. (Use new with C++ or malloc() with C). Dynamic allocation gets memory from the system "heap", which is a part of the total system virtual memory, and is, generally, much larger than stack space for a given program.

You can try the following:

CPP / C++ / C Code:

#include <iostream>

using namespace std;

unsigned long depth;// initialized to zero
double total;       // initialized to zero

int main()
{
    void junk(void);

    junk();
    return 0; // actually will never return, since recursive calls will
              // eventially cause program exit
}

void junk()
{
    char *array;
    cout << "Depth level = " << ++depth << flush;
    try {
        array = new char[1000000];
    }
    catch (const bad_alloc&) {
        cout << ", new threw an error; bailing out" << endl;
        exit(1);
    }
    // the following non-standard test works for Microsoft Visual C++ only
#if 0
    if (array == NULL) {
        cout << ", new returned null at this level" << endl;
        exit(1);
    }
#endif
    total += 1000000;
    cout << ", Total allocated = " << total << endl;
    junk();
}

This time, with Windows XP, the program compiled Borland and g++ caught the exception at depth level above 2000 (after allocating about 2 Gigabytes). Note that Microsoft Visual C++ version 6 doesn't comply with the C++ standard and doesn't generate an exception, but it does return NULL when the new operator fails. (This is not standard behavior, and the other compilers do not necessarily return NULL. The proper test is to catch the exception.) With the test for NULL, Microsoft Visual C++ also quit after about 2 Gigabytes.

One important difference: For automatic variables there is (as far as I know) no generally-available, reliable implementation-independent way to catch stack overflows. Some compilers or have command-line options that include extra code for stack bounds testing, but, as far as I can tell, this adds extra overhead. That is, it takes more time to access the array every single time, and, interestingly enough, actually increases stack usage. (But I could be wrong.)

Bottom line: if you know that you are going to use large arrays, I would suggest dynamic storage allocation. I can hear someone out there saying, "OK, but how can I know how large is 'large'?" My answer is, "If you have to ask, then it's 'large'."

Regards,

Dave

killer9012 · #5 05-Nov-2006, 15:39

so dave, what does this mean:

Depth level = 9212, Total allocated = 9.212e+009
Depth level = 9213, Total allocated = 9.213e+009
Depth level = 9214, Total allocated = 9.214e+009
Depth level = 9215, Total allocated = 9.215e+009
Depth level = 9216, Total allocated = 9.216e+009
Depth level = 9217, Total allocated = 9.217e+009
Depth level = 9218, Total allocated = 9.218e+009
Depth level = 9219, Total allocated = 9.219e+009
Depth level = 9220, Total allocated = 9.22e+009
Depth level = 9221, Total allocated = 9.221e+009
Depth level = 9222, Total allocated = 9.222e+009
Depth level = 9223, Total allocated = 9.223e+009
Depth level = 9224, Total allocated = 9.224e+009
Depth level = 9225, Total allocated = 9.225e+009
Depth level = 9226, Total allocated = 9.226e+009
Depth level = Press any key to continue

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Problems while burning CD's	netnut	Computer Software Forum - Windows	16	18-Jan-2008 00:45
Help with linking strategies	ThomasK	Search Engine Optimization Forum	8	22-May-2006 10:17
Linking Problem!	os008	MS Visual C++ / MFC Forum	0	20-Jul-2005 15:40
Chaintech Geforce 5600 FX problems	bartster74	Computer Hardware Forum	8	04-May-2004 14:16
CD Burner problems	dan_wood	Computer Hardware Forum	3	27-Nov-2003 20:12

Linking Problems :D

Re: Linking Problems :D

Re: Linking Problems :D

Re: Linking Problems :D

Re: Linking Problems :D