Max space that turbo c can utilize

This is a discussion on Max space that turbo c can utilize within the C Programming forums, part of the General Programming Boards category; I m using Turbo c and have implemented a code for finding factorial of a number using link list. The ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    7

    Max space that turbo c can utilize

    I m using Turbo c and have implemented a code for finding factorial of a number using link list.
    The actual problem was to 123456!.
    My program seems to be correct but it gives correct results upto 63! and then the result becomes zero for further factorials.

    The following program multiplies the nos only 63 times 64th time the whole result becomes 0.

    I think it is due shortage of memory. Is there any solution for that.


    Code:
    #include<stdio.h>
    #include<conio.h>
    /*
    This program is working good for finding factorial upto 63
    The error is it can multiply 63 times and then the list becomes 0
    Eg.If we want to find 111!
    it can find 100*99*98.....upto 56
    and when it multiplies the result to next no. i.e. 55,
    the whole result becomes 0
    */
    
    //this structure is used to form a list in which each
    //node holds only one digit and thus forming the no. from left to right
    typedef struct List
    {
    	int digit;
    	struct List *left,*right;
    }list;
    
    void disp(list **);
    
    //represent a no. in a list form
    void createlist(long int orignum,list  **head)
    {
    	long int num=orignum;
    	list *temp,*newnode;
    	int div;
    	temp=*head;
    
    	while(num>0)
    	{
    		div=num%10;
    		temp=*head;
    		newnode=(list*)malloc(sizeof(list));
    		newnode->digit=(short int)div;
    		newnode->left=newnode->right=NULL;
    		if(temp==NULL)
    		{
    
    			temp=newnode;
    			*head=temp;
    			//cur=temp1;
    		}
    		else
    		{
    
    			temp=*head;
    			while(temp->left!=NULL)
    				temp=temp->left;
    			temp->left=newnode;
    			newnode->right=temp;
    			//temp1=temp1->left;
    		}
    		num=(num-(num%10))/10;
    	}
    
    }
    
    //copy one list into another
    //copylist(oldlist,newlist)
    void copylist(list **list1,list **list3)
    {
    	list *temp1,*temp3,*newnode;
    	temp1=*list1;
    	temp3=*list3;
    	do
    	{
    
    		temp1->digit=temp3->digit;//copy digit from old to new list
    		if(temp1->left==NULL&&temp3->left!=NULL)
    		{
    			newnode=(list*)malloc(sizeof(list));
    			newnode->digit=0;
    			newnode->left=NULL;
    			newnode->right=temp1;
    			temp1->left=newnode;
    
    		}
    		temp1=temp1->left;
    		temp3=temp3->left;
    
    	}while(temp3!=NULL);
    
    }
    
    
    
    
    void multiply(list **list1,list **list2,list **list3)
    {
    	list *temp1,*temp2,*temp3,*newnode;
    	long int place1,place2,place3;
    	int var,carry,hold;
    	temp1=*list1;
    	temp2=*list2;
    	temp3=*list3;
    	place2=0;
    	//multiplying
    	while(temp2!=NULL)//loop for multiplier
    	{
    		temp1=*list1;
    		place1=1;
    		while(temp1!=NULL)//loop for multiplicand
    		{
    //			temp3=(*list3)->left;
    			////
    //			free(temp3);
    			temp3=*list3;
    			var=temp1->digit*temp2->digit;
    			place3=place1+place2;
    			while(place3>1)  //decides at which node the no. should go
    			{
    				if(temp3->left!=NULL)
    					temp3=temp3->left;
    				else
    				{
    					newnode=(list*)malloc(sizeof(list));
    					newnode->left=NULL;
    					newnode->digit=0;
    						//carry=0;
    					newnode->right=temp3;
    					temp3->left=newnode;
    					temp3=temp3->left;
    				}
    				place3--;
    			}
    			var=temp3->digit+var;
    			temp3->digit=var;
    			while(temp3->digit>9)//taking care of carry
    			{
    				hold=temp3->digit;
    				carry=(hold-(hold%10))/10;
    				hold=hold%10;
    				temp3->digit=hold;
    				if(temp3->left!=NULL)
    				{
    					temp3->left->digit=temp3->left->digit+carry;
    					temp3=temp3->left;
    				}
    				else
    				{
    					newnode=(list*) malloc(sizeof(list));
    					newnode->digit=carry;
    					newnode->left=NULL;
    					newnode->right=temp3;
    					temp3->left=newnode;
    					temp3=temp3->left;
    				}
    			}
    		 //	if(temp1->left==NULL)
    		 //	break;
    			temp1=temp1->left;//moving to next digit of multiplicand
    			place1++;
    
    		}
    	//	if(temp2->left==NULL)
    	  //	break;
    		temp2=temp2->left;//moving to next digit of multiplier
    		place2++;
    
    	}
    ///	printf("\nmul:");
    //	disp(list3);
    //	getch();
    }
    
    
    void disp(list **list3)
    {
    	list *temp;
    	temp=*list3;
    	while(temp->left!=NULL)
    	{
    		temp=temp->left;
    	}
    	while(temp)
    	{
    		printf("%d",temp->digit);
    		temp=temp->right;
    	}
    //	printf("%d",temp->digit);
    
    
    }
    
    
    void main()
    {
    	list *list1,*list2,*list3,*newnode;
    	long int num;
    	long int orignum;
    	list1=list2=list3=NULL;
    	clrscr();
    
    	printf("\n\tPlease enter a no. to find factorial of:");
    	scanf("%li",&num);
    	orignum=num;
    	printf("\n\tWAIT....");
    
    	createlist(num,&list2);  //create link list for multiplicand
    //	disp(&list2);
    	num--;
    	while(num>1)
    	{
    
    		list1=NULL;
    		createlist(num,&list1);//create link list for multiplier
    //		printf("\nlist1:");
    //		disp(&list1);
    		list3=NULL;
    		newnode=(list*)malloc(sizeof(list));
    		newnode->left=newnode->right=NULL;
    		newnode->digit=0;
    		list3=newnode;
    
    		multiply(&list2,&list1,&list3);//multiply and store the result in list3
    //		printf("\nlist3:");
    //		disp(&list3);
    		free(list2);
    		list2=NULL;                    //flush multiplicand
    		newnode=(list*)malloc(sizeof(list));
    		newnode->left=newnode->right=NULL;
    		list2=newnode;
    		copylist(&list2,&list3);      //result becomes new multiplicand
    //	printf("\nlist3:");
    //	disp(&list3);
    //	printf("\nlist2:");
    //	disp(&list2);
    
    //		printf("\nlist2:");
    //		printf("\n*%li=\t",num);
    //		disp(&list2);
    		free(list3);
    //		getch();
    		free(list1);
    		num--;
    
    	}
    	clrscr();
    	printf("\n\t%li!=",orignum);
    	disp(&list2);
    	getch();
    }

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,179
    My question is why you're using Turbo C in the first place?
    It's antique and limited to ridiculous limits such as 640K of memory.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Well, if we remove the clrscr() and getch() [which aren't really necessary for the program to function anyways], I have got it calculating 1000! - It didn't crash when I entered 123456!, but after a few minutes of using 100% cpu, I gave up.

    Your code appears to be correct for small numbers - I checked 20! which gives 2432902008176640000 and this site shows 20! as 2432902008176640000.

    Obviously, the way that it calculates the factorial is taking O(n^n), so large numbers will take VERY long.

    I'm giving 123456! another chance right now, but I don't expect it to be very quick.

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

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    To access more memory in Turbo C, you use the far heap, not just the near one. You should also be using one of the largest memory models for the compiler to work with this.

    I'm not too familiar with using the far heap, but I can look up some info on it, if you're quite interested. I'm sure the text I have on it would have at least one sample program I could post up.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Adak View Post
    To access more memory in Turbo C, you use the far heap, not just the near one. You should also be using one of the largest memory models for the compiler to work with this.

    I'm not too familiar with using the far heap, but I can look up some info on it, if you're quite interested. I'm sure the text I have on it would have at least one sample program I could post up.
    However, as the running of my test with 123456! is currently using 1.4GB, I doubt that using a far-heap that can at the VERY MOST use 1MB will work anyways. A 32-bit compiler is definitely necessary - I don't know if it's anywhere near completion yet, it may well be that it's still got a long way to go, so it may well run out of the 2GB memory space allowed in my Windows installation.

    Edit: My 123456! run seems to have crashed whilst I was out to lunch - with no error message (?). Doing 12345 at the moment.

    --
    Mats
    Last edited by matsp; 07-16-2008 at 07:05 AM.
    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
    Registered User
    Join Date
    Jul 2008
    Posts
    7
    Quote Originally Posted by Adak View Post
    To access more memory in Turbo C, you use the far heap, not just the near one. You should also be using one of the largest memory models for the compiler to work with this.

    I'm not too familiar with using the far heap, but I can look up some info on it, if you're quite interested. I'm sure the text I have on it would have at least one sample program I could post up.

    I have tried using far, but i m not experienced in that.
    I declared the pointer as
    unsigned far list *list1=(unsigned far list*) 0xb000000;
    It displays error when i use the pointer.

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    7
    Quote Originally Posted by matsp View Post
    However, as the running of my test with 123456! is currently using 1.4GB, I doubt that using a far-heap that can at the VERY MOST use 1MB will work anyways. A 32-bit compiler is definitely necessary - I don't know if it's anywhere near completion yet, it may well be that it's still got a long way to go, so it may well run out of the 2GB memory space allowed in my Windows installation.

    Edit: My 123456! run seems to have crashed whilst I was out to lunch - with no error message (?). Doing 12345 at the moment.

    --
    Mats

    I dont think that much RAM will be required.I m freeing the lists every time after multiplication.

    the structure will take 8 bytes.
    the final ans will be of about 250k digits
    so, 250X8=2MB(aprrox)

    We, can consider space required to 10 MB at max.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    But you assume that malloc only takes up the space you allocate. A minimal allocation in MS C runtime will use at least 64 bytes - so we're now 8 times larger than you suggest.

    I can only report back what I see - currently, running a 12345!, it is using 2,020,xxx KB - which is pretty darn close to 2GB.

    It would probably be a good idea to optimize the memory allocation/efficiency of the multiplication by using blocks instead of individual digits. I haven't tried it out, but blocks of 16-256 digits would be quite easy, and reduce the overhead of allocating, freeing and dereferencing pointers.

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

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Oh, and I just looked a bit closer at your implementation:
    Code:
    		multiply(&list2,&list1,&list3);//multiply and store the result in list3
    //		printf("\nlist3:");
    //		disp(&list3);
    		free(list2);
    There is no effort in freeing the elements held in list2 - you are just freeing the first element. This is probably the reason we're quickly running out of memory. Likewise after copylist - you free the first element of the list, the rest is just left around.

    I found this when I started thinking about a more efficient memory management.

    Edit: Fixing the above memory leaks seem to improve the memory usage by a relatively good amount - 4000! with the original code gets to about 1GB after a bit, and the new code hovers around 1MB at the moment.

    --
    Mats
    Last edited by matsp; 07-16-2008 at 09:52 AM.
    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.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I made some other improvements beyond fixing the memory leak - the primary one being that I avoid walking the entire list3 every time you calculate one digit by using a second pointer variable in the innermost loop (the one that propagates the carry).

    It sped things up quite a bit, as 600! took 1.64 seconds on my machine before this improvement, after, it took something like 0.13 seconds, and I could do 2000! in 1.8 seconds with the new variant. That is about 10x improvement, and I beleive it's even more for larger numbers, although I didn't make too many large runs with the original code. That is using Visual Studio .Net.

    I also compiled it with gcc-mingw 3.4.2, which takes 2.8 seconds to do 2000!, so slightly slower than MS

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    /*
    This program is working good for finding factorial upto 63
    The error is it can multiply 63 times and then the list becomes 0
    Eg.If we want to find 111!
    it can find 100*99*98.....upto 56
    and when it multiplies the result to next no. i.e. 55,
    the whole result becomes 0
    */
    
    //this structure is used to form a list in which each
    //node holds only one digit and thus forming the no. from left to right
    typedef struct List
    {
    	int digit;
    	struct List *left,*right;
    }list;
    
    void disp(list **);
    
    __inline list *NewNode(int digit)
    {
    	list *p = malloc(sizeof(list));
    	p->digit = digit;
    	p->left = NULL;
    	p->right = NULL;
    	return p;
    }
    
    __inline void AppendNode(list **current, int digit)
    {
    	list *newnode=NewNode(digit);
    	newnode->right = *current;
    	(*current)->left = newnode;
    	*current = newnode;
    }
    
    void ListFree(list *p)
    {
    	list *t;
    	while(p)
    	{
    		t = p->left;
    		free(p);
    		p = t;
    	}
    }
    
    //represent a no. in a list form
    void createlist(long int orignum,list  **head)
    {
    	long int num=orignum;
    	list *temp,*newnode;
    	int div;
    	temp=*head;
    
    	while(num>0)
    	{
    		div=num%10;
    		temp=*head;
    		newnode=(list*)malloc(sizeof(list));
    		newnode->digit=div;
    		newnode->left=newnode->right=NULL;
    		if(temp==NULL)
    		{
    
    			temp=newnode;
    			*head=temp;
    		}
    		else
    		{
    
    			temp=*head;
    			while(temp->left!=NULL)
    				temp=temp->left;
    			temp->left=newnode;
    			newnode->right=temp;
    			//temp1=temp1->left;
    		}
    		num=(num-(num%10))/10;
    	}
    
    }
    
    //copy one list into another
    //copylist(oldlist,newlist)
    void copylist(list **list1,list **list3)
    {
    	list *temp1,*temp3,*newnode;
    	temp1=*list1;
    	temp3=*list3;
    	do
    	{
    
    		temp1->digit=temp3->digit;//copy digit from old to new list
    		if(temp1->left==NULL&&temp3->left!=NULL)
    		{
    			newnode=NewNode(0);
    			newnode->right=temp1;
    			temp1->left=newnode;
    
    		}
    		temp1=temp1->left;
    		temp3=temp3->left;
    
    	}while(temp3!=NULL);
    
    }
    
    
    
    
    void multiply(list *list1,list *list2,list *list3)
    {
    	list *temp1,*temp2,*temp3;
    	long int place1,place2,place3;
    	int var,carry,hold;
    	temp1=list1;
    	temp2=list2;
    	place2=0;
    	//multiplying
    	while(temp2!=NULL)//loop for multiplier
    	{
    		temp1=list1;
    		place1=1;
    		place3=place2+1;
    		temp3=list3;
    		while(place3>1)  //decides at which node the no. should go
    		{
    			if(temp3->left!=NULL)
    				temp3=temp3->left;
    			else
    			{
    				AppendNode(&temp3, 0);
    			}
    			place3--;
    		}
    		while(temp1!=NULL)//loop for multiplicand
    		{
    			list *ptr3 = temp3;
    			var=temp1->digit*temp2->digit;
    			temp3->digit += var;
    
    			while(ptr3->digit > 9)//taking care of carry
    			{
    				int dig;
    				hold = ptr3->digit;
    				dig = hold % 10;
    				carry = (hold-(dig))/10;
    				ptr3->digit = dig;
    				if(ptr3->left!=NULL)
    				{
    					ptr3->left->digit += carry;
    					ptr3=ptr3->left;
    				}
    				else
    				{
    					AppendNode(&ptr3, carry);
    				}
    			}
    			temp1=temp1->left;//moving to next digit of multiplicand
    			if (temp1)
    			{
    				if (temp3->left)
    					temp3 = temp3->left;
    				else
    					AppendNode(&temp3, 0);
    			}
    			place1++;
    
    		}
    		temp2=temp2->left;//moving to next digit of multiplier
    		place2++;
    	}
    }
    
    
    void disp(list **list3)
    {
    	list *temp;
    	temp=*list3;
    	while(temp->left!=NULL)
    	{
    		temp=temp->left;
    	}
    	while(temp)
    	{
    		printf("%d",temp->digit);
    		temp=temp->right;
    	}
    }
    
    
    int main()
    {
    	list *list1,*list2,*list3;
    	long int num;
    	long int orignum;
    	clock_t t;
    	list1=list2=list3=NULL;
    
    	printf("\n\tPlease enter a no. to find factorial of:");
    	scanf("%li",&num);
    	orignum=num;
    	printf("\n\tWAIT....");
    
    	t = clock();
    	createlist(num,&list2);  //create link list for multiplicand
    	num--;
    	while(num>1)
    	{
    		list1=NULL;
    		createlist(num,&list1);//create link list for multiplier
    		list3=NewNode(0);
    
    		multiply(list2,list1,list3);//multiply and store the result in list3
    		ListFree(list2); 
    		ListFree(list1);
    		list2 = list3;
    		num--;
    	}
    	t = clock()-t;
    	printf("\n\t%li!=",orignum);
    	disp(&list2);
    	printf("\n\nTime used: %.2f\n", (double)t / CLOCKS_PER_SEC);
    	return 0;
    }
    --
    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.

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Your computer must be reasonably slow, then . . .

    GCC 4.3.1, compiled with no extra flags:
    1.53s @ 2.2GHz
    4.38s @ 800MHz

    with -O2:
    0.78s @ 2.2GHz
    2.37s @ 800 MHz

    This is running on AMD64 Debian GNU/Linux.

    Anyway, I don't think the point was to do the calculations quickly . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yeah, it's not a very fast machine. I guess gcc 4.3 is also a bit better than 3.4, but I haven't tested that myself. And no, the point isn't to do the calculation quickly, but a little bit of work gave 10x performance boost, which I think is worth doing.

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

  13. #13
    Registered User
    Join Date
    Jul 2008
    Posts
    7

    Talking @ Mats

    Thanx Mats for your gr8 help.
    I thought freeing the first element will free the whole list.
    Also, I was getting errors when I used inline functions.
    I got the result for 2345! after compiling the program in another compiler.
    Thanx for modifying the code, I will compile and check other values as well.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And, further: If we avoid calling malloc/free so often, by using a block allocation, we can improve quite a bit:
    Code:
    list *NewNode(int digit)
    {
        list *p;
        if (poolCnt == 0) {
    	pool = malloc(PREALLOC * sizeof(list));
    	poolCnt = PREALLOC;
    	if (pool == NULL)
    	{
    	    fprintf(stderr, "Out of memory\n");
    	    exit(1);
    	}
        }
        poolCnt--;
        p = &pool[poolCnt];
        p->head = (poolCnt == 0);
        p->digit = digit;
        p->left = NULL;
        p->right = NULL;
        return p;
    }
    
    void AppendNode(list **current, int digit)
    {
    	list *newnode=NewNode(digit);
    	newnode->right = *current;
    	(*current)->left = newnode;
    	*current = newnode;
    }
    
    void ListFree(list *p)
    {
    	list *t;
    	while(p)
    	{
    		t = p->left;
    		if (p->head)
    		{
    		    // We free the current pool object, so reset it. 
    		    if (p == pool)
    		    {
    			poolCnt = 0;
    		    }
    		    free(p);
    		}
    		p = t;
    	}
    }
    That took my 2.x seconds for a 2000! down to under half a second.

    Note that it allocates "backwards", which is probably a bit less efficient on memory, but it's still a whole heap better calling malloc & free 1024 as many times.

    The time spent in malloc/free is quite possibly the big difference between dwks Linux variant and my Windows variant. It would not surprise me if glibc's malloc is more efficient than the one in MS Windows.

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

  15. #15
    Registered User
    Join Date
    Jul 2008
    Posts
    7

    Thumbs up

    Thanks Mats. Even the previous code is much faster.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Remember Turbo? It is comming back
    By Mario F. in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 08-14-2006, 01:26 PM
  2. Easiest way to find the max value stored in an array
    By criticalerror in forum C++ Programming
    Replies: 14
    Last Post: 01-22-2004, 02:35 PM
  3. Question of White space
    By terryrmcgowan in forum C Programming
    Replies: 3
    Last Post: 06-09-2003, 09:13 AM
  4. Replies: 12
    Last Post: 05-17-2003, 05:58 AM
  5. Double output!
    By Spurnout in forum C++ Programming
    Replies: 3
    Last Post: 11-02-2002, 02:35 AM

Tags for this Thread


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