Large Factorials
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: Large Factorials

1. Member
Join Date
May 2004
Posts
249

Large Factorials

If i m writing a code for a program to solve factorials, what is the best approach if i have large numbers in mind?

If i use int, i can only go upto 4bytes and if i use double i can go upto 8bytes. so should i create new type or is there any other way to get this done.

2. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

Re: Large Factorials

Originally Posted by rockx
If i m writing a code for a program to solve factorials, what is the best approach if i have large numbers in mind?

If i use int, i can only go upto 4bytes and if i use double i can go upto 8bytes. so should i create new type or is there any other way to get this done.
Use one of the many "big number" or "arbitration precision" libraries out there, or you can approximate the factorial by using Stirling's formula.

http://en.wikipedia.org/wiki/Stirling%27s_formula

Regards,

Paul McKenzie

3. Member
Join Date
May 2004
Posts
249

Re: Large Factorials

Can the following code be modified to find the exact value factorials for #s greater than say 30

Code:
```long factorial(unsigned  long  value)
{
if(value ==0)
{
return 1;
}
else
{
return value * factorial(value-1);
}

}```

4. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

Re: Large Factorials

Originally Posted by rockx
Can the following code be modified to find the exact value factorials for #s greater than say 30
Again, get yourself a library to handle arbitrary large numbers. 4 or 8 byte ints are not going to help you.

Regards,

Paul McKenzie

5. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

Re: Large Factorials

Not sure what you mean by "solve factorials"
but if all you need is the values of n! for "any" value of n, then you can also just store precalculated values of those. There's websites listing n! for various values of n.

http://www.tsm-resources.com/alists/fact.html has 1-99 and 999
http://www.wattpad.com/4855-a-list-o...constants#!p=7 has a much larger list (in parts)
http://infomotions.com/etexts/gutenb...95/factr10.htm goes further still

I'm sure there's sites listing more details if you really need those.

Or did you mean "factoring" (splitting an integer into it's prime factors ?) In that case it depends how big the ints are you want to factor.

6. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

Re: Large Factorials

Originally Posted by rockx
Can the following code be modified to find the exact value factorials for #s greater than say 30
if you want exact:
an (unsigned) int can do 12!
a double (53bits) can do 18!
an (unsigned) int64 can do 20!
an (unsigned) int128 can do 34! (not all compilers have support for 128bit ints)
an (unsigned) int256 can do 57! (afaik, int256 isn't even a C++ standard (yet) and I know of only 1 c++ compiler that supports it).

a double can do much bigger factorials than 18!, but not without loosing decimal/integer accuracy.
a "long double" could do 20! (since it's 64bits mantissa), but you can't use this on VC++ though you could use it via assembly or via a another compiler that supports long double as a distinct type.

If you more than the above and you want decimal/integer accuracy, then you'll need a library/class that handles math with the accuracy you want, there are a few fixed size precision math packages out there but most will tend to have "arbitrary" size support.

7. Member
Join Date
May 2004
Posts
249

Re: Large Factorials

is it possible to do the above using Linked Lists and Stack.

WHat i m trying to ask is that if i create a NODE which only accepts numbers between 0-9 and doing so, each individual digit of the large calculated numbers be stored in each NODE.

So will this be possible?

Yes.

9. Re: Large Factorials

I've knocked this up as proof of concept for arbitrarily large integer numbers using vectors. The class operator ! has been overloaded to provide a factorial operator. This is offered 'as is' with no guarantees of working properly in all circumstances as testing has been very limited or that it is the most optimised code possible. It should also perform addition(+), subraction(-) and multiplication(*) on arbitary length positive and negative integer numbers.

Code:
```#include <vector>
#include <string>
#include <iostream>
#include <cctype>
using namespace std;

class Lint {
public:
Lint(const string& num);
~Lint();
Lint(const Lint& li);

Lint& operator=(const string& num);

bool operator==(const Lint& ladd) const;
bool operator!=(const Lint& ladd) const;
Lint operator+(const Lint& ladd) const;
Lint operator-(const Lint& ladd) const;
Lint operator*(const Lint& ladd) const;

Lint operator!();

friend ostream& operator <<(ostream&, const Lint& lint);

private:
typedef vector<int> vint;
typedef vint::reverse_iterator rivint;

mutable vint lngint;
mutable bool neg;
};

Lint::Lint(const string &num)
{
size_t	slen = num.length(),
vpos = 1;

lngint.resize(slen + 1, 0);

vpos += neg = (num[0] == '-');

for (size_t s = neg; s < slen; s++)
lngint[slen - vpos++] = isdigit(num[s]) ? num[s] - '0' : 0;
}

Lint::~Lint()
{
lngint.clear();
}

Lint::Lint(const Lint& li)
{
lngint = li.lngint;
neg = li.neg;
}

Lint& Lint::operator =(const string& num)
{
size_t	slen = num.length(),
vpos = 1;

lngint.clear();
lngint.resize(slen + 1, 0);

vpos += neg = (num[0] == '-');

for (size_t s = neg; s < slen; s++)
lngint[slen - vpos++] = isdigit(num[s]) ? num[s] - '0' : 0;

return *this;
}

Lint Lint::operator +(const Lint& ladd) const
{
if (ladd.neg == true && neg == false) {
ladd.neg = false;
Lint temp = *this - ladd;
ladd.neg = true;
return temp;
}

if (neg == true && ladd.neg == false) {
neg = false;
Lint temp = ladd - *this;
neg = true;
return temp;
}

bool	lneg = ladd.neg,
tneg = neg,
both = false;

if (neg == true && ladd.neg == true) {
neg = false;
ladd.neg = false;
both = true;
}

Lint temp(*this);

const size_t m = max(ladd.lngint.size(), temp.lngint.size());

temp.lngint.resize(m, 0);
ladd.lngint.resize(m, 0);

for (size_t i = 0; i < m; i++) {
temp.lngint[i] += ladd.lngint[i];
if (temp.lngint[i] > 9) {
if (i == (m - 1))
temp.lngint.resize(temp.lngint.size() + 1);

temp.lngint[i + 1] += (temp.lngint[i] / 10);
temp.lngint[i] %= 10;
}
}

neg = tneg;
ladd.neg = lneg;
temp.neg = both;

return temp;
}

Lint Lint::operator -(const Lint& ladd) const
{
if (ladd.neg == true) {
ladd.neg = false;
Lint temp = *this + ladd;
ladd.neg = true;
return temp;
}

if (neg == true) {
neg = false;
bool lneg = ladd.neg;
ladd.neg = false;
Lint temp = *this + ladd;
ladd.neg = lneg;
neg = true;
temp.neg = true;
return temp;
}

Lint temp(*this);

const size_t m = max(ladd.lngint.size(), temp.lngint.size());

temp.lngint.resize(m, 0);
ladd.lngint.resize(m, 0);

bool	res = false;

for (size_t i = 0; i < m; i++) {
temp.lngint[i] -= ladd.lngint[i];
if (temp.lngint[i] < 0) {
if (i == (m - 1)) {
temp.lngint.resize(temp.lngint.size() + 1, 0);
res = true;
}

temp.lngint[i + 1] -= 1;
temp.lngint[i] += 10;
}
}

if (res == true) {
string minus(m + 1, '0');
minus[0] = '1';

Lint comp(minus);
comp = comp - temp;
temp = comp;
temp.neg = true;
temp.lngint[temp.lngint.size() - 2] = 0;
}

return temp;
}

Lint Lint::operator *(const Lint& ladd) const
{
const	Lint lone("1");

bool	lneg = false;

if (ladd == Lint("0"))
return Lint("0");

if (ladd.neg == true) {
lneg = true;
ladd.neg = false;
}

Lint sum(*this);

for (Lint temp(ladd); temp != lone; temp = temp - lone)
sum = sum + *this;

if (lneg == true) {
if (sum.neg == false)
sum.neg = true;

ladd.neg = lneg;
}

return sum;
}

bool Lint::operator ==(const Lint& ladd) const
{
if (neg != ladd.neg)
return false;

int	sl,
st;

for (sl = (int)ladd.lngint.size() - 1; sl >= 0; sl--)
if (ladd.lngint[sl] != 0)
break;

for (st = (int)lngint.size() - 1; st >= 0 ; st--)
if (lngint[st] != 0)
break;

if (st != sl)
return false;

if (st < 0)
return true;

for (int s = 0; s <= st; s++)
if (ladd.lngint[s] != lngint[s])
return false;

return true;
}

bool Lint::operator !=(const Lint& ladd) const
{
return !(*this == ladd);
}

Lint Lint::operator!()
{
const Lint lone("1");
const Lint zero("0");

Lint sum(*this);

Lint start(sum);

if (neg == true)
return zero;

if (start == lone || start == zero)
return lone;

start = start - lone;

for (Lint fac(start); fac != lone; fac = fac - lone)
sum = sum * fac;

return sum;
}

ostream& operator<<(ostream& os, const Lint& lint)
{
bool z = false;

if (lint.neg)
os << '-';

for (Lint::rivint ci = lint.lngint.rbegin(); ci != lint.lngint.rend(); ++ci)
if (*ci != 0 || (*ci == 0 && z)) {
os << *ci;
z = true;
}

if (z == false)
os << '0';

return os;
}

int main(int argc, char* argv[])
{
/*cout << "1 + 2 = " << Lint("1") + Lint("2") << " (" << 1 + 2 << ")" << endl;
cout << "11 + 333 = " << Lint("11") + Lint("333") << " (" << 11 + 333 << ")" << endl;
cout << "3 - 1 = " << Lint("3") - Lint("1") << " (" << 3 - 1 << ")" << endl;
cout << "1 - 3 = " << Lint("1") - Lint("3") << " (" << 1 - 3 << ")" << endl;
cout << "13 + -22 = " << Lint("13") + Lint("-22") << " (" << 13 + (-22) << ")" << endl;
cout << "-22 + 16 = " << Lint("-22") + Lint("16") << " (" << (-22) + 16 << ")" << endl;
cout << " -234 - -567 = " << Lint("-234") - Lint("-567") << " (" << (-234) - (-567) << ")" << endl;
return 0;*/

if (argc != 2) {
cout << "Usage:" << endl << "fact n" << endl;
return 0;
}

string f(argv[1]);
Lint fact(f);

cout << argv[1] << "! is" << endl;
cout << !fact << endl;

return 0;
}```
fact 500 gives
Code:
```500! is
12201368259911100687012387854230469262535743428031928421924135883858453731538819
97605496447502203281863013616477148203584163378722078177200480785205159329285477
90757193933060377296085908627042917454788242491272634430567017327076946106280231
04526442188787894657547771498634943677810376442740338273653974713864778784954384
89595537537990423241061271326984327745715546309977202781014561081188373709531016
35632443298702956389662891165897476957208792692887128178007026517450776841071962
43903943225364226052349458501299185715012487069615681416253590566934238130088562
49246891564126775654481886506593847951775360894005745238940335798476363944905313
06232374906644504882466507594673586207463792518420045936969298102226397195259719
09452178233317569345815085523328207628200234026269078983424517120062077146409794
56116127629145951237229913340169552363850942885592018727433795173014586357570828
35578015873543276888868012039988238470215146760544540766353598417443048012893831
38968816394874696588175045069263653381750554781286400000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000```
Last edited by 2kaud; November 25th, 2013 at 06:05 AM. Reason: Changed constructor

10. Member
Join Date
May 2004
Posts
249

Re: Large Factorials

Considering the above, could it help solve the following:

x = (n! - (n -1)!) + ((n-2)! - (n - 3)!) .............. - 1!

assuming n is an even number or

(n! - (n -1)!) + ((n-2)! - (n - 3)!) .............. + 1!

assuming n is an odd number

11. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

Re: Large Factorials

Originally Posted by rockx
Considering the above, could it help solve the following:

x = (n! - (n -1)!) + ((n-2)! - (n - 3)!) .............. - 1!

assuming n is an even number or

(n! - (n -1)!) + ((n-2)! - (n - 3)!) .............. + 1!

assuming n is an odd number
If the code has no bugs, then what's the issue? The code has overloaded all of the operators necessary -- there is a ! operator, a + operator, a - operator, etc.

Regards,

Paul McKenzie

12. Member
Join Date
May 2004
Posts
249

Re: Large Factorials

so what is a better way of doing this

13. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,734

Re: Large Factorials

Originally Posted by rockx
so what is a better way of doing this
Make use of an existing, well tested library instead of trying to write your own or use one that, while a commendable effort, has not been thoroughly tested. Then, re-arrange your formula to minimise the number of computations and implement the code.

14. Re: Large Factorials

Originally Posted by rockx
so what is a better way of doing this
Rewrite the formula in an easier to calculate form.
E.g. n! - (n - 1)! = n * (n - 1)! - (n - 1)!

15. Re: Large Factorials

Originally Posted by laserlight
Make use of an existing, well tested library instead of trying to write your own or use one that, while a commendable effort, has not been thoroughly tested. Then, re-arrange your formula to minimise the number of computations and implement the code.
In cases like this, it is always better to use a well tested supported library if possible, rather than code one yourself.

As I stated in my post #9, the code I posted is only 'proof of concept' in response to OP post #7 querying using linked lists and a stack. I believe the code I posted 'works' but is provided 'as is' with no support. Anyone is free to use it as they wish.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)