Large Factorials
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Large Factorials

  1. #1
    Join Date
    May 2004
    Posts
    207

    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. #2
    Join Date
    Apr 1999
    Posts
    27,423

    Re: Large Factorials

    Quote Originally Posted by rockx View Post
    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. #3
    Join Date
    May 2004
    Posts
    207

    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. #4
    Join Date
    Apr 1999
    Posts
    27,423

    Re: Large Factorials

    Quote Originally Posted by rockx View Post
    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. #5
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,782

    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. #6
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,782

    Re: Large Factorials

    Quote Originally Posted by rockx View Post
    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. #7
    Join Date
    May 2004
    Posts
    207

    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?

  8. #8
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,272

    Re: Large Factorials

    Yes.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  9. #9
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,272

    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
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  10. #10
    Join Date
    May 2004
    Posts
    207

    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. #11
    Join Date
    Apr 1999
    Posts
    27,423

    Re: Large Factorials

    Quote Originally Posted by rockx View Post
    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. #12
    Join Date
    May 2004
    Posts
    207

    Re: Large Factorials

    so what is a better way of doing this

  13. #13
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,250

    Re: Large Factorials

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  14. #14
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,012

    Re: Large Factorials

    Quote Originally Posted by rockx View Post
    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)!
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  15. #15
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,272

    Re: Large Factorials

    Quote Originally Posted by laserlight View Post
    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.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Page 1 of 2 12 LastLast

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center