473,836 Members | 1,487 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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:

(please don't top-post)
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().
Factorial doesn't /need/ 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.
Why not start with 0! = 1 ?

<snip>
Factorial doesn't /need/ addition.
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?

Please don't top-post. Your replies belong following or interspersed
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
program, and maybe we can help you fix it.

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
below. Your answer belong after, or intermixed with, the SNIPPED
quoted material.

--
Some informative links:
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
on your application.

--
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.

Similar topics

8
11364
by: salman | last post by:
this program is giving compile time error. so plse ge me the logic of factorial # include <iostream.h> # include <math.h> void main() { int f,sum=0,i,j,n; cout<<"\nEnter Number: ";
3
8024
by: Sugandh Jain | last post by:
Hi. How to write a function that will return me the factorial (say in a string) for the any positive integer it takes? When we find a factorial of even say 2000 or a higher number, it will be very big to be accomodated in int or long datatype. Regards, Sugandh
0
9814
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10838
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10544
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10585
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9369
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
6977
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5821
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4010
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3111
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.