99 ^ 99 in C

[asit]

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

[vippstar@gmail.com]

Re: 99 ^ 99 in C

On Sep 27, 3:55 pm, asit <lipu...@gmail. comwrote:

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.

You're mistaken.
99^99 is 0 in C. (^ is XOR, not some expontation operator)

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

Which perl implementation? (Don't answer)
The implementation is allowed to calculate it however it wants.
Even s/99 **
99/369729637649726 772657187905628 805440595668764 281741102430259 972423552570455 277523421410650 010128232727940 978889548326540 119429996769494 359451621570193 644014418071060 667659301384999 779999159200499 899/
;-)

For a serious answer, you might want to look into bignum libraries in
C.
GMP is one of the best and free.
<http://gmplib.org/>

To calculate 99 ** 99, you'd have:
mpz_t x;
mpz_init(x);
mpz_ui_powm_ui( x, 99, 99); /* x = 99 ** 99 */
/* ... */
mpz_clear(x);


However, it's important to note you shouldn't ask further questions
about gmp lib, since it's off-topic here.

[Bartc]

Re: 99 ^ 99 in C

<vippstar@gmail .comwrote in message
news:fc905e1b-19c4-4de6-ac27-9b99d26ceb98@m7 3g2000hsh.googl egroups.com...

On Sep 27, 3:55 pm, asit <lipu...@gmail. comwrote:

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

>
You're mistaken.
99^99 is 0 in C. (^ is XOR, not some expontation operator)

This always comes up. In English, ^ if often used to mean 'raised to the
power of'. The rest of the context makes this clear. In fact only in C code
is ^ used for exclusive-or.

>

>But how perl interpreter calculates it( $x = 99 ** 99; print 4x;)
>within seconds???/
>which algorithm it uses ???

>
Which perl implementation? (Don't answer)
The implementation is allowed to calculate it however it wants.
Even s/99 **
99/369729637649726 772657187905628 805440595668764 281741102430259 972423552570455 277523421410650 010128232727940 978889548326540 119429996769494 359451621570193 644014418071060 667659301384999 779999159200499 899/
;-)

How accurate an answer is needed? In C I can do pow(99.0,99) with no trouble
and I can do it ten million times in half a second. About 3.7e197 (or
3.7x10^197).

--
Bartc

[Flash Gordon]

Re: 99 ^ 99 in C

asit wrote, On 27/09/08 13:55:

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.

How time consuming it is depends on how you do it. As evidence you have
what you wrote below...

But how perl interpreter calculates it( $x = 99 ** 99; print 4x;)
within seconds???/
>
which algorithm it uses ???

Look at the source code for Perl. Possibly try asking on an appropriate
perl group or mailing list.
--
Flash Gordon
If spamming me sent it to smap@spam.cause way.com
If emailing me use my reply-to address
See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/

[vippstar@gmail.com]

Re: 99 ^ 99 in C

On Sep 27, 5:00 pm, "Bartc" <b...@freeuk.co mwrote:

<vipps...@gmail .comwrote in message
>
news:fc905e1b-19c4-4de6-ac27-9b99d26ceb98@m7 3g2000hsh.googl egroups.com...
>

On Sep 27, 3:55 pm, asit <lipu...@gmail. comwrote:

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.

>

You're mistaken.
99^99 is 0 in C. (^ is XOR, not some expontation operator)

>
This always comes up. In English, ^ if often used to mean 'raised to the
power of'. The rest of the context makes this clear. In fact only in C code
is ^ used for exclusive-or.

You obviously missed the part of my post after that saying
"For a serious answer, [...]"

[Bartc]

Re: 99 ^ 99 in C


"asit" <lipun4u@gmail. comwrote in message
news:2fc78646-9258-45d1-9fe2-dbfbd89df3b3@p3 1g2000prf.googl egroups.com...

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

Within /seconds/? You mean microseconds?

Assuming you want an exact answer:

I calculated 99**99 on a big int library of mine that works with individual
decimal digits and runs under an interpreted language. You can't get much
slower. But it only took 1 millisecond.

>
which algorithm it uses ???

The algorithm, if you can call it that, consists of multiplying by 99, 98
times. There are better ways of doing it.

If you don't want to use an existing library, a function in C, working with
fixed precision numbers (some sort of array of ints), to multiply like this
wouldn't be that difficult to program (but neither trivial enough to present
here..).

The problem is displaying the answer, which will likely involve division,
rather more difficult.

--
Bartc

[Richard Heathfield]

Re: 99 ^ 99 in C

asit said:

I know it is really tough to calculate 99^99 in C.

Nope. Assuming you mean "to the power of", it's
13C8DB009372548 E1D1EE21004B41F 9D0A2F1C7A4\
CA716024FF71403 2153A5AB531817C 13EF1F2F7F4\
01B48535A8C22BB DC1EE93B772F0DD 094A8FD9727\
DAE16CEB8E4A254 51BBA34A3209961 5746B57BC8BB

and it took my C program about a hundredth of a second to find this out.

Its not only
difficult but also time consuming to get the o/p.

I suppose it depends on how often you want to do it. A hundredth of a
second here, a fiftieth there, pretty soon you're talking serious time.

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

SECONDS? Sheesh, no wonder nobody uses Perl any more.

which algorithm it uses ???

A slow one, it seems.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Keith Thompson]

Re: 99 ^ 99 in C

asit <lipun4u@gmail. comwrites:

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

<OT>
According to Perl's documentation ("perldoc perlop"), its "**"
operator simply uses the C pow() function. And no, it doesn't take
"seconds" to execute.
</OT>

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Ben Pfaff]

Re: 99 ^ 99 in C

"Bartc" <bc@freeuk.comw rites:

<vippstar@gmail .comwrote in message
news:fc905e1b-19c4-4de6-ac27-9b99d26ceb98@m7 3g2000hsh.googl egroups.com...

>On Sep 27, 3:55 pm, asit <lipu...@gmail. comwrote:

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

>>
>You're mistaken.
>99^99 is 0 in C. (^ is XOR, not some expontation operator)

>
This always comes up. In English, ^ if often used to mean 'raised to
the power of'. The rest of the context makes this clear. In fact only
in C code is ^ used for exclusive-or.

I noticed yesterday that even otherwise respected book authors
get this wrong. Steve McConnell's _Code Complete_ contains the
following code on page 194 labeled as a "C Example":

/* Compute roots of a quadratic equation.
This assumes that (b^2-4*a*c) is positive. */

Temp = sqrt( b^2 - 4*a*c );
root[0] = ( -b + Temp ) / ( 2 * a );
root[1] = ( -b - Temp ) / ( 2 * a );

It will, of course, compute nothing of the sort and in fact b^2
is a constraint violation if 'b' is declared as a floating-point
type.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Antoninus Twink]

Re: 99 ^ 99 in C

On 27 Sep 2008 at 13:13, vippstar@gmail. com wrote:

To calculate 99 ** 99, you'd have:
mpz_t x;
mpz_init(x);
mpz_ui_powm_ui( x, 99, 99); /* x = 99 ** 99 */

Wrong. You need mpz_ui_pow_ui() .

(The *powm* functions do exponentiation modulo some integer.)

[Antoninus Twink]

Re: 99 ^ 99 in C

On 27 Sep 2008 at 17:35, Richard Heathfield wrote:

asit said:

>I know it is really tough to calculate 99^99 in C.

>
Nope. Assuming you mean "to the power of", it's
13C8DB009372548 E1D1EE21004B41F 9D0A2F1C7A4\
CA716024FF71403 2153A5AB531817C 13EF1F2F7F4\
01B48535A8C22BB DC1EE93B772F0DD 094A8FD9727\
DAE16CEB8E4A254 51BBA34A3209961 5746B57BC8BB
>
and it took my C program about a hundredth of a second to find this
out.

That seems incredibly slow unless you're running it on a PDP-11.

Is that using your hacked together "do everything with integers
represented as strings" library that you seem to be very proud of? Why
not use an off-the-shelf professional-grade multiprecision library, of
the sort you're obviously incapable of writing yourself?

[Malcolm McLean]

Re: 99 ^ 99 in C

"Antoninus Twink" <nospam@nospam. invalidwrote in message

On 27 Sep 2008 at 17:35, Richard Heathfield wrote:

>asit said:

>>I know it is really tough to calculate 99^99 in C.

>>
>Nope. Assuming you mean "to the power of", it's
>13C8DB00937254 8E1D1EE21004B41 F9D0A2F1C7A4\
>CA716024FF7140 32153A5AB531817 C13EF1F2F7F4\
>01B48535A8C22B BDC1EE93B772F0D D094A8FD9727\
>DAE16CEB8E4A25 451BBA34A320996 15746B57BC8BB
>>
>and it took my C program about a hundredth of a second to find this
>out.

>
That seems incredibly slow unless you're running it on a PDP-11.
>
Is that using your hacked together "do everything with integers
represented as strings" library that you seem to be very proud of? Why
not use an off-the-shelf professional-grade multiprecision library, of
the sort you're obviously incapable of writing yourself?
>

It's nice to use homemade things.
Having the ouput in hex is a cheat, though.

--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[Richard Heathfield]

Re: 99 ^ 99 in C

Malcolm McLean said:

"Antoninus Twink" <nospam@nospam. invalidwrote in message

>On 27 Sep 2008 at 17:35, Richard Heathfield wrote:

>>asit said:
>>>I know it is really tough to calculate 99^99 in C.
>>>
>>Nope. Assuming you mean "to the power of", it's
>>13C8DB0093725 48E1D1EE21004B4 1F9D0A2F1C7A4\
>>CA716024FF714 032153A5AB53181 7C13EF1F2F7F4\
>>01B48535A8C22 BBDC1EE93B772F0 DD094A8FD9727\
>>DAE16CEB8E4A2 5451BBA34A32099 615746B57BC8BB
>>>
>>and it took my C program about a hundredth of a second to find this
>>out.

>>
>That seems incredibly slow unless you're running it on a PDP-11.
>>
>Is that using your hacked together "do everything with integers
>represented as strings" library that you seem to be very proud of? Why
>not use an off-the-shelf professional-grade multiprecision library, of
>the sort you're obviously incapable of writing yourself?
>>

It's nice to use homemade things.

Yes, it is. Given that high performance was not a design goal, I don't
think it does too shabbily.

Having the ouput in hex is a cheat, though.

<shrugNumbers are numbers. Conversion to decimal is available, but takes
a little longer.

Well, I thought it would. It seems I was mistaken. Adding the conversion
appears to have stripped a couple of ms off the runtime!

369729637649726 772657187905628 805440595668764 281\
741102430259972 423552570455277 523421410650010 128\
232727940978889 548326540119429 996769494359451 621\
570193644014418 071060667659301 384999779999159 200\
499899

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

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Bartc]

Re: 99 ^ 99 in C


"Richard Heathfield" <rjh@see.sig.in validwrote in message
news:8aydnRAaHs iBmH3VnZ2dnUVZ8 v6dnZ2d@bt.com. ..

Malcolm McLean said:
>

>"Antoninus Twink" <nospam@nospam. invalidwrote in message

>>On 27 Sep 2008 at 17:35, Richard Heathfield wrote:
>>>asit said:
>>>>I know it is really tough to calculate 99^99 in C.
>>>>
>>>Nope. Assuming you mean "to the power of", it's
>>>13C8DB009372 548E1D1EE21004B 41F9D0A2F1C7A4\
>>>CA716024FF71 4032153A5AB5318 17C13EF1F2F7F4\
>>>01B48535A8C2 2BBDC1EE93B772F 0DD094A8FD9727\
>>>DAE16CEB8E4A 25451BBA34A3209 9615746B57BC8BB
>>>>
>>>and it took my C program about a hundredth of a second to find this
>>>out.
>>>
>>That seems incredibly slow unless you're running it on a PDP-11.
>>>
>>Is that using your hacked together "do everything with integers
>>represented as strings" library that you seem to be very proud of? Why
>>not use an off-the-shelf professional-grade multiprecision library, of
>>the sort you're obviously incapable of writing yourself?
>>>

>It's nice to use homemade things.

>
Yes, it is. Given that high performance was not a design goal, I don't
think it does too shabbily.
>

>Having the ouput in hex is a cheat, though.

>
<shrugNumbers are numbers. Conversion to decimal is available, but takes
a little longer.
>
Well, I thought it would. It seems I was mistaken. Adding the conversion
appears to have stripped a couple of ms off the runtime!
>
369729637649726 772657187905628 805440595668764 281\
741102430259972 423552570455277 523421410650010 128\
232727940978889 548326540119429 996769494359451 621\
570193644014418 071060667659301 384999779999159 200\
499899
>
real 0m0.008s
user 0m0.000s
sys 0m0.000s

I suspect this may be faster than you think. How long does it take to
calculate 99**99 one thousand times, not including printing the result?

--
Bartc

[Peter Nilsson]

Re: 99 ^ 99 in C

asit <lipu...@gmail. comwrote:

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

Not really. Even my old 1980's 1MHz Hitachi Peach managed to
do this sort of stuff in a few seconds with interpreted Basic.

% type 99.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char digit[] = "0123456789ABCD EFGHIJKLMNOPQRS TUVWXYZ";

int main(int argc, char **argv)
{
static char ans[1024] = "1";
int i, acc, carry;
long b = 0;
char *p;

if (argc 1) b = strtol(argv[1], 0, 10);
if (b < 2 || b 36) b = 10;

for (i = 0; i < 99; i++)
{
carry = 0;
for (p = ans; *p; p++)
{
acc = carry + 99 * (strchr(digit, *p) - digit);
*p = digit[acc % b];
carry = acc / b;
}

while (carry)
{
*p++ = digit[carry % b];
carry /= b;
}

*p = 0;
}

for (i = 0, p = ans + strlen(ans); ans < p; )
{
putchar(*--p);
if (++i % 40 == 0) putchar('\n');
}
if (i % 40) putchar('\n');

return 0;
}

% acc 99.c

% a
369729637649726 772657187905628 8054405956
687642817411024 302599724235525 7045527752
342141065001012 823272794097888 9548326540
119429996769494 359451621570193 6440144180
710606676593013 849997799991592 00499899

% a 16
13C8DB009372548 E1D1EE21004B41F 9D0A2F1C7A
4CA716024FF7140 32153A5AB531817 C13EF1F2F7
F401B48535A8C22 BBDC1EE93B772F0 DD094A8FD9
727DAE16CEB8E4A 25451BBA34A3209 9615746B57
BC8BB

% a 11
561145756320529 45390991A974112 9022605573
037316854238988 7382353926641A4 7423956A45
637795945250000 000000000000000 0000000000
000000000000000 000000000000000 0000000000
000000000000000 000000000000000

--
Peter