factorial of very big number like 4096

[Michael Wojcik]

Old Wolf said:


1 (assuming binary notation).

1 (assuming base-1000000! notation).

(On a more serious note: if we're using base 10, the least-
significant non-zero digit has to be one of {2,4,6,8}, but further
analysis is beyond my skills, at least for casual Usenet speculation.)

 

[jacob navia]

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

Compiler in "conforming mode" ???

Conforming to what?

Standard C has short int, int, long int and long long int.

You are conforming to another, not the current C standard.

P.S.

Just add
-std=c99 if you use gcc

 

[Keith Thompson]

Compiler in "conforming mode" ???

Conforming to what?

Conforming to C89/C90, as Richard has made extremely clear many times.

Standard C has short int, int, long int and long long int.

You are conforming to another, not the current C standard.

P.S.

Just add
-std=c99 if you use gcc

With "-std=c89", gcc conforms to the C89/C90 (undoubtedly with a few
bugs here and there).

With "-std=c99", gcc does not fully conform to *any* standard.

So "-std=c89" (or "-ansi") is the *only* "conforming mode" available
for gcc, and it will be until gcc fully implements C99.

But you knew that already.

Many C compilers implement *some* of the new features in C99, but very
few implement all of them, and different compilers implement different
sets of features. The best way to write maximally portable C code is
to limit yourself to C89/C90, while avoiding any conflicts with C99
(e.g., don't use implicit int, and don't use "restrict" as an
identifier). With gcc, "-std=c89", along with some other options,
does a decent job of warning about code that doesn't meet these limits
(it probably won't warn about "restrict", but that's easy enough to
handle manually).

There are probably some C99 features that are supported by almost all
compilers, such as "//" comments. So it's tempting to write code in
the subset of C99 that includes all of C90 plus "//" comments. But
there is no set of options for gcc that will permit "//" features and
still warn about C99 features that are not yet portable.

There is still a real price for using C99 features. If you're willing
to pay that price, that's fine. Richard is not, for perfectly good
reasons that he has explained before.

 

[Elijah Cardon]

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


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

Take n to be 4095. Root 2 pi n is going to be 160. n over e is going to
1516. 1.516 exceeds three halves. Three halves excceds one. So the number
we're looking at is bounded below by 160 times quatity one thousand to the
4095. To represent in decimal fashion would therefore require 2+3*4095>12
thousand places. Is bigbum.h any help in working with numbers of this size
in C? EC

 

[Richard Heathfield]

Elijah Cardon said:

To represent [4096!] in decimal fashion would therefore require
2+3*4095>12 thousand places.

Er, so what? As we've already seen, it is possible to deal with numbers as
large as that in C, if you're prepared or were prepared at some point in
the past to take a little time and effort or to pinch someone else's
library.

 

[Elijah Cardon]

Elijah Cardon said:

To represent [4096!] in decimal fashion would therefore require
2+3*4095>12 thousand places.

Er, so what? As we've already seen, it is possible to deal with numbers as
large as that in C, if you're prepared or were prepared at some point in
the past to take a little time and effort or to pinch someone else's
library.

Well, this looks like the business part of bignum.h:

#define LITTLENUM_NUMBER_OF_BITS (16)
#define LITTLENUM_RADIX (1 << LITTLENUM_NUMBER_OF_BITS)
#define LITTLENUM_MASK (0xFFFF)
#define LITTLENUM_SHIFT (1)
#define CHARS_PER_LITTLENUM (1 << LITTLENUM_SHIFT)
#ifndef BITS_PER_CHAR
#define BITS_PER_CHAR (8)
#endif

typedef unsigned short LITTLENUM_TYPE;

/* JF truncated this to get around a problem with GCC */
#define LOG_TO_BASE_2_OF_10 (3.3219280948873623478703194294893901758651)
/* WARNING: I haven't checked that the trailing digits are correct! */

/* lengths are in sizeof(littlenum)s */

int bignum_copy (LITTLENUM_TYPE * in, int in_length,
LITTLENUM_TYPE * out, int out_length);

/* end of bignum.h */
It seems to me that this is going after long numbers as opposed to big
numbers. Long numbers are like pi. Borwein and Borwein have an
excellent book on this that I read maybe a decade ago(_Pi and the AGM_).
So if you have pi to 13000 digits and say, "we're just going to remove
the decimal point", then you'd have a big number, but a big number of no
consequence.

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

 

[Richard Heathfield]

Elijah Cardon said:

Elijah Cardon said:

To represent [4096!] in decimal fashion would therefore require
2+3*4095>12 thousand places.

Er, so what? As we've already seen, it is possible to deal with numbers
as large as that in C, if you're prepared or were prepared at some point
in the past to take a little time and effort or to pinch someone else's
library.

Well, this looks like the business part of bignum.h:

/* end of bignum.h */
It seems to me that this is going after long numbers as opposed to big
numbers.

"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:

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

 

[Spiros Bousbouras]

Take n to be 4095. Root 2 pi n is going to be 160. n over e is going to
1516. 1.516 exceeds three halves. Three halves excceds one. So the number
we're looking at is bounded below by 160 times quatity one thousand to the
4095. To represent in decimal fashion would therefore require 2+3*4095>12
thousand places. Is bigbum.h any help in working with numbers of this size
in C? EC

If there is indeed some library somewhere called
bigbum then I'd love to know more about it.

 

[Elijah Cardon]

If there is indeed some library somewhere called
bigbum then I'd love to know more about it.

'b' is next to 'n' and I have large fingers and hayfever that
occasionally reduces my vision. You can't see the other newsgroups I
subscribe to, can you? EC

 

[Dik T. Winter]

> I've never met an interesting number larger than ten to
> the fifty-five.

Never met an RSA key?

 

[mensanator]

Elijah Cardon said:

To represent [4096!] in decimal fashion would therefore require
2+3*4095>12 thousand places.

Er, so what? As we've already seen, it is possible to deal with numbers as
large as that in C, if you're prepared or were prepared at some point in
the past to take a little time and effort or to pinch someone else's
library.

Well, this looks like the business part of bignum.h:

#define LITTLENUM_NUMBER_OF_BITS (16)
#define LITTLENUM_RADIX (1 << LITTLENUM_NUMBER_OF_BITS)
#define LITTLENUM_MASK (0xFFFF)
#define LITTLENUM_SHIFT (1)
#define CHARS_PER_LITTLENUM (1 << LITTLENUM_SHIFT)
#ifndef BITS_PER_CHAR
#define BITS_PER_CHAR (8)
#endif

typedef unsigned short LITTLENUM_TYPE;

/* JF truncated this to get around a problem with GCC */
#define LOG_TO_BASE_2_OF_10 (3.3219280948873623478703194294893901758651)
/* WARNING: I haven't checked that the trailing digits are correct! */

/* lengths are in sizeof(littlenum)s */

int bignum_copy (LITTLENUM_TYPE * in, int in_length,
LITTLENUM_TYPE * out, int out_length);

/* end of bignum.h */
It seems to me that this is going after long numbers as opposed to big
numbers. Long numbers are like pi. Borwein and Borwein have an
excellent book on this that I read maybe a decade ago(_Pi and the AGM_).
So if you have pi to 13000 digits and say, "we're just going to remove
the decimal point", then you'd have a big number, but a big number of no
consequence.

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

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.

For example, the formula for the ith kth Generation Type [1,2]
Mersenne Hailstone is:

a(i,k) = 2**(6*((i - 1)*9**(k - 1) + (9**(k - 1) - 1)/2 + 1) - 1) - 1

for which (1,10) gives you a number over a billion bits. It'll do
paltry calculations like 4096! easily.

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.

 

[Spiros Bousbouras]

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.

 

[mensanator]

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.

 

[Dik T. Winter]

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

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

 

[Elijah Cardon]

Elijah Cardon said:

"How big do we want?" is a significant question for bignum library authors.


They happen sometimes, in cryptography.


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 = 500 + i;
}

for(i = highest_index; i > 0 && n == 0; i++)
{
continue;
}
while(i > 1)
{
printf("%03d%c", n, thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n);
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

 

[Richard Heathfield]

Elijah Cardon said:

Richard Heathfield wrote:
int n[highest_index];
int flag, i;
char thousands_separator = ',';

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

for(i = highest_index; i > 0 && n == 0; i++)
{
continue;
}
while(i > 1)
{
printf("%03d%c", n, thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n);
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.

 

[Elijah Cardon]

Elijah Cardon said:

Richard Heathfield wrote:
int n[highest_index];
int flag, i;
char thousands_separator = ',';

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

for(i = highest_index; i > 0 && n == 0; i++)
{
continue;
}
while(i > 1)
{
printf("%03d%c", n, thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n);
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

 

[Dave Thompson]

On Sun, 10 Sep 2006 07:09:35 +0000, Richard Heathfield

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

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:

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 == 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, thousands_separator);
flag = 1;
}
printf(flag ? "%03d\n" : "%d\n", n);

You want a (post)decrement of i in there. And 1 or 0 as above.

I see you already caught the leading-zeros on 1-unit vs more.

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

 

[Richard Heathfield]

Dave Thompson said:

On Sun, 10 Sep 2006 07:09:35 +0000, Richard Heathfield

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

short is enough for 1000. Or even 10_000.

Sure, but unless space is at a premium, does it matter?

<abysmal code snipped>

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