Segmentation fault in factorial program

unkn00wn (71)
i created a factorial program for numbers greater than 14 ,
it seems to be working for numbers less than and equal to 80 , but for 81 and above giving segmentation fault.

all functions , i.e. multiply , add are working fine!
but factorial giving segmentation fault for 81 and above ! any help Pls !
hre is the code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include<iostream>
#include<string.h>
#include<cstdlib>
#include<cmath>
#include"attachedtofactorial.cpp"
using namespace std;
int count=0;
char* factorial(char *b)
{
	count++;
	char *a=new char[1];
	a[0]='1';
	cout<<count;
	cout<<"    value : "<<value(b);
	if(value(b)==1||value(b)==0)
	{ 
		cout<<"  returned"<<endl;
		return a;

	}
	else
	{ 
		cout<<"  forward"<<endl;
		return(multiply(b,factorial(subs(b,a))));

	}
}


int main()
{
	char a[1000000];//=new char;

	char *c=new char[1000000];//=new char;

	system("echo Enter The Number : ");
	cin>>a;

	c=factorial(a);

	//cout<<"\nAns : "<<c<<" "<<a<<endl;

	return 0;
}



attachedtofactorial.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<cmath>
using namespace std;
void change(char *b)
{
	char *a=new char;
	int i=0,j=0;
	for(i=strlen(b)-1;i>=0;i--)
	{

		a[j++]=b[i];//-48;
	}
	a[j]='\0';
	strcpy(b,a);
	//	return a;
}

void tenmul(char * c,int j)
{
	int i=0,k=0;
	char a;
	for(i=0;i<j;i++)
	{
		for(k=strlen(c)-1;k>0;k--)
		{	
			c[k]=c[k-1];		
		}
		c[0]='0';
	}
}
int value(char *a)
{
	char *b=new char[strlen(a)];
	strcpy(b,a);
	change(b);
	int i=0,blen=0,temp=0,bval=0;
	blen=strlen(b);
	for(i=0;i<blen;i++)
	{
		temp=b[i]-48;
		bval+=temp*pow(10,i);
	}
	return bval;
}

char * subs(char *c,char *d)
{
	
	int alen=0,blen=0,i=0,j=0,k=0;
	alen=strlen(c);
	blen=strlen(d);
	char *a =new char[alen];
	char *b =new char[blen];
	strcpy(a,c);
        strcpy(b,d);
        change(a);
        change(b);


	if(alen>=blen)
	{
		for(i=0;i<alen;i++)
		{
			if(i>=blen) b[i]='0';
			j=(int)a[i]-(int)b[i];
			if(j>=0) a[i]=j+48;
			else
			{	
				j=j+10;
				a[i+1]=(int)a[i+1]-1;
				a[i]=j+48;

			}


		}

	}
	else if(blen>alen)
	{
	char *A =new char[blen];
	A=subs(d,c);	
	change(A);
	A[blen]='-';
	change(A);
	return A;
	


	}

	change(a);
	return a;

}

void add(char *ans,char *c)
{
	int alen=0,blen=0;
	alen=strlen(ans);
	blen=strlen(c);


	//change(ans);
	//change(c);

	int i=0,j=0,k=0,curr=0,aval=0,carry=0;
	k=strlen(c);
	for(i=0;i<k;i++)
	{
		aval=ans[i]-48;
		if(aval<0) aval=0;
		curr=c[i]-48;
		if(curr<0) curr=0;
		carry=aval+curr+carry;
		ans[i]=carry%10+48;
		carry=carry/10;

	}
	ans[k]='\0';
	//change(ans);

}



char * multiply(char * a,char * b)
{

	int alen=0,blen=0,i=0,curr=0,bval=0,carry,j=0;
	alen=strlen(a);
	blen=strlen(b);

	change(a);
	change(b);

	char *c=new char[alen+blen];
	char *ans=new char[alen+blen];
	for(j=0;j<blen;j++)
	{	
		carry=0;
		bval=b[j]-48;
		for(i=0;i<alen+blen;i++)
		{
			curr=a[i]-48;
			if(curr<0) curr=0;
			carry=bval*curr+carry;
			c[i]=carry%10+48;
			carry=carry/10;
		}
		tenmul(c,j);
		add(ans,c);
		change(c);
		//cout<<c<<endl;

	}
	change(a);
	change(b);
	change(ans);
	return ans;
}
cire (8284)
That's a whole lot of memory leak you've got going on. 8 news in various functions called multiple times. I see several arbitrary news for what should be local automatic variables.

Where are the corresponding delete[]s for your news?

Since you never check for buffer overruns, I'm not surprised you get segmentation faults.

I don't know why people think a factorial function is a good candidate for recursion. It's not.
viliml (791)
!?!?
the factorial function is as simple as this:
1
2
3
4
5
6
7
8
9
 
long long fact(int n)
{
     long long rez=1;
     for (int i=2; i<=n; i++)
     {
         rez*=i;
         }
     return rez;
     }
unkn00wn (71)
@VILIML , can ur program calculate 99999999! ?

@cire , but its wotking till 80 , returning value of 81 ! and then giving up !

I tried using delete , its giving memory error at 20 ! only !!!
can u resolve this ?
Last edited on
kbw (9488)
I think you're trying to calculate a factorial recursively using Binary Coded Decimal, BCD.

You have several flaws.
1. You're confusing an array of chars and a C string.
2. You're not dealing with memory management correctly.

An array of characters is an array of characters. You have to keep track of the length of the array.

A C string is zero terminated array of characters. All the str... functions deal with this format of string.

So when you write code like:
1
2
3
 
   char *a = new char;
   a[0] = '1';
   int alen = strlen(a);
you're using a string function on a character array that is not zero terminated, and is therefore a serious errror.

You're allocating memory in one function, returning it to another without worrying about where the memory should be deleted. You eventually discard the pointer to the memory and end up with garbage (lost memory blocks in the heap). This is a less serious error until you run out of memory.

C++ has a string type that is probably more suitable. It saves you from having to deal with zero termination and memory management.
Pravesh Koirala (267)
in attachedtofactorial.cpp line 8
perhaps you meant
 
 
	char *a=new char[strlen(b)];
cire (8284)
This may be a bit beyond the OPs grasp, but here is basically what you were trying to do wrapped up in a very minimal BigNum class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
#include <string>
#include <vector>
#include <cctype>
#include <iostream>

class BigNum
{
public:

	class BadInput {} ;
	class Underflow {} ;

	BigNum( const std::string& s ) ;
	BigNum( BigNum && n ) : num_(n.num_) {}

	BigNum &operator *=(const BigNum& n ) ;
	BigNum &operator=(BigNum&& n) { num_ = std::move(n.num_); }
	BigNum &operator--() ;

	bool IsZero() const { return num_.size() == 0 || (num_.size()==1 && num_[0] == 0) ; }
	std::string ToString() const ;

private:

	std::vector<unsigned char> num_ ;
	static const unsigned default_vec_capacity=200 ;
};

std::string BigNum::ToString() const
{
	std::string result ;

	for ( auto i = num_.rbegin() ; i != num_.rend() ; ++i )
		result += *i+'0' ;

	return result ;
}

BigNum::BigNum(const std::string& s ) : num_()
{
	num_.reserve(default_vec_capacity) ;

	for ( auto i = s.rbegin() ;  i != s.rend() ;  ++i )
	{
		if ( !isdigit(*i) )
			throw BadInput() ;

		num_.push_back(*i-'0') ;
	}
}

BigNum& BigNum::operator--()
{
	if (num_.size() == 0 || (num_.size() == 1 && num_[0] == 0))
		throw Underflow() ;

	if ( num_[0] > 0 )
	{
		--num_[0] ;
		return *this ;
	}

	for ( auto i = num_.begin(); i!=num_.end(); ++i )
	{
			if ( *i > 0 )
			{
				*i = *i - 1 ;
				break ;
			}

			*i = 9 ;
	}

	if ( num_.back() == 0 )
		num_.pop_back() ;

	return *this ;
}

BigNum& BigNum::operator*=(const BigNum & n)
{
	std::vector<unsigned char> result(n.num_.size()+num_.size()) ;

	for ( auto i = n.num_.begin(); i != n.num_.end() ; ++i )
	{
		auto r = result.begin() + (i-n.num_.begin()) ;

		for ( auto j = num_.begin() ; j != num_.end() ; ++j )
		{
			const unsigned char prod = *j * *i ;

			*r += prod ;
			if ( *r >= 10 )
			{
				*(r+1) += *r/10 ;
				*r %= 10 ;
			}

			++r ;
		}

		if ( r != result.end() )
		{
			if ( *r >= 10 )
			{
				*(r+1) = *r/10 ;
				*r %= 10 ;
			}
		}
	}

	if ( result.back() == 0 )
		result.pop_back() ;

	num_ = std::move(result) ;
	return *this ;
}

BigNum factorial(BigNum n)
{
	BigNum result = n ;
	--n ;

	while ( !n.IsZero() )
	{
		result *= n ;
		--n ;
	}

	return result ;
}

int main()
{
	try
	{
		for ( ; ; )
		{
			std::cout << "What number would you like to find the factorial for?\n" ;

			std::string input ;
			std::getline(std::cin, input) ;

			std::cout << factorial(input).ToString() << '\n' ;
		}
	}

	catch(BigNum::BadInput)
	{
		std::cout << "Thanks for playing!\n" ;
	}
}
unkn00wn (71)
Its pretty clear i am not good in memory management ...
as u said i tried deleting possible dynamically allocated arrays ,

but when i have to return some array i have to use
char *a = new char[alen];
type array , else its generating segmentation fault .

or is there any secure way to return array ?

Can u debug the program , if u can give some time on it !
Moschops (7244)
Its pretty clear i am not good in memory management ...

Welcome to C++ - currently, you seem to be writing C code, with cout and cin on top. This is not fun.

In light of the hassle of having to manage memory, we have containers that do all that annoying memory management junk for you, leaving you free to actually program.

For an array of char, consider std::string. For everything else, consider std::vector. As you get used to them, expand into all the others.
Last edited on
viliml (791)
I made a simple WORKING program that can evaluate any factorial with up to 1073741820 digits!
here's the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
string myitoa(long long br)
{
     string str="";
     stack<char> temp;
     while (br)
     {
           temp.push((br%10)+'0');
           br-=br%10;
           br/=10;
           }
     while (temp.size())
     {
           str+=temp.top();
           temp.pop();
           }
     return str;
     }

void operator*= (vector<char>& str, long long n)
{
       long long r=0, a;
       for (long long i=str.size()-1; i>=0; i--)
       {
           a=((str[i]-'0')*n+r);
           str[i]=(a%10)+'0';
           r=(a-a%10)/10;
           }
       if (r)
       {
             string temp=myitoa(r);
             str.insert(str.begin(), temp.begin(), temp.end());
             }
       }

string fact(string n)
{
      string rez="1";
      vector<char> temp(rez.begin(), rez.end());
      rez="";
      for (int i=2; i<=atoll(n.c_str()); i++)
      {
          temp*=i;
          }
      rez.insert(rez.begin(), temp.begin(), temp.end());
      return rez;
      }

I think even though I overloaded the *= operator for char vectors and my own itoa(which seems very unnecesary) is MUCH less complicated than your code!
Last edited on
viliml (791)
you must learn to do things the easy way!
unkn00wn (71)
I don't want any limits in my program. First let my program work . I'll calculate till any number of digits it takes !

True ! I have been writing c code for a year , recently moved to c++ (as i am a student).

And as i am new in C++ , i have less or no knowledge about Memory and vectors !

Well first i have to study more , thanks for all of your helps !
Thank you very much .

Can you suggest me good reference for c++ ?
Last edited on
viliml (791)
Umm, 1073741820 digits isn't realy a "limit" in that sense the factorial of 3000 needs 10 sec to calculate, and has "only" about 9000 digits. So, the factorial of no number that will compute in less than a decade will have more than 1073741820 digits, and becouse you will never compute the factorial of such a big number, you can also say that my program has NO limits!
Topic archived. No new replies allowed.