S
Saurabh Saxena
can we calculate the 73! value in c or c++ without loss of significant digits.
J
Joona I Palaste
Saurabh Saxena said:
Yes. I've done it myself.
S
Sidney Cadot
Saurabh said:
Yes. Here you go:
/* homework.c */
#include <stdio.h>
#include <string.h>
char f[] = "44701154615126843408912571381250511100768007002829050"
"15819080092370422104067183317016903680000000000000001";
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
O
osmium
digits.Saurabh said:
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.
C
CBFalconer
Saurabh said:
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,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
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++) {
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');
return 0;
}
fputs("Usage: fact n\n", stderr);
return EXIT_FAILURE;
} /* main */
P
Peter Pichler
osmium said:
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 ;-)
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
O
osmium
Peter said:
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.
P
Peter Pichler
osmium said:
It actually says "without loss of significant digits", but yes, you are
right. I missed that. Doh!
In that case, the answer is "yes or no"
Peter
M
Martin Ambuhl
Saurabh said:
73! is about the 351st power of 2. There is no type in C or C++ that is
guaranteed 351 bits of precision.
R
Richard Heathfield
Martin said:
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:
4470115461512684340891257138125051110076\
8007002829050158190800923704221040671833\
17016903680000000000000000
It actually takes 107 octets, which is 856 bits, to store (in base 256).
J
jacob navia
Using lcc-win32 we have:
#include <stdio.h>
#include <qfloat.h>
int main(int argc,char *argv[])
{
int n;
int i = n = atoi(argv[1]);
qfloat q = 1;
while (i) {
q = q*i;
i--;
}
printf("%d! = %75.75qf\n",n,q);
// To verify the number above we divide it by
// the factorial of one less than that number
// (n!) / (n-1)! == n
qfloat m = 1;
i = n - 1;
while (i) {
m = m*i;
i--;
}
printf("%d! / %d! = %qg\n",n,n-1,q/m);
return 0;
}
Output
D:\lcc\mc50\test>f 75
75! = 2.480914081139539809194647711659403366
092624388657012283779589451265584267757e+109
75! / 74! = 75
D:\lcc\mc50\test>
#include <stdio.h>
#include <qfloat.h>
int main(int argc,char *argv[])
{
int n;
int i = n = atoi(argv[1]);
qfloat q = 1;
while (i) {
q = q*i;
i--;
}
printf("%d! = %75.75qf\n",n,q);
// To verify the number above we divide it by
// the factorial of one less than that number
// (n!) / (n-1)! == n
qfloat m = 1;
i = n - 1;
while (i) {
m = m*i;
i--;
}
printf("%d! / %d! = %qg\n",n,n-1,q/m);
return 0;
}
Output
D:\lcc\mc50\test>f 75
75! = 2.480914081139539809194647711659403366
092624388657012283779589451265584267757e+109
75! / 74! = 75
D:\lcc\mc50\test>
M
Martin Ambuhl
jacob said:
The original poster asked about C or C++, not lcc extensions which invade
the programmer's namespace.
C
CBFalconer
jacob said:
73! has precisely 16 trailing zeroes, in decimal notation. So the
above cannot be correct. (The original required no loss of
significant digits)
I believe C99 has some long double types that could be mapped into
your qfloat system, which would give you something very close to
standardization.
N
Nick Landsberg
CBFalconer said:
I believe that the original question was: "Can 73! be computed
using C without loss of significant digits?"
If you only use the standard types for any current implementation,
the answer is patently NO.
If on the other hand, you are creative and devise some kind
of algorithm where you have multiple "words" (32 bit or 64 bit)
representing the number, then the answer is YES.
For example -
One can define a vector of 32-bit integers where the low-order
24 bits are the data and the remaining 8 bits are for overflow.
Multiplying the first element by any number, one may get an overflow
(carry) in the high-order bits.
This carry is then added to the second element of the vector,
cleared, and the process repeated until the vector
is exhausted. One may add to the vector via malloc(), as needed
when there is a need carry overflow and there is no succeeding element.
Easy? No. Doable? Yes!
Displaying the results is yet another knotty problem, but that
was not what the original question asked.
R
Richard Heathfield
Nick Landsberg wrote:
Yes, it was.
I've done it using only standard types (and structs using only standard
types), so I'm not sure how you deduce that it can't be done.
Yes, it was.
I've done it using only standard types (and structs using only standard
types), so I'm not sure how you deduce that it can't be done.
M
Mark Shelor
Saurabh said:
Saurabh,
As you perhaps already know, the value of 73! is
44701154615126843408912571381250511100768007002829050158190800923704\
22104067183317016903680000000000000000
This is a value whose precision (number of digits in its representation)
exceeds that of all integral and floating types defined by (drum roll
please) ... THE STANDARD. In other words, to compute 73! using Standard
C, you'll need to develop a multiple-precision data structure and
associated computation procedure. There are myriad ways to do this;
Knuth Vol. 2 is a useful reference.
However, since the term "multiple-precision" is probably nowhere
mentioned in (drum roll please) THE STANDARD, you may want to be careful
about mentioning it any further, lest one of the newsgroup nannies, in
their never-ending quest for absolute purity, raps you on the knuckles
with a hard ruler.
Regards, Mark
R
Richard Heathfield
Mark said:
Right. (Well, it looks right at first glance; I haven't checked every
digit.)
Not so. The Standard imposes no maxima on precision levels - only minima.
Excellent advice.
This is unlikely. It is, however, true that the writing of "multiple
precision" libraries is less to do with C and more to do with programming.
Having said that, if someone were to run into a C problem whilst
programming a multiple precision library, I see no reason why they
shouldn't seek help for their C question here.
M
Mark Shelor
Richard said:
Though your statement about imposing no maxima is technically correct,
it's not precisely relevant to the problem at hand. The task is to find
a method for computing 73! that works on all implementations abiding by
the standard: in which case the minima are relevant, not the maxima.
Otherwise, one could glibly prescribe that the original poster either
find or create a C implementation that uses, say, 512-bit integers, and
then compute the factorial by normal means. However, that's neither
realistic nor helpful.
It's implied that my above statement should be read as: "This is a value
whose precision (number of digits in its representation) exceeds that of
all *guaranteed* integral and floating types defined by the standard."
This is the only interpretation that makes sense with regard to assuring
portability.
Regards, Mark
C
CBFalconer
Nick said:
If you look around in this thread you will find my earlier answer
with a purely standard C method, which involved no types larger
than an unsigned long.
R
Richard Heathfield
Mark said:
True enough, but neither is the remark about precision in the first place!
Whilst it's very true that anyone wishing to know the value of 73! by
writing a C program is not going to get very far using unsigned long, it's
also true that they'd be very naive to try. Some kind of array storage is,
I think, inevitable. Once the OP realises this, they will soon be
cheerfully writing their own bignum library.
All that is required is a few hundred unsigned chars. We are guaranteed that
CHAR_BIT is at least 8, which is plenty, and we know we can get hold of a
good 32767 bytes' worth of RAM, which is also vastly more than required by
the problem at hand. I think it's very obvious that there are no resource
or size issues here.
<snip>