# Thread: Max space that turbo c can utilize

1. ## 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
{
long int num=orignum;
list *temp,*newnode;
int div;

while(num>0)
{
div=num%10;
newnode=(list*)malloc(sizeof(list));
newnode->digit=(short int)div;
newnode->left=newnode->right=NULL;
if(temp==NULL)
{

temp=newnode;
//cur=temp1;
}
else
{

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

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

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

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

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. Originally Posted by matsp
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. 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

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

10. 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
{
long int num=orignum;
list *temp,*newnode;
int div;

while(num>0)
{
div=num%10;
newnode=(list*)malloc(sizeof(list));
newnode->digit=div;
newnode->left=newnode->right=NULL;
if(temp==NULL)
{

temp=newnode;
}
else
{

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

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

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

13. ## @ 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. 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->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;
{
// 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

15. Thanks Mats. Even the previous code is much faster.