99 ^ 99 in C

[Bartc]

Willem said:



Nice code, btw.

Oh, yes - so I set up my version for 1000 iterations, and removed the
print
to outside the loop, giving me 0.084 real, i.e. less than 100 microseconds
per power calc.

This sounds better than the 8ms/8000us you had earlier reported.

I tried to get some C code up to speed and managed around 60uS per
calculation (three times faster than Willem's). However this used fixed size
int arrays with decimal representation (4 digits per int) for ease of
display.

There is scope for improvement though when there is access to things such as
the 32-bit => 64-bit multiplies of a typical cpu.

 

[Willem]

Bartc wrote:
) This sounds better than the 8ms/8000us you had earlier reported.
)
) I tried to get some C code up to speed and managed around 60uS per
) calculation (three times faster than Willem's). However this used fixed size
) int arrays with decimal representation (4 digits per int) for ease of
) display.

Well that would make it about 4 times as fast, given that I used 1 digit
per int.

) There is scope for improvement though when there is access to things such as
) the 32-bit => 64-bit multiplies of a typical cpu.

There is a lot of scope for improvement if you use a halfway decent
algorithm to do the multiplication instead of the blindingly simple
obvious O(n^2) one... I think.
Perhaps for this size the speed of simpleness wins out, who knows.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Peter Nilsson]

Even if the answer has to be exact you can get it in 0
seconds.  There is no need to spend any time at all
calculating a know[n] constant.

True, but you must first know it!

I would point out that the 2 minutes it took me to type,
compile and run the least efficient code posted so far
could itself be replicated many many times over in the
time that some others have spent trying to shave
microseconds off a tediously dull calculation!

 

[Paul Hsieh]

I tried to get some C code up to speed and managed around 60uS per
calculation (three times faster than Willem's). However this used fixed
size int arrays with decimal representation (4 digits per int) for ease
of display.

Why don't you just use sizeof(unsigned long long)*CHAR_BIT bit digits,
and write a radix converter? I mean you guys are seriously timing
these things after making strange decisions like that?

There is scope for improvement though when there is access to things
such as the 32-bit => 64-bit multiplies of a typical cpu.

Every single PC or workstation you could buy for the last 3 years or
so has built-in hardware for doing 64 x 64 => 128 that's exposed by
one or more popular C compilers on that platform.

 

[Keith Thompson]

Every single PC or workstation you could buy for the last 3 years or
so has built-in hardware for doing 64 x 64 => 128 that's exposed by
one or more popular C compilers on that platform.

Really? I don't question the existence of the hardware support, but
how is it exposed by C compilers? Can you give a sample code fragment
for one or more existing compilers?

(If you're referring to inline assembly code, never mind.)

 

[Ian Collins]

Every single PC or workstation you could buy for the last 3 years or
so has built-in hardware for doing 64 x 64 => 128 that's exposed by
one or more popular C compilers on that platform.

Which data type is used for the result?

 

[Willem]

Paul Hsieh wrote:
) Why don't you just use sizeof(unsigned long long)*CHAR_BIT bit digits,
) and write a radix converter? I mean you guys are seriously timing
) these things after making strange decisions like that?

Dude, we're not even posting what kind of hardware we're running on, how
can you possibly think we're actually being serious with these comparisons ?




SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Bartc]

Why don't you just use sizeof(unsigned long long)*CHAR_BIT bit digits,
and write a radix converter? I mean you guys are seriously timing
these things after making strange decisions like that?


Every single PC or workstation you could buy for the last 3 years or
so has built-in hardware for doing 64 x 64 => 128 that's exposed by
one or more popular C compilers on that platform.

My machine uses a 32-bit OS. I'm sure it's possible to override the OS and
switch to 64-bit mode, and use a special compiler for coding the fastest
possible bigint multiply and power functions.

But, the OP seemed to be claiming that this calc was taking seconds on Perl
and possibly C, and it was merely necessary to provide some tested
counter-examples. Especially with noone yet coming forward with timings from
a professional library.

It would be interesting to find out what timings /are/ possible; how fast is
/your/ code for 99**99, or in comparison with some of the posted code?

 

[Dik T. Winter]

> I tried to get some C code up to speed and managed around 60uS per
> calculation (three times faster than Willem's). However this used fixed size
> int arrays with decimal representation (4 digits per int) for ease of
> display.
>
> There is scope for improvement though when there is access to things such as
> the 32-bit => 64-bit multiplies of a typical cpu.

There is a trade-off involved. If a program involves a lot of output it
makes sense to use a decimal representation, but in that case the extended
multiplies will not help very much.

 

[Pilcrow]

Pilcrow said:


Well, it's easy to find out - just omit the loop, and re-time.

I did this, and got 0.004 seconds. I was suspicious, so I made the thing
print its result, getting 0.017 seconds, which suggests that the 0.004 for
just the calc was probably right. Trouble is, the print gave me this:

3.69729637649727e+197

which is too high by
2273428120943711945594043312357182588975697400275764474295447224765\
78589349989871767272059021110451673459880570003230505640548378429806\
355985581928939332340698615000220000840799500101

If the answer doesn't have to be right, I can get it in 0 seconds.

Possibly, but how did you arrive at that?

A program in C
------------------------------------------------------------------
#include <stdio.h>
#include <math.h>
int main(void)
{
double c = 99.0;
printf("%.25g\n", pow(c,99));
}
------------------------------------------------------------------
outputs:
3.697296376497268e+197

and a one-line program in perl:
C:\>perl -e "printf qq/%.25g\n/,99**99"
3.697296376497268e+197

(the 'qq/ ... /' is neccessary because of micro$oft's weird quoting
rules)

 

[Pilcrow]

Possibly, but how did you arrive at that?

A program in C
------------------------------------------------------------------
#include <stdio.h>
#include <math.h>
int main(void)
{
double c = 99.0;
printf("%.25g\n", pow(c,99));
}
------------------------------------------------------------------
outputs:
3.697296376497268e+197

and a one-line program in perl:
C:\>perl -e "printf qq/%.25g\n/,99**99"
3.697296376497268e+197

(the 'qq/ ... /' is neccessary because of micro$oft's weird quoting
rules)

And I also did this:
C:\>perl
use bignum;
print 99**99,"\n";
^D
3697296376497267726571879056288054405956687642817\
4110243025997242355257045527752342141065001012823\
2727940978889548326540119429996769494359451621570\
193644014418071060667659301384999779999159200499899

which may be exact

 

[Keith Thompson]

My machine uses a 32-bit OS. I'm sure it's possible to override the OS
and switch to 64-bit mode, and use a special compiler for coding the
fastest possible bigint multiply and power functions.

But, the OP seemed to be claiming that this calc was taking seconds on
Perl and possibly C, and it was merely necessary to provide some
tested counter-examples. Especially with noone yet coming forward with
timings from a professional library.

[...]

The OP's claim that it was taking "seconds" in Perl was absurd.
Here's what the OP wrote:

But how perl interpreter calculates it( $x = 99 ** 99; print 4x
within seconds???/

Apart from the type (4x should be $x), the Perl code just does a
floating-point calculation, using C's pow() function. I'm fairly sure
that no machine powerful enough to support Perl would take more than a
small fraction of a second to do this.

 

[Merrill]

I know it is really tough to calculate 99^99 in C. Its not only
difficult but also time consuming to get the o/p.

But how perl interpreter calculates it( $x = 99 ** 99; print 4x
within seconds???/

which algorithm it uses ???

Wie das gerade um 99 geht kann ick mick wenig vertexarn.

Falls ihr Reiner Einer seid, so seid ihr wehlche mit denen zu tun haette,
und under Umststaenden, um die ich nie habe glauben muss: bsw, auszug aus
Genf.

Ich bitte meine EU Komeraden um Wahlkampfhilfe.

Falls dies auf richtige Ohren bei, zB, Merkel, findet, so rufe ich auf
andere, die mir zu Schulde, bei deiner Mauer, sind.

u tja
--

 

[Merrill]

Wie das gerade um 99 geht kann ick mick wenig vertexarn.

Falls ihr Reiner Einer seid, so seid ihr wehlche mit denen zu tun haette,
und under Umststaenden, um die ich nie habe glauben muss: bzw, auszug aus
Genf.

Ich bitte meine EU Komeraden um Wahlkampfshilfe.

Falls dies auf richtige Ohren bei, zB, Merkel, findet, so rufe ich auf
andere, die mir zu Schulde, bei deiner Mauer, sind.

u tja
--

tja