factorial of very big number like 4096

[Dik T. Winter]

> 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

Too small to look for Mersenne primes. (The largest currently known
is 9.152.052 digits.)

 

[jmcgill]

Too small to look for Mersenne primes. (The largest currently known
is 9.152.052 digits.)

I have wondered how these are represented, say, by GIMPS.

I kinda-sorta get how the algorithm that GIMPS uses to multiply works,
at least by a casual reading of Knuth vol. 2, multiplication via a DFT.
But I don't yet grasp how an arbitrary precision multiply solves the
problem of representing the numbers (even just the factors) in something
like the Mersenne Prime search.

 

[SM Ryan]

(e-mail address removed) wrote:
# Hi
#
# How to write a program to get the factorial of 4096.
# I am working on a Linux m/c.

Use the gamma function from the math library.

 

[dcorbit]

(e-mail address removed) wrote:
# Hi
#
# How to write a program to get the factorial of 4096.
# I am working on a Linux m/c.

Use the gamma function from the math library.

Even assuming the cephes package and the qfloat version of gamma, it
will not handle an input of 4096:

../qcalc


Steve Moshier's command interpreter V1.3

Functions:
h help hex acos asin atan atantwo cbrt cos cot exp expten log logten
floor acosh asinh atanh cosh sinh tanh fac gamma lgamma jv yv ndtr
ndtri erf erfc pdtr pdtri incbet incbetinv incgam incgaminv ellie ellik
ellpe ellpk in gausshyp confhyp frexp ldexp polylog zeta pow sin sqrt
tan cmp bits digits intcvts double longdouble hexinput remainder dm tm
em take save system rem exit
Variables:
a b c d e f g h i j k l m n o p q r s t u v w x y z pi
Operators:
- , = + - * / ( )
* gamma(4096)
gamma(4096)


qexp overflow error

2.7552299095770043878042297237819677374315336293094360472858401246561324E5009
*

 

[Chris Dollin]

Chris Dollin said:



Why not start with 0! = 1 ?

Because I had a sudden attack of non-recall about 0! and went for
speed & safety.

It does need subtraction, though.

Subtraction of 1 from a C integer type (in the context of the OPs
post, where 4096 was the number to be banged), yes.

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

Then we differ in our reasonability criteria.

(Specifically, I wanted to avoid saying "infinite precision arithmetic",
and I think it's reasonable for "you don't have enough store" to
stop you working with big numbers: the contrast I was thinking of
was to "you can have big numbers of up to K-for-some-fixed-constant
digits". I suppose you can argue that my "unbounded" is bounded with
K = enough digits to fill available memory.)

 

[Richard Heathfield]

Chris Dollin said:

Subtraction of 1 from a C integer type (in the context of the OPs
post, where 4096 was the number to be banged), yes.

In the general case, however, we must be prepared for factorials such as
1000000000000000000000! - so we must be able to subtract 1 from a bignum.
(And yes, I know... "huge" is an utterly inadequate way to describe the
result of 1000000000000000000000! )

Then we differ in our reasonability criteria.

(Specifically, I wanted to avoid saying "infinite precision arithmetic",

How about "arbitrary precision arithmetic"?

<snip>

 

[Chris Dollin]

Chris Dollin said:


In the general case, however, we must be prepared for factorials such as
1000000000000000000000! - so we must be able to subtract 1 from a bignum.

One step at a time, I thought: but yes, in general.

(And yes, I know... "huge" is an utterly inadequate way to describe the
result of 1000000000000000000000! )

Pah. Your 1000000000000000000000! is a wimp, a wimpish wimp with knobs
taken off, before my mighty 1024!! ! We could just use adjectives with
emphasising markers so perhaps 1000000000000000000000! is huge! or is
that huge!! ? Or maybe huge, Huge, HUge, HUGe, HUGE, huge!, Huge!, ...

How about "arbitrary precision arithmetic"?

Better, although couldn't I be unboundedly arbitrary?

 

[pemo]

(e-mail address removed) said:

What is the logic to fill the below structure ?

const char *f4096[] =
{
"36427363894570419315658274703116469205712449235098",
"55429950938484780378749358324138749113885226019241",
"40891623559751804416272059989050947403083905593144",

[...]

Well, I started off by calculating 4096!, and storing that result in
a file. I then wrote the following program, feeding it that file as
input:

<snip>

A fine example of 'I'd rather write programs to write programs than write
programs'.

 

[CBFalconer]

Better, although couldn't I be unboundedly arbitrary?

How about you being an arbitrary bounder?

 

[Chris Dollin]

How about you being an arbitrary bounder?

I'm in no fit shape to do any kind of bounding. I can
manage a stroll to the station, even a brisk stroll,
but no bounding.

Are we far enough off topic yet?

 

[stdazi]

As someone alredy poitned out, you should stick with GMP :

==============
#include <gmp.h>
int main() {

mpz_t i;
mpz_init(i);
mpz_fac_ui(i, 4096);

return gmp_printf("%Zd\n" ,i);
}
==============

 

[T.M. Sommers]

Even assuming the cephes package and the qfloat version of gamma, it
will not handle an input of 4096:

Then compute the log of the gamma function instead.

 

[SM Ryan]

(e-mail address removed) wrote:
# SM Ryan wrote:
# > (e-mail address removed) wrote:
# > # Hi
# > #
# > # How to write a program to get the factorial of 4096.
# > # I am working on a Linux m/c.
# >
# > Use the gamma function from the math library.
#
# Even assuming the cephes package and the qfloat version of gamma, it
# will not handle an input of 4096:

Quality of implementation.

 

[Gordon Burditt]

How to write a program to get the factorial of 4096.

I am working on a Linux m/c.

You will need a very large integer type to represent this. This
is commonly done with a "bignum" library as other posters have
mentioned.

For example: 4096! is the product of 4096 numbers:

2048 of them are multiples of 2.
1024 of them are multiples of 4.
512 of them are multiples of 8.
256 of them are multiples of 16.
128 of them are multiples of 32.
64 of them are multiples of 64.
32 of them are multiples of 128.
16 of them are multiples of 256.
8 of them are multiples of 512.
4 of them are multiples of 1024.
2 of them are multiples of 2048.
1 of them is 4096.

so there are 4095 low-order zero bits in the result. And that only
includes the factors of two in the result, ignoring all the other
stuff. You can do a similar analysis of how many factors of 5 there
are, to determine how many trailing decimal zeroes there are in the
result.

 

[James Dow Allen]

After being insulted in another thread ("no one
advocates gets()" indeed!) I see a problem I can solve:

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);
}

First of all, the necessary datatype in this application isn't "long
long",
or even "long long long", but "long long Long long HUGE HUGE long
Long long VERY_HUGE big big big plump". Isn't all this in your manual?

That doesn't explain your memory overflow. I think I get more than
4096 smallish pushes with Linux, though I seldom try that many
(at least on purpose). I don't know about Windoze(tm):
Call me old-fashioned but I like to run under an Operating System.

Even compilers smart enough to find tail-recursion automatically,
won't find it in your fact(). You can change this to
iteration easily though.

PS: Working with large factorials is common, but don't we usually
use the logarithm of the factorial? You can get this with 4096 adds,
or just use Stirling's approximation.

Hope this helps with your homework,
James Dow Allen

 

[Ben Pfaff]

That doesn't explain your memory overflow. I think I get more than
4096 smallish pushes with Linux, though I seldom try that many
(at least on purpose). I don't know about Windoze(tm):
Call me old-fashioned but I like to run under an Operating System.

The OP's function does not limit recursion to 4096 levels.

 

[Old Wolf]

Look up the format specifiers for long long int and unsigned long long int
when you get a minute. %ld is for long int, not long long int.

What is this 'long long int' of which you speak? My compiler,
in conforming mode, doesn't support it...

 

[Old Wolf]

so there are 4095 low-order zero bits in the result. And that only
includes the factors of two in the result, ignoring all the other
stuff. You can do a similar analysis of how many factors of 5 there
are, to determine how many trailing decimal zeroes there are in the
result.

An interesting problem -- what's the last non-zero digit of one
million factorial?

 

[Richard Heathfield]

Old Wolf said:

What is this 'long long int' of which you speak? My compiler,
in conforming mode, doesn't support it...

Neither does mine. Nevertheless, the OP was using long long, so presumably
he has a C99 compiler. C99 is topical here.

If, however, you are suggesting that the use of long long int renders the
code less portable than it might be, then I agree entirely.

 

[Richard Heathfield]

Old Wolf said:

An interesting problem -- what's the last non-zero digit of one
million factorial?

1 (assuming binary notation).