calculate value of 73!

[Saurabh Saxena]

can we calculate the 73! value in c or c++ without loss of significant digits.

[Joona I Palaste]

Saurabh Saxena <sa******@vit.a c.in> scribbled the following:

can we calculate the 73! value in c or c++ without loss of significant digits.

Yes. I've done it myself.

--
/-- Joona Palaste (pa*****@cc.hel sinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/

[Sidney Cadot]

Saurabh Saxena wrote:

can we calculate the 73! value in c or c++ without loss of significant digits.

Yes. Here you go:

/* homework.c */

#include <stdio.h>
#include <string.h>

char f[] = "44701154615126 843408912571381 250511100768007 002829050"
"15819080092370 422104067183317 016903680000000 000000001";

int main(void)
{
f[strlen(f)-1]--; /* calculate 73! from 73!+1*/
puts(f);
return 0;
}

In c++ it's even easier, since you can omit the void parameter to main.

Best regards,

Sidney

[osmium]

Saurabh Saxena writes:

can we calculate the 73! value in c or c++ without loss of significant

digits.

Oddly enough, the range of a pocket scientific calculator is greater than
that of C for long or even double precision numbers. And you will note that
the calculator will not compute 73!. It could be done but it would require
coding (or acquiring) a method of dealing with very large numbers. The
person who asked that rather poorly worded question probably expects the
answer to be "no", but I am not a mind reader.

In short, we *can* do almost any mathematical problem we can formulate in
our mind. Or anything that we can conjure up a way to represent by a
sequence of mathematical operations.

[CBFalconer]

Saurabh Saxena wrote:

can we calculate the 73! value in c or c++ without loss of
significant digits.

Yes.

c:\c\junk>fact 73
Factorial(73) == 2449473536e16 * pow(3,34) * pow(7,11) * pow(11,6)
* pow(13,5) * pow(17,4) * pow(19,3) * pow(23,3) * pow(29,2) *
pow(31,2) * pow(37,1) * pow(41,1) * pow(43,1) * pow(47,1) *
pow(53,1) * pow(59,1) * pow(61,1) * pow(67,1) * pow(71,1) *
pow(2,29)

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

#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,1 9,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
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[i] = 0;

for (i = 1, val = 1UL, *zeroes = 0; i <= n; i++) {
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("Factori al(%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');
return 0;
}
fputs("Usage: fact n\n", stderr);
return EXIT_FAILURE;
} /* main */

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Peter Pichler]

"osmium" <r1********@com cast.net> wrote:

Saurabh Saxena writes:

can we calculate the 73! value in c or c++ without loss of significant digits.

Oddly enough, the range of a pocket scientific calculator is greater than
that of C for long or even double precision numbers. And you will note

that the calculator will not compute 73!.
A good one*) will. Mine can do, though it takes a few seconds (1000! takes
almost an hour) and I cannot vouch for the precision.

*) Read: programmable ;-)
It could be done but it would require
coding (or acquiring) a method of dealing with very large numbers.

Not really, you just need to separate the mantissa from the exponent. I
don't remember how big the exponent was for 1000!, I only *think* it had to
be expressed in scientific notation on my calculator (too lazy to try it
again).

The method is simple: take advantage of the fact that a * b == pow(10,
log10(a) + log10(b)). I'll leave the rest on the OP - after all, I'm not
going to do his homework for him! ;-)

Peter

[osmium]

Peter Pichler writes:

"osmium" <r1********@com cast.net> wrote:

Saurabh Saxena writes:

can we calculate the 73! value in c or c++ without loss of

significant digits. Osmium writes:
It could be done but it would require
coding (or acquiring) a method of dealing with very large numbers.
Not really, you just need to separate the mantissa from the exponent. I
don't remember how big the exponent was for 1000!, I only *think* it had

to be expressed in scientific notation on my calculator (too lazy to try it
again).

The method is simple: take advantage of the fact that a * b == pow(10,
log10(a) + log10(b)). I'll leave the rest on the OP - after all, I'm not
going to do his homework for him! ;-)

The problem says "without loss of precision". You can not use logarithms
for generalized numbers without loss of precision. Note that I mentioned
the constraint on double only in passing, the real glitch is that the long
is not big enough.

I think the homework was only a yes or no answer to a poorly phrased
question, not an actual solution.

[Peter Pichler]

"osmium" <r1********@com cast.net> wrote:

The problem says "without loss of precision".
It actually says "without loss of significant digits", but yes, you are
right. I missed that. Doh!
I think the homework was only a yes or no answer to a poorly phrased
question, not an actual solution.

In that case, the answer is "yes or no" :-)

Peter

[Martin Ambuhl]

Saurabh Saxena wrote:

can we calculate the 73! value in c or c++ without loss of significant digits.

73! is about the 351st power of 2. There is no type in C or C++ that is
guaranteed 351 bits of precision.
--
Martin Ambuhl

[Richard Heathfield]

Martin Ambuhl wrote:

Saurabh Saxena wrote:

can we calculate the 73! value in c or c++ without loss of significant
digits.

73! is about the 351st power of 2. There is no type in C or C++ that is
guaranteed 351 bits of precision.

Nevertheless, it is certainly possible to calculate 73! in C. I have a
program written entirely in ISO C which can certainly do this. I won't post
it here, since the bignum library is 3500+ lines long (and yes, I know we
don't need *all* of it for this problem!), but it's straight ISO C. The
answer it provides is:

447011546151268 434089125713812 5051110076\
800700282905015 819080092370422 1040671833\
170169036800000 00000000000

It actually takes 107 octets, which is 856 bits, to store (in base 256).

--
Richard Heathfield : bi****@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton