
November 21st, 2013, 08:12 PM
#1
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.

November 21st, 2013, 09:15 PM
#2
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

November 21st, 2013, 09:41 PM
#3
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(value1);
}
}

November 21st, 2013, 09:56 PM
#4
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

November 22nd, 2013, 07:42 AM
#5
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.tsmresources.com/alists/fact.html has 199 and 999
http://www.wattpad.com/4855alisto...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.

November 22nd, 2013, 08:07 AM
#6
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.

November 24th, 2013, 01:48 PM
#7
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 09 and doing so, each individual digit of the large calculated numbers be stored in each NODE.
So will this be possible?

November 24th, 2013, 02:00 PM
#8
Re: Large Factorials
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.

November 24th, 2013, 09:57 PM
#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
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.

November 25th, 2013, 07:00 PM
#10
Re: Large Factorials
Considering the above, could it help solve the following:
x = (n!  (n 1)!) + ((n2)!  (n  3)!) ..............  1!
assuming n is an even number or
(n!  (n 1)!) + ((n2)!  (n  3)!) .............. + 1!
assuming n is an odd number

November 25th, 2013, 07:10 PM
#11
Re: Large Factorials
Originally Posted by rockx
Considering the above, could it help solve the following:
x = (n!  (n 1)!) + ((n2)!  (n  3)!) ..............  1!
assuming n is an even number or
(n!  (n 1)!) + ((n2)!  (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

November 25th, 2013, 07:36 PM
#12
Re: Large Factorials
so what is a better way of doing this

November 26th, 2013, 12:53 AM
#13
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, rearrange your formula to minimise the number of computations and implement the code.

November 26th, 2013, 01:50 AM
#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)!
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

November 26th, 2013, 05:08 AM
#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, rearrange 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.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
