468,463 Members | 2,022 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 6251
me********@aol.com wrote:
I use the GMP library which does arbitrary precision integers as large
as your memory will allow (using base 65536 I believe).
Their documentation says:
"The speed of GMP is achieved by using fullwords
as the basic arithmetic type..."

So this would suggest base 2^32 in a 32 bits machine.

Sep 10 '06 #51

Spiros Bousbouras wrote:
me********@aol.com wrote:
I use the GMP library which does arbitrary precision integers as large
as your memory will allow (using base 65536 I believe).

Their documentation says:
"The speed of GMP is achieved by using fullwords
as the basic arithmetic type..."

So this would suggest base 2^32 in a 32 bits machine.
I must have been thinking of Python.

Sep 10 '06 #52
....
I use the GMP library which does arbitrary precision integers as large
as your memory will allow (using base 65536 I believe). I use it to
study the Collatz Conjecture where a lot of stuff is exponential so
big numbers are essential.
I have written such a library myself. The basis is a libary of routines
that work with a fixed size. That library is highly machine dependent.
It uses arrays of integers using some base that can range from 2 ** 16 to
2 ** 32. Also the number of elements in the arrays range such that the
maximal number that can be represented is about 10 ** 280. This
sublibrary is highly optimised, using assembler, for some 40 machine/
compiler combinations. On top of it there is a library using arbitrary
precision, allocating and reallocating memory when needed. It is all
not so very difficult to do. And I think that the library Elijah
Cardon wrote about does something similar.
There is, however, a limitation: the power function considers
an exponent of 32 bits or more "outrageous", so the above
formula only works up to k=10. You can have bigger numbers,
you just can't get there by that path.
Or you write your own wrapper around that situation. I do not think
that would be very difficult.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Sep 11 '06 #53
In article <11**********************@e3g2000cwe.googlegroups. com"Spiros Bousbouras" <sp****@gmail.comwrites:
me********@aol.com wrote:
I use the GMP library which does arbitrary precision integers as large
as your memory will allow (using base 65536 I believe).

Their documentation says:
"The speed of GMP is achieved by using fullwords
as the basic arithmetic type..."

So this would suggest base 2^32 in a 32 bits machine.
Perhaps. But if a machine does not have a 32x32 to 64 bit multiply,
you are better off with a base 2 ** 16 base.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Sep 11 '06 #54
Richard Heathfield wrote:
Elijah Cardon said:
>Richard Heathfield wrote:
"How big do we want?" is a significant question for bignum library authors.
>I think the way to go is to change the base and represent with entries
in an array. I've never met an interesting number larger than ten to
the fifty-five.

They happen sometimes, in cryptography.
>Am I right to think that if you have base ten thousand,
then you could represent it in an array of ints that is of length 15? EC

Personally, I use base 256, which I can represent in any number of unsigned
chars I like. If I worked to base 65536, I could represent it in any number
of unsigned shorts I like.

But let's take your 10^55. Or, if you prefer, 44!, which is
2,658,271,574,788,448,768,043,625,811,014,615,890, 319,638,528,000,000,000

If you wanted to stay in a 10-based base, though, you could do worse than
base 1000. You'd need an array of 19 ints for numbers of the magnitude you
require. Or perhaps you could use base 1000000 and an array of 10 long
ints. But base 1000 is attractive because printing it is so easy, in
locales where numbers are divided into groups of three for printing:
<snip>
#include <stdio.h>

#define highest_index 19

int main(void)
{
int n[highest_index];
int flag, i;
char thousands_separator = ',';

for(i = highest_index; i >= 0; i--)
{
n[i] = 500 + i;
}

for(i = highest_index; i 0 && n[i] == 0; i++)
{
continue;
}
while(i 1)
{
printf("%03d%c", n[i], thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n[i]);
return 0;
}

I'm missing the point here. Before I actually tried to create a
meaningful large number, I wanted to make sure I could get output at all
with any old numbers. So I populate the array. If highest_index is
positive, I don't see how the output loop necessarily terminates. It's a
good bet that I'm confused about left and right. EC

Sep 14 '06 #55
Elijah Cardon said:
Richard Heathfield wrote:
int n[highest_index];
int flag, i;
char thousands_separator = ',';

for(i = highest_index; i >= 0; i--)
{
n[i] = 500 + i;
}

for(i = highest_index; i 0 && n[i] == 0; i++)
{
continue;
}
while(i 1)
{
printf("%03d%c", n[i], thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n[i]);
return 0;
}

I'm missing the point here.
No, you're only missing the realisation that ol' Richard still can't write
code-on-the-fly.

What the code is *supposed* to do is whizz through your upper ints, ignoring
zeros, and then whizz through everything else, printing each int in turn,
followed if need be by a comma. And every int *except the first* (another
bug in the above code!) should be padded to three bytes with 0s. Whether
the loop proceeds from left to right or right to left depends entirely on
whether your array uses n[0] for the least, or the most, significant bigit,
which is your decision, not mine.

This is sophomore-level code, so naturally I got it wrong. I never even
learned Morse, let alone sophomore.

--
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 14 '06 #56

"Richard Heathfield" <in*****@invalid.invalidwrote in message
news:Tr********************@bt.com...
Elijah Cardon said:
>Richard Heathfield wrote:
int n[highest_index];
int flag, i;
char thousands_separator = ',';

for(i = highest_index; i >= 0; i--)
{
n[i] = 500 + i;
}

for(i = highest_index; i 0 && n[i] == 0; i++)
{
continue;
}
while(i 1)
{
printf("%03d%c", n[i], thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n[i]);
return 0;
}

I'm missing the point here.

No, you're only missing the realisation that ol' Richard still can't write
code-on-the-fly.

What the code is *supposed* to do is whizz through your upper ints,
ignoring
zeros, and then whizz through everything else, printing each int in turn,
followed if need be by a comma. And every int *except the first* (another
bug in the above code!) should be padded to three bytes with 0s. Whether
the loop proceeds from left to right or right to left depends entirely on
whether your array uses n[0] for the least, or the most, significant
bigit,
which is your decision, not mine.

This is sophomore-level code, so naturally I got it wrong. I never even
learned Morse, let alone sophomore.
No re Morse then. Preliminary agenda is document N1170 on the ISO
JTC1/SC22/WG14 Web site.

Godammit, Heathfield, I ran that routine and the only output it would give
me is 97236 . I sometimes think that we on differing sides of the Atlantic
are talking past each other.

Luckily, for me, I've got Dr. Kelly on disc to make up for your
shortcomings. If he is the English answer to Knuth, what was the question?
EC
Sep 15 '06 #57
On Sun, 10 Sep 2006 07:09:35 +0000, Richard Heathfield
<in*****@invalid.invalidwrote:
<snip: bigints (but unfortunately not bigbums :-)>
If you wanted to stay in a 10-based base, though, you could do worse than
base 1000. You'd need an array of 19 ints for numbers of the magnitude you
[u]short is enough for 1000. Or even 10_000.
require. Or perhaps you could use base 1000000 and an array of 10 long
ints. But base 1000 is attractive because printing it is so easy, in
locales where numbers are divided into groups of three for printing:
[u]long allows 1_000_000_000 (my billion, your thousand million IIUC).
Which is 9 decimal digits, and 9 is just a neat number in general, and
can easily (and usually efficiently) be broken into 3 groups of three;
but (approximately) 30 bits, and 30 is the onset of uncoolness.
(Also for some reason the end of a text in traditional press.)
for(i = highest_index; i 0 && n[i] == 0; i++)
{
continue;
}
Did you want that to be i-- for bigendian? And maybe i 1 if you use
[0] for the (allocated?) length (as I once did)?
while(i 1)
{
printf("%03d%c", n[i], thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n[i]);
You want a (post)decrement of i in there. And 1 or 0 as above.

Plus in serious use I'd want this (re)directable to a FILE*, or even a
callback which could do something other than C's idea of a file.
Like, say, (C's idea of) a string.

- David.Thompson1 at worldnet.att.net
Sep 21 '06 #58
Dave Thompson said:
On Sun, 10 Sep 2006 07:09:35 +0000, Richard Heathfield
<in*****@invalid.invalidwrote:
<snip: bigints (but unfortunately not bigbums :-)>
>If you wanted to stay in a 10-based base, though, you could do worse than
base 1000. You'd need an array of 19 ints for numbers of the magnitude
you

[u]short is enough for 1000. Or even 10_000.
Sure, but unless space is at a premium, does it matter?

<abysmal code snipped>

Er, yes. We all have off-days. </blush>
Plus in serious use I'd want this (re)directable to a FILE*,
In serious use, I wouldn't be using base 1000. :-) In my own lib, yes, I
have routines for turning a bignum into a string and for writing it through
a FILE *.

--
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 21 '06 #59

### This discussion thread is closed

Replies have been disabled for this discussion.