very very very long integer

S

shanx__=|;-

hi i need some help regarding use of very very long integer datatype
in 'c'.. i need it to store result of large number's factorial..

if someone can healp it would be a delight..
 
K

Karthik Kumar

shanx__=|;- said:
hi i need some help regarding use of very very long integer datatype
in 'c'.. i need it to store result of large number's factorial..

if someone can healp it would be a delight..

As such C cannot support it.
But what you could do is to implement a linked list of long
integers yourselves and define the operations accordingly.
That would be interesting.
 
S

shanx__=|;-

Ivan Vecerina said:
Someone, or something ?
http://www.google.com/search?q=bigint+C+library

Several 'big integer' libraries have already been implemented.


hth -Ivan

i actually need to use the datatype to find factorial of any number n
the ans may be anything like 999448849493945848385845868546854 so
need that sort of integer datatype.... i know ive to build this my
self. ya one option can be linked list of long integers. thanx for
replyin...
 
S

shanx__=|;-

Ivan Vecerina said:
Someone, or something ?
http://www.google.com/search?q=bigint+C+library

Several 'big integer' libraries have already been implemented.


hth -Ivan

ya i know that there are several lib's there with which we can use
bigger integers , but the point is i wanna have my own datatype.. i
wanna know how this thing can be done eg. using linked list is one
way..

thanx for ur repy..
 
J

jacob navia

shanx__=|;- said:
hi i need some help regarding use of very very long integer datatype
in 'c'.. i need it to store result of large number's factorial..

if someone can healp it would be a delight..
The lcc-win32 compiler comes with a bignum package in the standard
distribution.
This is an extension to the C language of lcc-win32.
#include <stdio.h>
#include <bignums.h>
pBignum factorial(int n)
{
pBignum b = 1,r=1;

while (n) {
r = b*r;
b++;
n--;
}
return r;
}
int main(void)
{
pBignum b = factorial(100);
char buffer[4096];

quadtoa(b,buffer);
printf("%s\n",buffer);
}
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639
76156518286253697920827223758251185210916864000000000000000000000000
http://www.cs.virginia.edu/~lcc-win32
 
?

=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=

shanx__=|;- said:
i actually need to use the datatype to find factorial of any number n
the ans may be anything like 999448849493945848385845868546854 so
need that sort of integer datatype.... i know ive to build this my
self. ya one option can be linked list of long integers. thanx for
replyin...

Check if you can use gmp.
http://www.swox.com/gmp/
 
F

Flash Gordon

The lcc-win32 compiler comes with a bignum package in the standard
distribution.
This is an extension to the C language of lcc-win32.
#include <stdio.h>
#include <bignums.h>

<snip>

Are you offering to provide the source code (implemented in standard C,
not your strange language) for this library to the OP for free? If not
then stop advertising your compiler and libraries for a language similar
to C.
 
J

jacob navia

Flash said:
<snip>

Are you offering to provide the source code (implemented in standard C,
not your strange language) for this library to the OP for free? If not
then stop advertising your compiler and libraries for a language similar
to C.
 
J

jacob navia

Flash said:
<snip>

Are you offering to provide the source code (implemented in standard C,
not your strange language) for this library to the OP for free? If not
then stop advertising your compiler and libraries for a language similar
to C.
The library is written by Mr Mike Scott, for the first time in 1989. I
rewrote most of it in 386 asm, and it is quite fast now. The newer
versions of this library are available in standard C at:
ftp.compapp.dcu.ie/pub/crypto/miracl.zip

It has a C++ interface, very similar to what my compiler does.
Number operations can be used to naturally express operations on
numbers.

I had cancelled my message. I cancelled it 5 minutes after I sent
it, so you are really fast. Congratulations.

I put here the rest of my message for documentation, since
I cancelled it:

#include <stdio.h>
#include <bignums.h>
pBignum factorial(int n)
{
pBignum b = 1,r=1;

while (n) {
r = b*r;
b++;
n--;
}
return r;
}
int main(void)
{
pBignum b = factorial(100);
char buffer[4096];

quadtoa(b,buffer);
printf("%s\n",buffer);
}
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639
76156518286253697920827223758251185210916864000000000000000000000000
http://www.cs.virginia.edu/~lcc-win32

In standard C that would be:
pBignum factorial(int n)
{
pBignum b = long2quad(1);
pBignum r=long2quad(1);

while (n) {
quadmult(b,r,r);
quadadd(b,long2quad(1),b);
n--;
}
return r;
}

Great deal.
 
C

CBFalconer

shanx__=|;- said:
i actually need to use the datatype to find factorial of any number
n the ans may be anything like 999448849493945848385845868546854
so need that sort of integer datatype.... i know ive to build this
my self. ya one option can be linked list of long integers. thanx
for replyin...

You can try the following. If the exact value of approximately
93326215443944102190000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.0
isn't big enough you can extend the primes table used.


/* compute factorials, extended range
on a 32 bit machine this can reach fact(15) without
unusual output formats. With the prime table shown
overflow occurs at 101.

Public domain, by C.B. Falconer. 2003-06-22
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* 2 and 5 are handled separately
Placing 2 at the end attempts to preserve such factors
for use with the 5 factor and exponential notation
*/
static unsigned char primes[] = {3,7,11,13,17,19,23,29,31,37,
41,43,47,53,57,59,61,67,71,
/* add further primes here -->*/
2,5,0};
static unsigned int primect[sizeof primes]; /* = {0} */

static double fltfact = 1.0;

static
unsigned long int fact(unsigned int n, unsigned int *zeroes)
{
unsigned long val;
unsigned int i, j, k;

#define OFLOW ((ULONG_MAX / j) < val)

/* This is a crude mechanism for passing back values */
for (i = 0; i < sizeof primes; i++) primect = 0;

for (i = 1, val = 1UL, *zeroes = 0; i <= n; i++) {
fltfact *= i; /* approximation */
j = i;
/* extract exponent of 10 */
while ((0 == (j % 5)) && (!(val & 1))) {
j /= 5; val /= 2;
(*zeroes)++;
}
/* Now try to avoid any overflows */
k = 0;
while (primes[k] && OFLOW) {
/* remove factors primes[k] */
while (0 == (val % primes[k]) && OFLOW) {
val /= primes[k];
++primect[k];
}
while (0 == (j % primes[k]) && OFLOW) {
j /= primes[k];
++primect[k];
}
k++;
}

/* Did we succeed in the avoidance */
if (OFLOW) {
#if DEBUG
fprintf(stderr, "Overflow at %u, %lue%u * %u\n",
i, val, *zeroes, j);
#endif
val = 0;
break;
}
val *= j;
}
return val;
} /* fact */

int main(int argc, char *argv[])
{
unsigned int x, zeroes;
unsigned long f;

if ((2 == argc) && (1 == sscanf(argv[1], "%u", &x))) {
if (!(f = fact(x, &zeroes))) {
fputs("Overflow\n", stderr);
return EXIT_FAILURE;
}

printf("Factorial(%u) == %lu", x, f);
if (zeroes) printf("e%u", zeroes);
for (x = 0; primes[x]; x++) {
if (primect[x]) {
printf(" * pow(%d,%d)", primes[x], primect[x]);
}
}
putchar('\n');
printf("or approximately %.0f.\n", fltfact);
return 0;
}
fputs("Usage: fact n\n", stderr);
return EXIT_FAILURE;
} /* main */
 
F

Flash Gordon

The library is written by Mr Mike Scott, for the first time in 1989. I
rewrote most of it in 386 asm, and it is quite fast now.

So your implementation won't run on one of my computers or most of the
systems I have programmed for.
The newer
versions of this library are available in standard C at:
ftp.compapp.dcu.ie/pub/crypto/miracl.zip

Had you pointed to that standard C implementation in the first place I
would have had no complaint.
It has a C++ interface, very similar to what my compiler does.
Number operations can be used to naturally express operations on
numbers.

Well, your use of operator overloading is OT here.
I had cancelled my message. I cancelled it 5 minutes after I sent
it, so you are really fast. Congratulations.

<snip>

Many news servers do not honour cancels so these days issuing cancel
generally does not do much good. In this case, I can be certain that
your message was not downloaded on to my systems until approximately 10
minutes after it was posted since I have an hourly cron job doing the
pull in to leafnode and you posted at about 10 minutes to the hour.
 
K

Keith Thompson

i actually need to use the datatype to find factorial of any number n
the ans may be anything like 999448849493945848385845868546854 so
need that sort of integer datatype.... i know ive to build this my
self. ya one option can be linked list of long integers. thanx for
replyin...

You should be aware that, unless you find a clever shortcut that
avoids doing all the multiplcations, computing the factorial of
999448849493945848385845868546854 on any current system will take
longer than the expected lifetime of the universe. Storing the result
would also be an interesting challenge.

There are several arbitrary-precision software packages floating
around which can do calculations limited only by available time and
memory. The GNU "gmp" package is one of them.
 
O

osmium

Keith Thompson said:
You should be aware that, unless you find a clever shortcut that
avoids doing all the multiplcations, computing the factorial of
999448849493945848385845868546854 on any current system will take
longer than the expected lifetime of the universe. Storing the result
would also be an interesting challenge.

I haven't been able to detect what the real requirements/wants of the OP
are. But I would suggest the OP start by using a Stirling approximation to
see if what he wants to do is realistic. If it takes more than a few tens
of years to run, or more than 80 GB to store, this seems like a good time to
stop the effort.

Assuming it is doable with his real numbers, I would suggest an array that
can grow, with each array element being a BCD representation of the number.
This trivializes the conversions necessary for a human to see how things are
going. The array that grows will be much faster than a linked list.
 
I

Ivan Vecerina

Yes, but as the OP said in the paragraph you quoted:
"the ans(wer) may be anything like 999448849493945848385845868546854"
I believe he's talking about the *result* of the factorial,
so this should be quite reasonable to handle.
(this said, obviousy the provided number cannot be the actual value
of an integer factorial function -- there would be trailing zeroes...)


Cheers,
Ivan
 
C

CBFalconer

Ivan said:
Keith Thompson said:
(e-mail address removed) (shanx__=|;-) writes:
[...]
i actually need to use the datatype to find factorial of any number
n the ans may be anything like 999448849493945848385845868546854
so need that sort of integer datatype.... i know ive to build this
my self. ya one option can be linked list of long integers. thanx
for replyin...

You should be aware that, unless you find a clever shortcut that
avoids doing all the multiplcations, computing the factorial of
999448849493945848385845868546854 on any current system will take
longer than the expected lifetime of the universe. Storing the
result would also be an interesting challenge.

Yes, but as the OP said in the paragraph you quoted:
"the ans(wer) may be anything like 999448849493945848385845868546854"
I believe he's talking about the *result* of the factorial,
so this should be quite reasonable to handle.
(this said, obviousy the provided number cannot be the actual value
of an integer factorial function -- there would be trailing zeroes...)

I agree, and that is why I supplied some code that will give both
exact and approximate values in the indicated range. In particular
it is easy to tell how many trailing zeroes are actually present.
 
K

Keith Thompson

Ivan Vecerina said:
Yes, but as the OP said in the paragraph you quoted:
"the ans(wer) may be anything like 999448849493945848385845868546854"
I believe he's talking about the *result* of the factorial,
so this should be quite reasonable to handle.
(this said, obviousy the provided number cannot be the actual value
of an integer factorial function -- there would be trailing zeroes...)

I believe you're right (on both counts); my mistake. (The given value
is between 30! and 31!.) (That's factorial; I'm not shouting!)
 
M

Mike Wahler

Keith Thompson said:
I believe you're right (on both counts); my mistake. (The given value
is between 30! and 31!.) (That's factorial; I'm not shouting!)

I saw this somewhere a while back:

Factorials are exciting!

:)

-Mike
 
M

Merrill & Michele

If you have a tenuous grasp on the English language, I suggest using the
Queen's English, where possible.

Nice link.
CBFalconer" <[email protected]>
You can try the following. If the exact value of approximately
9332621544394410219000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
000000.0
isn't big enough you can extend the primes table used.

I'm unacquainted with a combinatorialist who would rather see a
computer-busting integer rather than fact(some n greater than 7 or so) as an
answer, cf. Stanley, Richard on differing standards between combo and the
rest of math. What a person needs to ask himself is to what end am I
computing this huge number? I think the answer to this question determines
what representation is the most useful. The algorithm below is a great
start if what you are eventually going to do is divide this ungodly-large
number by another, which is usually the case. MPJ
/* compute factorials, extended range
on a 32 bit machine this can reach fact(15) without
unusual output formats. With the prime table shown
overflow occurs at 101.

Public domain, by C.B. Falconer. 2003-06-22
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* 2 and 5 are handled separately
Placing 2 at the end attempts to preserve such factors
for use with the 5 factor and exponential notation
*/
static unsigned char primes[] = {3,7,11,13,17,19,23,29,31,37,
41,43,47,53,57,59,61,67,71,
/* add further primes here -->*/
2,5,0};
static unsigned int primect[sizeof primes]; /* = {0} */

static double fltfact = 1.0;

static
unsigned long int fact(unsigned int n, unsigned int *zeroes)
{
unsigned long val;
unsigned int i, j, k;

#define OFLOW ((ULONG_MAX / j) < val)

/* This is a crude mechanism for passing back values */
for (i = 0; i < sizeof primes; i++) primect = 0;

for (i = 1, val = 1UL, *zeroes = 0; i <= n; i++) {
fltfact *= i; /* approximation */
j = i;
/* extract exponent of 10 */
while ((0 == (j % 5)) && (!(val & 1))) {
j /= 5; val /= 2;
(*zeroes)++;
}
/* Now try to avoid any overflows */
k = 0;
while (primes[k] && OFLOW) {
/* remove factors primes[k] */
while (0 == (val % primes[k]) && OFLOW) {
val /= primes[k];
++primect[k];
}
while (0 == (j % primes[k]) && OFLOW) {
j /= primes[k];
++primect[k];
}
k++;
}

/* Did we succeed in the avoidance */
if (OFLOW) {
#if DEBUG
fprintf(stderr, "Overflow at %u, %lue%u * %u\n",
i, val, *zeroes, j);
#endif
val = 0;
break;
}
val *= j;
}
return val;
} /* fact */

int main(int argc, char *argv[])
{
unsigned int x, zeroes;
unsigned long f;

if ((2 == argc) && (1 == sscanf(argv[1], "%u", &x))) {
if (!(f = fact(x, &zeroes))) {
fputs("Overflow\n", stderr);
return EXIT_FAILURE;
}

printf("Factorial(%u) == %lu", x, f);
if (zeroes) printf("e%u", zeroes);
for (x = 0; primes[x]; x++) {
if (primect[x]) {
printf(" * pow(%d,%d)", primes[x], primect[x]);
}
}
putchar('\n');
printf("or approximately %.0f.\n", fltfact);
return 0;
}
fputs("Usage: fact n\n", stderr);
return EXIT_FAILURE;
} /* main */
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,834
Latest member
BuyCannaLabsCBD

Latest Threads

Top