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