How to exceed certain limitations

[uzferry]

So I made a program which can calculate factorial, however, it goes up to 1754. Is there a way to calculate larger numbers than that factorial?

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long double x,t=0,a; long double factorial=1;
cout << "Enter a number: " << endl; 
cin >> x; // original number
a=x; // using a to remember what was the number because x will go down to 1
while (x>=1) {
factorial=factorial*x; x--;}
while (factorial>=10) {factorial=factorial/10, t++;}
cout << a << " factorial is " << factorial << " * 10^" << t;
cin.ignore();
cin.get();
}

[D80DSL3A]

I think most people would recommend using a professional big number library such as http://gmplib.org/

However, if your goal is to do it yourself as an exercise then there are many options.
I'm not sure what your code does exactly, but any floating point type representation will only give you the first few digit values. Usually, the goal is to obtain all of the digits.

My own best effort produces a big integer value in a linked list, with 8 digits stored in each node.

To calculate a factorial I use an overload for bigInt *= unsigned int

bigInt_sList& bigInt_sList::operator*=(unsigned int x)
{
	node* iter = head;
	long long unsigned int prod = 0;
	unsigned int carry = 0;

	while( iter )
	{
            prod = iter->dgt;
            prod *= x;
            prod += carry;
            carry = prod/base;
            iter->dgt = prod%base;
            iter = iter->next;
	}

	if( carry > 0 )// one more term
	{
	    tail->next = new node( carry, NULL );
            tail = tail->next;
            numDigits += digitsPerNode;
	}

	return *this;
}

Then I use it in this function to calculate a factorial.

bigInt_sList factorial( unsigned int n )
{
    bigInt_sList z(1);
    if( n < 2 ) return z;

    for( unsigned int x = 2; x <= n; ++x )
        z *= x;
    return z;
}

This will find 2,000! in well under a second.

One drawback with this singly linked list method is that, since the digits are stored from least to most significant in the list, I must use recursion in the 'to string' conversion for displaying the number.

Try searching this site for examples of other big integer codes. You should find many.

[eklavya sharma 2]

My best effort uses std::vector<unsigned> to store numbers in base UINT_MAX. It calculated 20,000! and stored the result in a string (for displaying) in 440 ms on intel i5. It is a 77338 digit number (in base 10).

If you'll write a big int library and you follow my way of doing it, try to make a function to display contents in hexadecimal ASAP (displaying in decimal requires a division and modulo function before which you'll probably want to make simpler functions like add and subtract). Otherwise debugging will be a pain.

Using a release build instead of a debug build usually boosts speed by many times on STL containers (at least in Visual Studio 2008)

[D80DSL3A]

@eklavya sharma 2. Nice job! I just tested mine for 20,000! and time = 4.39 seconds just to calculate the number. Yours is at least 10x faster. My computer uses a Pentium D dual core processor at 3.6Ghz. I'm not sure how the processor performance compares to yours.

Oh well, back to the drawing board! At least I stimulated some interest in this otherwise dead thread.

EDIT:
Throwing together a quick vector based method, I still get a long time = 4.796 seconds, which is (marginally) slower than my linked list based method. Perhaps this is due to my smaller base = 1e08 more than a processor difference?

[eklavya sharma 2]

My laptop has 2.5GHz dual core processor (and 4GB RAM). Your computer is faster.

One possible reason for your slow performance could be that to calculate carry you divide by base. Division is slow. By using base UINT_MAX (which is 4294967295), I have an advantage. I calculate the product of 2 digits in a 64 bit number. Using a union, I split the number into 2 32 bit numbers. The higher bits make 'carry' while the lower bits make the product's digit. And of course, my method uses less digits, which means less loops during multiplication.