Long(er) Factorial

A

aNt17017

This is my code:

long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}

But it works only for small numbers (up to 15 or so). Can someone tell
me what to change/add, so I can calculate larger factorials?

Thank You,

Kris
 
R

Roberto Waltman

aNt17017 said:
long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}

But it works only for small numbers (up to 15 or so). Can someone tell
me what to change/add, so I can calculate larger factorials?

a) Changing the function type from long to unsigned long will give you
one more usable bit, it may be just enough to obtain one more value
from your function.

b) Check your system (compiler docs, header file "stdint.h", etc.) to
see if you have a built-in type offering a greater range than "long"
("long long" may be available)

c) Use a library like GMP (http://www.swox.com/gmp/) instead of the C
built-in data types and operators.
 
Q

questions?

aNt17017 said:
This is my code:

long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}

But it works only for small numbers (up to 15 or so). Can someone tell
me what to change/add, so I can calculate larger factorials?

Thank You,

Kris

take log of the numbers, say you want a.b.c,instead of multiply, just
do log(a)+log(b)+log(c)
this==log(abc), you can hold big numbers in log scale.
 
W

Walter Roberson

This is my code:
long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}
But it works only for small numbers (up to 15 or so). Can someone tell
me what to change/add, so I can calculate larger factorials?

How many bits are in a 'long' in your implementation?

12 factorial is the largest that will fit in a signed 32 bit long.
13! -- needs 34 bits of signed (2's complement) long
14! -- 38 bits
15! -- 42 bits
16! -- 46 bits

19! -- 58 bits
20! -- 63 bits
21! -- 67 bits

100! -- requires at least a 526 bit signed 2's complement long
(158 decimal digits)

If you want to be able to calculate such large numbers, you will
have to write (or find) an extended precision library.
 
J

John Devereux

How many bits are in a 'long' in your implementation?
100! -- requires at least a 526 bit signed 2's complement long
(158 decimal digits)

If you want to be able to calculate such large numbers, you will
have to write (or find) an extended precision library.

Or he could perhaps change the data types to double.
 
A

aNt17017

in my my implementation 'long' = 32 bits
I tried to use 'long long' or 'double' types and it doesn't work.
 
K

Kenneth Brody

John said:
This is my code:
long fact(int n)
[...]
But it works only for small numbers (up to 15 or so). Can someone tell
me what to change/add, so I can calculate larger factorials?

How many bits are in a 'long' in your implementation?
100! -- requires at least a 526 bit signed 2's complement long
(158 decimal digits)

If you want to be able to calculate such large numbers, you will
have to write (or find) an extended precision library.

Or he could perhaps change the data types to double.

But only if an approximation of the factorial is permissible.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>
 
A

aNt17017

This is my complete setup:
1 - get data from user
2 - calculate factorial

and it's still doesn't work as I wish. I don't wont to use other
libraries 'cause it should base on "simple" recursive formula.


void factorial(void)
{
clearScreen();
printf("\n\t\tCalculate the Factorial of entered numbers.\n");
printf("\t\t===========================================\n");

int num;
printf("\t\tPlease enter a value in the range of 0 to 100(q to
quit): ");
while (scanf("%d",&num) == 1)
{
if(num <= 0)
printf("\t\tPlease enter a value greater than 0.\n");
else if (num > 100)
printf("\t\tPlease keep the value under 100.\n");
else
{
printf("\t\t%d factorial = %ld\n",num, fact(num));
}
printf("\t\tPlease enter a value in the range of 0 to 100(q to
quit): ");
}
pressEnter();
}


long long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}
 
S

SM Ryan

# But it works only for small numbers (up to 15 or so). Can someone tell
# me what to change/add, so I can calculate larger factorials?

Factorial is a restriction of the gamma function to integers.
n! = either gamma(n+1) or gamma(n-1), don't remember which offhand.
The gamma function should be in the math library; it will efficiently
and accurately compute factorials of doubles outside the range of
long long long long ints.
 
K

Keith Thompson

aNt17017 said:
in my my implementation 'long' = 32 bits
I tried to use 'long long' or 'double' types and it doesn't work.

You need to provide some context when you post a followup.
Read <http://cfaj.freeshell.org/google/>.

Saying "it doesn't work" really doesn't tell us anything useful. What
exactly did you try, and what happened?

Note that using double will give you imprecise results; double can
represent very large numbers, but it pays for that by not being able
to distinguish between very large numbers that differ by a small
amount.
 
K

Keith Thompson

aNt17017 said:
This is my complete setup:
1 - get data from user
2 - calculate factorial

and it's still doesn't work as I wish. I don't wont to use other
libraries 'cause it should base on "simple" recursive formula.


void factorial(void)
{
clearScreen();
printf("\n\t\tCalculate the Factorial of entered numbers.\n");
printf("\t\t===========================================\n");

int num;
printf("\t\tPlease enter a value in the range of 0 to 100(q to
quit): ");
while (scanf("%d",&num) == 1)
{
if(num <= 0)
printf("\t\tPlease enter a value greater than 0.\n");
else if (num > 100)
printf("\t\tPlease keep the value under 100.\n");
else
{
printf("\t\t%d factorial = %ld\n",num, fact(num));
}
printf("\t\tPlease enter a value in the range of 0 to 100(q to
quit): ");
}
pressEnter();
}


long long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}

Again, read <http://cfaj.freeshell.org/google/>.

This is not a complete program. You don't have a main() function, and
you don't have the "#include <stdio.h>" that's required for printf and
scanf.

You say it doesn't work as you wish. What does it do? Or are we
supposed to guess?

What are clearScreen() and pressEnter()? It's obvious from their
names what they're supposed to do, but why on Earth do you want to
clear the screen before asking for input? If I'm running your
program, I might have important information on my screen.

In factorial(), you declare "int num;" after several call statements.
In C90, all declarations must precede all statements in a block. (C99
allows them to be mixed, as does C++, and some compilers allow it as
an extension, but there's no real benefit in using the feature here.)

You call fact() from factorial(). At the point of the call, the
declaration of the fact() function hasn't been seen yet. In C90, this
causes the compiler to assume that fact() returns an int; since it
actually returns long long, the result is undefined behavior. If
you're lucky, the program will crash; if you're unlucky, you may get
seemingly valid output in some cases. The simplest way to fix this is
to move the definition of fact() above the definition of factorial().
You can also provide separate declarations at the top of the program,
and give the definitions in any order you like (make sure the
declarations match the definitions).

fact() returns long long int (using unsigned long long int would give
you one additional bit), but you print its result using printf's "%ld"
format, which expects a long int. The format for printing a long long
int is "%lld" (or "%llu" for unsigned long long).

If you fix these problems, your program should be able to handle
values up to fact(20), or 2432902008176640000, which fits in 62 bits.
fact(21), or 51090942171709440000, requires 66 bits.

Some interesting numbers:

2432902008176640000 fact(20)
9223372036854775807 2**63-1
18446744073709551615 2**64-1
51090942171709440000 fact(21)

2**63-1 is likely to be the maximum value of a long long; 2**64-1 is
likely to be the maximum value of an unsigned long long.
 
C

CBFalconer

aNt17017 said:
This is my code:

long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}

But it works only for small numbers (up to 15 or so). Can someone
tell me what to change/add, so I can calculate larger factorials?

Here is one way:

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

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
J

jacob navia

aNt17017 a écrit :
This is my code:

long fact(int n)
{
if (n == 0)
return(1);
if(n > 100)
{
printf("\t\tERROR: %d is too large for factorial.\n", n);
return 1;
}
return(n * fact(n-1));
}

But it works only for small numbers (up to 15 or so). Can someone tell
me what to change/add, so I can calculate larger factorials?

Thank You,

Kris

You can use the lcc-win32 compiler:
#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);
}

Output:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

lcc-win32:
http://www.cs.virginia.edu/~lcc-win32
 
K

Keith Thompson

jacob navia said:
aNt17017 a écrit :

You can use the lcc-win32 compiler:
[snip]

Only if he happens to be using a win32 system, and only if he doesn't
mind his code being portable only to win32 systems.

This is, of course, off-topic.
 
A

Andrew Poelstra

questions? said:
take log of the numbers, say you want a.b.c,instead of multiply, just
do log(a)+log(b)+log(c)
this==log(abc), you can hold big numbers in log scale.

True, but you need to use a double and hope that you aren't losing
precision; holding logs requires enough space to hold all the decimal
places.
So, 8 can fit into a signed char, which is 7 usable bits, but log(8) is
0.903089987 and will require a float or a double (the latter of which is
80 bits on some systems!).
 
K

Kelsey Bjarnason

[snips]

What are clearScreen() and pressEnter()? It's obvious from their
names what they're supposed to do, but why on Earth do you want to
clear the screen before asking for input? If I'm running your
program, I might have important information on my screen.

God, I hate that asinine argument. If your information is so damned
important, then a) why are you storing it on a screen, instead of backed
up to a DVD, tape, or even simply a disk file, and b) why are you running
such wildly unknown and unpredictable applications *right in the middle of
your critical data*?

I very rarely have problems with my backups containing the correct data...
because I very rarely dump the results of /dev/random into the files I
create as part of the backup. See, that data is important, so I simply do
not treat it as a scratch pad. End of problem.

If the data's important, but the user treats the data store like a scratch
pad, blame the user, not the applications, when the data goes away.

Run it on a different machine. In a different terminal. Whatever turns
your crank. Running it in the same place your "important information"
resides, when you don't know the results of running it, is just stupid.
 
K

Keith Thompson

Kelsey Bjarnason said:
[snips]
What are clearScreen() and pressEnter()? It's obvious from their
names what they're supposed to do, but why on Earth do you want to
clear the screen before asking for input? If I'm running your
program, I might have important information on my screen.

God, I hate that asinine argument. If your information is so damned
important, then a) why are you storing it on a screen, instead of backed
up to a DVD, tape, or even simply a disk file, and b) why are you running
such wildly unknown and unpredictable applications *right in the middle of
your critical data*?
[...]

I think we're both guilty of overstatement.

Ok, so my screen is a scratchpad, and I shouldn't depend on any
information on it sticking around for long. But it's *my* scratchpad,
and if a program clears it for no good reason, I'm not going to be
pleased.

If your program needs to take control of the entire screen (say, it's
a text editor), on many systems it can use a system-specific library
that allows it to save and restore the current screen contents.

What's on my screen is probably the output of the last program (or
programs) I ran. Your own program's output isn't so important that
you need to erase *my* (possibly unimportant) data.

Unless you can think of a good reason why any program should need to
clear the screen before printing "Please enter a number"?
 
R

Richard Bos

Kelsey Bjarnason said:
God, I hate that asinine argument. If your information is so damned
important, then a) why are you storing it on a screen, instead of backed
up to a DVD, tape, or even simply a disk file,

Who's talking about storing? Suppose I've just run a command - it need
be no more complicated than ls - and now I want to enter some
information from the result of that command into the next program. Very
useful, at times. If that next command just clobbered over my directory
listing for no good reason, all filenames that I wanted to enter are now
gone.

Richard
 
K

Kelsey Bjarnason

Who's talking about storing?

He is. That's where his important data is. where he stored it. If he
doesn't want it messed with, he has two choices: store it somewhere else,
or don't run unpredictable things in the same place it's being stored.

There are _no_ other options if the data is important.
Suppose I've just run a command - it need
be no more complicated than ls - and now I want to enter some
information from the result of that command into the next program. Very
useful, at times. If that next command just clobbered over my directory
listing for no good reason, all filenames that I wanted to enter are now
gone.

So you just ran a program with unpredictable outputs all over your data
store, and you're complaining that your data store is gone. Do you
regularly dump /dev/random ovetop of your backups? No? Why not? Could it
have something to do with it being a *stupid* idea to dump unpredictable
data overtop of data you want to keep?

Of course you'd never do that. It would be stupid. But somehow it's
magically not stupid when the data's on the screen.

Nope, sorry, it's stupid in both cases. If the data's important, you do
*not* run apps with unpredictable outputs in the middle of your store.
 

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

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top