calculate value of 73!

[Saurabh Saxena]

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

[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\tes t>f 75
75! = 2.4809140811395 398091946477116 59403366
092624388657012 283779589451265 584267757e+109
75! / 74! = 75

D:\lcc\mc50\tes t>

[Martin Ambuhl]

jacob navia wrote:

Using lcc-win32 we have:
#include <stdio.h>
#include <qfloat.h>

The original poster asked about C or C++, not lcc extensions which invade
the programmer's namespace.

--
Martin Ambuhl

[CBFalconer]

jacob navia wrote:

Using lcc-win32 we have:
#include <stdio.h>
#include <qfloat.h>
int main(int argc,char *argv[])
{ .... snip ... }
Output
D:\lcc\mc50\tes t>f 75
75! = 2.4809140811395 398091946477116 59403366
092624388657012 283779589451265 584267757e+109
75! / 74! = 75

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 .

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

[Nick Landsberg]

CBFalconer wrote:

jacob navia wrote:

Using lcc-win32 we have:
#include <stdio.h>
#include <qfloat.h>
int main(int argc,char *argv[])
{

... snip ...

}
Output
D:\lcc\mc50\t est>f 75
75! = 2.4809140811395 398091946477116 59403366
092624388657012 283779589451265 584267757e+109
75! / 74! = 75

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 .

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. :)
--
Ñ
"It is impossible to make anything foolproof because fools are so
ingenious" - A. Bloch

[Richard Heathfield]

Nick Landsberg wrote:

<snip>

I believe that the original question was: "Can 73! be computed
using C without loss of significant digits?"
Yes, it was.

If you only use the standard types for any current implementation,
the answer is patently NO.

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

[Mark Shelor]

Saurabh Saxena wrote:

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

Saurabh,

As you perhaps already know, the value of 73! is

447011546151268 434089125713812 505111007680070 028290501581908 00923704\
221040671833170 169036800000000 00000000

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

[Richard Heathfield]

Mark Shelor wrote:

Saurabh Saxena wrote:

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

Saurabh,

As you perhaps already know, the value of 73! is

447011546151268 434089125713812 505111007680070 028290501581908 00923704\
221040671833170 169036800000000 00000000

Right. (Well, it looks right at first glance; I haven't checked every
digit.)
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.
Not so. The Standard imposes no maxima on precision levels - only minima.

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

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.

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.

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

[Mark Shelor]

Richard Heathfield wrote:

Mark Shelor wrote:

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.

Not so. The Standard imposes no maxima on precision levels - only minima.

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

[CBFalconer]

Nick Landsberg wrote:

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

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.

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

[Richard Heathfield]

Mark Shelor wrote:

Richard Heathfield wrote:

Mark Shelor wrote:

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.

Not so. The Standard imposes no maxima on precision levels - only minima.

Though your statement about imposing no maxima is technically correct,
it's not precisely relevant to the problem at hand.

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

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>

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