469,568 Members | 1,482 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,568 developers. It's quick & easy.

calculate value of 73!

can we calculate the 73! value in c or c++ without loss of significant digits.
Nov 14 '05 #1
41 2710
Saurabh Saxena <sa******@vit.ac.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.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
Nov 14 '05 #2
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[] = "4470115461512684340891257138125051110076800700282 9050"
"1581908009237042210406718331701690368000000000000 0001";

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

Nov 14 '05 #3
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.
Nov 14 '05 #4
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,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[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("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 */

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #5
"osmium" <r1********@comcast.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
Nov 14 '05 #6
Peter Pichler writes:
"osmium" <r1********@comcast.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.
Nov 14 '05 #7
"osmium" <r1********@comcast.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
Nov 14 '05 #8
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
Nov 14 '05 #9
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:

4470115461512684340891257138125051110076\
8007002829050158190800923704221040671833\
17016903680000000000000000

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

--
Richard Heathfield : bi****@eton.powernet.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
Nov 14 '05 #10
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>
Nov 14 '05 #11
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
Nov 14 '05 #12
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\test>f 75
75! = 2.480914081139539809194647711659403366
092624388657012283779589451265584267757e+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********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #13


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\test>f 75
75! = 2.480914081139539809194647711659403366
092624388657012283779589451265584267757e+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

Nov 14 '05 #14
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.powernet.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
Nov 14 '05 #15
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

44701154615126843408912571381250511100768007002829 050158190800923704\
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

Nov 14 '05 #16
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

44701154615126843408912571381250511100768007002829 050158190800923704\
22104067183317016903680000000000000000


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.powernet.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
Nov 14 '05 #17
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

Nov 14 '05 #18
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********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #19
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.powernet.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
Nov 14 '05 #20

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@hercules.btinternet.com...
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.


It is quite possible todo in ISO C.... ;-)

#include <tommath.h>
int main(int argc, char **argv)
{
mp_int a;
char buf[1000];
int x;

if (argc != 2 || sscanf(argv[1], "%d", &x) != 1) {
printf("Syntax: f num\n");
return EXIT_FAILURE;
}

mp_init(&a);
mp_set(&a, 1);

do {
mp_mul_d(&a, x, &a);
} while (--x > 0);

mp_toradix(&a, buf, 10);
printf("%s ! == %s\n", argv[1], buf);

mp_clear(&a);
return EXIT_SUCCESS;
}
[I should have error checking... but you get the point right ?]

This produced

tom@tomlaptop ~
$ time ./f 73
73 ! ==
44701154615126843408912571381250511100768007002829 05015819080092370422104067
183317016903680000000000000000

real 0m0.084s
user 0m0.040s
sys 0m0.040s

[most of that time was spent in cygwin startup and the mp_toradix conversion
because "f 4" and "f 350" produce basically the same numbers...]

There, that's how you do 73! in portable C.

Tom
Nov 14 '05 #21
Tom St Denis wrote:

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@hercules.btinternet.com...
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.


It is quite possible todo in ISO C.... ;-)


I know, but...
#include <tommath.h>
int main(int argc, char **argv)
{
mp_int a;
char buf[1000];
int x;

if (argc != 2 || sscanf(argv[1], "%d", &x) != 1) {
printf("Syntax: f num\n");
return EXIT_FAILURE;
}

mp_init(&a);
mp_set(&a, 1);

do {
mp_mul_d(&a, x, &a);
} while (--x > 0);

mp_toradix(&a, buf, 10);
printf("%s ! == %s\n", argv[1], buf);

mp_clear(&a);
return EXIT_SUCCESS;
}
gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm -lrjh -lncurses -lwnn
foo.c:1: tommath.h: No such file or directory
[I should have error checking... but you get the point right ?]
Yes, the point you are making has already been made.
This produced

tom@tomlaptop ~
$ time ./f 73
73 ! ==
44701154615126843408912571381250511100768007002829 05015819080092370422104067 183317016903680000000000000000

real 0m0.084s
user 0m0.040s
sys 0m0.040s


What are you running it on, a 286?

--
Richard Heathfield : bi****@eton.powernet.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
Nov 14 '05 #22

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@sparta.btinternet.com...
Tom St Denis wrote:

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@hercules.btinternet.com...
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.


It is quite possible todo in ISO C.... ;-)


I know, but...
#include <tommath.h>
int main(int argc, char **argv)
{
mp_int a;
char buf[1000];
int x;

if (argc != 2 || sscanf(argv[1], "%d", &x) != 1) {
printf("Syntax: f num\n");
return EXIT_FAILURE;
}

mp_init(&a);
mp_set(&a, 1);

do {
mp_mul_d(&a, x, &a);
} while (--x > 0);

mp_toradix(&a, buf, 10);
printf("%s ! == %s\n", argv[1], buf);

mp_clear(&a);
return EXIT_SUCCESS;
}


gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm -lrjh -lncurses -lwnn
foo.c:1: tommath.h: No such file or directory


So download a copy or if you are in gentoo emerge one ;-)

LibTomMath itself is ISO C compliant. So it's just a matter of having a
copy handy [like the copy of glibc you're so fond of]

Also "-ansi" ... weak... "--std=c99" baby, all the way!
[I should have error checking... but you get the point right ?]


Yes, the point you are making has already been made.
This produced

tom@tomlaptop ~
$ time ./f 73
73 ! ==

44701154615126843408912571381250511100768007002829 05015819080092370422104067
183317016903680000000000000000

real 0m0.084s
user 0m0.040s
sys 0m0.040s


What are you running it on, a 286?


Um, to be honest I think the bulk of the 0.040s is in the mp_toradix step.
Let's confirm it. Sans the mp_toradix and printf... whoa it takes 0.010s
longer. Conclusion: cygwin's "time" is based off the Windows timer and is
a P.O.S.

Sans "output" on my Athlon Barton Gentoo box...

tombox tom # time ./f 73
real 0m0.001s
user 0m0.000s
sys 0m0.000s

With the output
tombox tom # time ./f 73
73 ! ==
44701154615126843408912571381250511100768007002829 05015819080092370422104067
183317016903680000000000000000

real 0m0.001s
user 0m0.000s
sys 0m0.000s

Conclusion. You're trying to be "smart" and have failed at it.

Tom
Nov 14 '05 #23

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@sparta.btinternet.com...
gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm -lrjh -lncurses -lwnn
foo.c:1: tommath.h: No such file or directory


While I'm at it...

tombox tom # gcc -O3 f.c -ltommath -lrjn -lwnn -o f
/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/../../../../i686-pc-linux-gnu/bin/l
d: cannot find -lrjn
collect2: ld returned 1 exit status

So what's your point about complaining about tommath.h?

Tom
Nov 14 '05 #24


Richard Heathfield wrote:
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.



My apologies - I was away on a business trip for about a week
and was too lazy to read the whole thread and only read the
OP and the last few posts. A faux-pas which I will not
make again. Also apologies to CBFalconer who pointed
out my mistake to me.

--

"It is impossible to make anything foolproof because fools are so
ingenious" - A. Bloch

Nov 14 '05 #25
On Sun, 08 Feb 2004 01:57:44 -0700, in comp.lang.c , Mark Shelor
<ms*****@comcast.removeme.net> 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.
This is true, despite your hyperbolic attempt to trivialise 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.
Good 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.


Bogus reasoning, to be expected from someone who otherthread is being
rapped for asking OT questions and persisting in it.

What /is/ true is that determining the necessary algo to do this sum
is offtopic here. comp.programming would be a better place. Having
said that, for trivial questions like this, where the algo is
generally well understood, a lucky poster might get handed a
read-written C implementation

In either case, having determined the algo, to ask for implementation
tips here is not offtopic. This is unlike (say) interfacing to a
database or user interface, which generally just cannot be done in
standard C.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 14 '05 #26
On Sun, 08 Feb 2004 02:38:37 -0700, in comp.lang.c , Mark Shelor
<ms*****@comcast.removeme.net> 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. 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.


This is true, and salient. The only way to do this portably is to work
with the minima that are guaranteed, and therefore to devise an algo
that works for those minima.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 14 '05 #27
Tom St Denis wrote:
Conclusion. You're trying to be "smart" and have failed at it.


I wonder whether you will ever grow up.

Nov 14 '05 #28

"Nudge" <de*****@kma.eu.org> wrote in message
news:40***********************@news.free.fr...
Tom St Denis wrote:
Conclusion. You're trying to be "smart" and have failed at it.


I wonder whether you will ever grow up.


How so? Richard was trying to be smart with his reply by using hyperbole.
I politely showed that the same code on my Linux box gave the expected
timing counts.

Tom
Nov 14 '05 #29
Tom St Denis wrote:

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@sparta.btinternet.com...
gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm -lrjh -lncurses -lwnn
foo.c:1: tommath.h: No such file or directory

While I'm at it...

tombox tom # gcc -O3 f.c -ltommath -lrjn -lwnn -o f

/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/../../../../i686-pc-linux-gnu/bin/l d: cannot find -lrjn
You meant rjh, not rjn

Yes, it is quite true that my rjh library, librjh.a, is not publicly
available (although the other one, libwnn.a, *is*), and it is also quite
true that I should have edited the -l switches out of my gcc line before
posting it. Usually I remember; on this occasion I forgot. Relevance to
this thread: none whatsoever.

collect2: ld returned 1 exit status

So what's your point about complaining about tommath.h?


It's not an ISO C header. Therefore, we can't assume that everyone has it
installed on their system. It's precisely the same reasoning as that which
led to your perfectly correct objection to librjh.a, you see.
--
Richard Heathfield : bi****@eton.powernet.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
Nov 14 '05 #30

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@sparta.btinternet.com...
Tom St Denis wrote:

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@sparta.btinternet.com...
gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm -lrjh -lncurses -lwnn
foo.c:1: tommath.h: No such file or directory


While I'm at it...

tombox tom # gcc -O3 f.c -ltommath -lrjn -lwnn -o f

/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/../../../../i686-pc-linux-gnu/bin/l
d: cannot find -lrjn


You meant rjh, not rjn

Yes, it is quite true that my rjh library, librjh.a, is not publicly
available (although the other one, libwnn.a, *is*), and it is also quite
true that I should have edited the -l switches out of my gcc line before
posting it. Usually I remember; on this occasion I forgot. Relevance to
this thread: none whatsoever.


So what was your comment about tommath.h then? I never said it's part of
EVERY C COMPILER ON EARTH. I said it's an ISO C solution to the problem.

collect2: ld returned 1 exit status

So what's your point about complaining about tommath.h?


It's not an ISO C header. Therefore, we can't assume that everyone has it
installed on their system. It's precisely the same reasoning as that which
led to your perfectly correct objection to librjh.a, you see.


Everyone should have it though [<= this is sarcasm so please put the
flamethrowers away]. My point was it's a solution that's portable in that
you have to have libtommath installed.

Ok you caught me. I was plugging my library... ;-)

Tom
Nov 14 '05 #31
Tom St Denis wrote:
So what was your comment about tommath.h then?
That it's not an ISO C header.
I never said it's part of
EVERY C COMPILER ON EARTH.
Then it cannot sensibly be advanced as an ISO C solution to the stated
problem, unless all the relevant code is provided. You won't provide all
your relevant library code for calculating a large factorial for precisely
the same reason that I won't produce mine - i.e. it would take too long to
isolate the necessary code, and it would be too much the mark of a newbie
/not/ to isolate it and post the whole damn thing instead.
I said it's an ISO C solution to the problem.
Not unless the support libraries are actually around - which we can't
guarantee for anyone's third party code; not mine, and not yours, even
though your code and mine for doing this are both written in ISO C.
Ok you caught me. I was plugging my library... ;-)


Indeed.

--
Richard Heathfield : bi****@eton.powernet.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
Nov 14 '05 #32

"Richard Heathfield" <do******@address.co.uk.invalid> wrote in message
news:c0**********@sparta.btinternet.com...
Tom St Denis wrote:
So what was your comment about tommath.h then?


That it's not an ISO C header.
I never said it's part of
EVERY C COMPILER ON EARTH.


Then it cannot sensibly be advanced as an ISO C solution to the stated
problem, unless all the relevant code is provided. You won't provide all
your relevant library code for calculating a large factorial for precisely
the same reason that I won't produce mine - i.e. it would take too long to
isolate the necessary code, and it would be too much the mark of a newbie
/not/ to isolate it and post the whole damn thing instead.


I don't see this as being a valid argument. Just because the code isn't
part of the ISO C standard doesn't mean it doesn't follow the ISO C standard
and therefore is ISO C source code. Since my code solves the problem it's
an ISO C solution. Splitting fine hairs... ;-)

As for isolating the code that's not entirely hard. However, if a lesson is
to be had the OP could check out my 300 page text book on MP math ;-)
[included in the library package].

Tom
Nov 14 '05 #33

"Martin Ambuhl" <ma*****@earthlink.net> wrote in message
news:My******************@newsread1.news.atl.earth link.net...
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

Hi Martin
Did you overlooked
#include <qfloat.h>

???

Nothing invades the user names space unless he/she wants it so.
jacob
Nov 14 '05 #34
Saurabh Saxena wrote:
can we calculate the 73! value in c or c++ without loss of significant digits.

#include <stdio.h>

#define PRECISION 106

int mul(int *mp, int m)
{
int i, p, c;

for (i = 0, c = 0; i < PRECISION; i++) {
mp[i] = (p = mp[i] * m + c) % 10;
c = p / 10;
}
return(c);
}

int mp[PRECISION];

int main()
{
int i;

mp[0] = 1;
for (i = 2; i <= 73; i++)
if (mul(mp, i))
return(1);
for (i = PRECISION-1; i > 0; i--)
if (mp[i])
break;
for (; i >= 0; i--)
printf("%d%s", mp[i], i ? "" : "\n");
return(0);
}

Output:

44701154615126843408912571381250511100768007002829 05015819080092370422104067183317016903680000000000 000000

Nov 14 '05 #35

On Mon, 9 Feb 2004, Sidney Cadot wrote:

jacob navia wrote:

[re someone's saying his implementation encroached user namespaces]
Did you overlooked
#include <qfloat.h>
???
Nothing invades the user names space unless he/she wants it so.


Fair enough. However, your program invokes UB in both C and C++ by using
%qf in a printf formatting string, I believe.


Well, duh. His program invokes undefined behavior, or at least
implementation-specified behavior (I don't feel like checking), by
#including <qfloat.h> in the first place.
The program was *obviously* not trying to be a strictly conforming
C program [which BTW makes it off-topic here]; and AIUI, this subthread
was talking about implementation compliance, not program compliance,
anyway.
(A final note from Obvious-Man: one possible effect of undefined
behavior is the printing of the contents of an object as if it were
a 'qfloat' object. ;-)

-Arthur
Nov 14 '05 #36
"Mark Shelor" <ms*****@comcast.removeme.net> wrote in message
news:Oe********************@comcast.com...
Saurabh Saxena wrote:
can we calculate the 73! value in c or c++ without loss of significant
digits.


...
int main()
{
...
return(1);


1 is not a robust return value from main; 0, EXIT_SUCCESS or EXIT_FAILURE
are safe in terms of returning a reliable status to the host. [The latter
two macros being available from <stdlib.h>]

--
Peter
Nov 14 '05 #37
Peter Nilsson wrote:
"Mark Shelor" <ms*****@comcast.removeme.net> wrote in message
news:Oe********************@comcast.com...
Saurabh Saxena wrote:
> can we calculate the 73! value in c or c++ without loss of significant
> digits.


...
int main()
{
...
return(1);


1 is not a robust return value from main; 0, EXIT_SUCCESS or EXIT_FAILURE
are safe in terms of returning a reliable status to the host. [The latter
two macros being available from <stdlib.h>]


Isn't that just a touch on the churlish side, Pete (albeit correct!)?

For the record, I thought Mark's reply was superb.

--
Richard Heathfield : bi****@eton.powernet.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
Nov 14 '05 #38
Arthur J. O'Dwyer wrote:
On Mon, 9 Feb 2004, Sidney Cadot wrote:
jacob navia wrote:


[re someone's saying his implementation encroached user namespaces]
Did you overlooked
#include <qfloat.h>
???
Nothing invades the user names space unless he/she wants it so.


Fair enough. However, your program invokes UB in both C and C++ by using
%qf in a printf formatting string, I believe.

Well, duh. His program invokes undefined behavior, or at least
implementation-specified behavior (I don't feel like checking), by
#including <qfloat.h> in the first place.


You don't know that, since you haven't seen qfloat.h (it may be
perfectly compliant). All we know is that UB is introduced by the printf
format string.

Best regards,

Sidney

Nov 14 '05 #39

"Sidney Cadot" <si****@jigsaw.nl> wrote in message
news:c0**********@news.tudelft.nl...
Arthur J. O'Dwyer wrote:
On Mon, 9 Feb 2004, Sidney Cadot wrote:
jacob navia wrote:


[re someone's saying his implementation encroached user namespaces]
Did you overlooked
#include <qfloat.h>
???
Nothing invades the user names space unless he/she wants it so.

Fair enough. However, your program invokes UB in both C and C++ by using
%qf in a printf formatting string, I believe.

Well, duh. His program invokes undefined behavior, or at least
implementation-specified behavior (I don't feel like checking), by
#including <qfloat.h> in the first place.


You don't know that, since you haven't seen qfloat.h (it may be
perfectly compliant). All we know is that UB is introduced by the printf
format string.


First line of qfloat.h

#define printf qfloat_compatible_printf

;-)

Tom
Nov 14 '05 #40
Richard Heathfield wrote:
Isn't that just a touch on the churlish side, Pete (albeit correct!)?

For the record, I thought Mark's reply was superb.

A very kind remark, Richard. Thank you. I've also added a splendid
adjective to my vocabulary ;)

Truthfully, though, I was ignorant of EXIT_SUCCESS and EXIT_FAILURE, so
thanks also to Pete for pointing this out.

Regards, Mark

Nov 14 '05 #41
Sidney Cadot <si****@jigsaw.nl> wrote:
Arthur J. O'Dwyer wrote:
Well, duh. His program invokes undefined behavior, or at least
implementation-specified behavior (I don't feel like checking), by
#including <qfloat.h> in the first place.


You don't know that, since you haven't seen qfloat.h (it may be
perfectly compliant).


Imprimis, he didn't show us his qfloat.h, so the program _as posted_
invokes non-defined, IIRC undefined, behaviour.
Secundis, you can't definedly use <> with your own headers; only the
Standard headers are guaranteed to be useable that way. "qfloat.h" is
also not quite guaranteed to be found, but there are more requirements
for the search in that case.

Richard
Nov 14 '05 #42

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by Building Blocks | last post: by
6 posts views Thread by luanhoxung | last post: by
11 posts views Thread by Thomas | last post: by
6 posts views Thread by rrstudio2 | last post: by
reply views Thread by suresh191 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.