calculate value of 73!

[Tom St Denis]

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

 

[Richard Heathfield]

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 ! ==
4470115461512684340891257138125051110076800700282905015819080092370422104067
183317016903680000000000000000

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

What are you running it on, a 286?

 

[Tom St Denis]

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

4470115461512684340891257138125051110076800700282905015819080092370422104067

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 ! ==
4470115461512684340891257138125051110076800700282905015819080092370422104067
183317016903680000000000000000

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

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

Tom

 

[Tom St Denis]

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

 

[Nick Landsberg]

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.

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.

 

[Mark McIntyre]

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]

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.

 

[Nudge]

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

I wonder whether you will ever grow up.

 

[Tom St Denis]

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

 

[Richard Heathfield]

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.

 

[Tom St Denis]

/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.2/../../../../i686-pc-linux-gnu/bin/l

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.

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

 

[Richard Heathfield]

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.

 

[Tom St Denis]

That it's not an ISO C header.


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

 

[jacob navia]

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

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

???

Nothing invades the user names space unless he/she wants it so.
jacob

 

[Sidney Cadot]

jacob navia wrote:

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

???

Nothing invades the user names space unless he/she wants it so.
jacob

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

Best regards, Sidney

 

[Mark Shelor]

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 = (p = mp * 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)
break;
for (; i >= 0; i--)
printf("%d%s", mp, i ? "" : "\n");
return(0);
}

Output:

4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000

 

[Arthur J. O'Dwyer]

jacob navia wrote:

[re someone's saying his implementation encroached user namespaces]

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

 

[Peter Nilsson]

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

 

[Richard Heathfield]

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

 

[Sidney Cadot]

jacob navia wrote:

[re someone's saying his implementation encroached user namespaces]

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