473,836 Members | 1,487 Online

# factorial of very big number like 4096

Hi

How to write a program to get the factorial of 4096.
I am working on a Linux m/c.

Best Regards,
Subra

Sep 5 '06
58 6761
ma*********@gma il.com wrote:
Hi Richard,
I started with the below kind of program which is not working because
of memory overflow.

long long fact(long long n)
{
return n*fact(n-1);
}
int main()
{
printf("%ld",fa ct(4096));
}

Now I am planning to write the linked list version of addition().
Which inturn will be used by the multiplication( ). That inturn by the
fact(). Is these unlimited size data types are already there ?
A recursive function should have a stop condition ensuring it
terminates.
In this case you want to stop when n reaches 0.
long long fact(long long n)
{
if(n == 0) /* 0! is 1*/
return 1;
else
return n*fact(n-1); /* n! is n*(n -1)! */
}

Rewriting the function to be iterative is likely a better choice.

However, a long long type might not be able to hold a value big enough
to represent the factorial of big numbers. You might resort to doing
all the math yourself (atleast subtraction and multiplication) e.g. in
a similar fashion as you'd do the math on paper. You could use a
postitional numbering system built up from primititive C types, e.g.
an array of ints.
There are libriaries available for various systems doing the math
for you though, generally referred to as bignum libraries.
Sep 5 '06 #11
In article <11************ **********@m73g 2000cwd.googleg roups.com>,
<ma*********@gm ail.comwrote:
>I started with the below kind of program which is not working because
of memory overflow.

long long fact(long long n)
{
return n*fact(n-1);
}
int main()
{
printf("%ld",fa ct(4096));
}
So what happened when you tried to compute 3! with it?

-- Richard
Sep 5 '06 #12
ma*********@gma il.com wrote:

I started with the below kind of program which is not working because
of memory overflow.

long long fact(long long n)
{
return n*fact(n-1);
}
A good starting test case is to check that your code computes
1! = 1 correctly.
int main()
{
printf("%ld",fa ct(4096));
}

Now I am planning to write the linked list version of addition().
Which inturn will be used by the multiplication( ).
And in this case, it doesn't need fully general multiplication either.
That inturn by the
fact().
Is these unlimited size data types are already there ?
There are libraries out there that do unbounded-precision arithmetic,
yes.

But what you can manage with is code that can multiply an
unbounded-precision number by an int. (And something to
print such an int out - which you can hack by working in
base 10, or better 10000.).

--
Chris "seeker" Dollin
Nit-picking is best done among friends.

Sep 5 '06 #13
Chris Dollin said:

<snip>
>
A good starting test case is to check that your code computes
1! = 1 correctly.

<snip>
It does need subtraction, though.

<snip>
There are libraries out there that do unbounded-precision arithmetic,
yes.
No, there aren't, for any reasonable definition of "unbounded" .

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 5 '06 #14
ma*********@gma il.com wrote:

What is the logic to fill the below array?

with properly trimmed quotes. See the majority of other posts in the
newsgroup, or:
<http://www.caliburn.nl/topposting.html >

Brian
Sep 5 '06 #15
Richard Heathfield <in*****@invali d.invalidwrites :
Chris Dollin said:
[...]
>There are libraries out there that do unbounded-precision arithmetic,
yes.

No, there aren't, for any reasonable definition of "unbounded" .
There are libraries that do arithmetic on quantities whose magnitude
is limited only by available memory.

I won't claim that that's a reasonable definition of "unbounded" , but
it's good enough for many applications that don't *really* need
unbounded magnitudes.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Sep 5 '06 #16
Keith Thompson a écrit :
Richard Heathfield <in*****@invali d.invalidwrites :
>>Chris Dollin said:

[...]
>>>There are libraries out there that do unbounded-precision arithmetic,
yes.

No, there aren't, for any reasonable definition of "unbounded" .

There are libraries that do arithmetic on quantities whose magnitude
is limited only by available memory.

I won't claim that that's a reasonable definition of "unbounded" , but
it's good enough for many applications that don't *really* need
unbounded magnitudes.
Using a relatively small amount of memory for the numbers
in a PC, i.e. 1GB numbers. Supposing 8GB main RAM,
and 16GB swap that would work. You would hold
up to 3 or 4 numbers in core RAM, enough for the
four operations and some intermeidate storage.

We have then numbers of :

1 073 741 824 bytes, i.e. 8 589 934 592 bits.

Dividing by 3 this means (in decimal) numbers of
2 863 311 530 digits, what could be enough for
many applications.

:-)
In a more reasonable realm, 1MB numbers hold 8 388 608
bits or 2 796 202 decimal digits. With a run of the mill
PC with 1GB RAM we can hold several of those numbers
in RAM. No problems!

Not unbounded of course, but the bounds are fairly large
Sep 5 '06 #17
Keith Thompson said:
Richard Heathfield <in*****@invali d.invalidwrites :
>Chris Dollin said:
[...]
>>There are libraries out there that do unbounded-precision arithmetic,
yes.

No, there aren't, for any reasonable definition of "unbounded" .

There are libraries that do arithmetic on quantities whose magnitude
is limited only by available memory.
Et viola, monsieur, une bound! :-)
I won't claim that that's a reasonable definition of "unbounded" , but
it's good enough for many applications that don't *really* need
unbounded magnitudes.
Sure. Just being my usual nittypicky self.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 5 '06 #18
*** top-posting fixed ***
ma*********@gma il.com wrote:
Richard Heathfield wrote:
>ma*********@gma il.com said:
>>How did you calculated 4096!. My calc failed and even my program !!

Aha! Some evidence that you've had a go yourself. Let's see your

I started with the below kind of program which is not working
because of memory overflow.
.... snip ...
>
Now I am planning to write the linked list version of addition().
Which inturn will be used by the multiplication( ). That inturn by
the fact(). Is these unlimited size data types are already there ?
Don't top-post, or you will get no help here. See the links
quoted material.

--
news:news.annou nce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html
Sep 5 '06 #19
ma*********@gma il.com wrote:
>
How to write a program to get the factorial of 4096.
I am working on a Linux m/c.
OT, but you might want to look at the gamma function, depending

--
Thomas M. Sommers -- tm*@nj.net -- AB2SB

Sep 5 '06 #20

This thread has been closed and replies have been disabled. Please start a new discussion.