AquaRegia t1_j23slck wrote on December 29, 2022 at 1:24 PM

There are often shortcuts that can be used to make the problem easier. For example the fact that:

>(x^(a))^(b) = x^(ab)

Using this knowledge you can break down the exponent in your example, by finding its factors:

>67 * 1087 = 72829

1087 is still a bit large, so we can use another trick:

>x^(a) * x^(b) = x^(a+b)

And for example break it down to:

>500 + 587 = 1087

Using all this we can then perform the calculation:

>(2838393^(500) * 2838393^(587))^(67)

Which is a lot less daunting. It could probably use other rules to break it down further, but this is the general concept.

mfb- t1_j23u03n wrote on December 29, 2022 at 1:37 PM

There is a much nicer way to break down exponents:

Calculate 2838393^2
Calculate (2838393^(2))^2 = 2838393^4 by squaring the previous result
Calculate ((2838393^(2))^(2))^2 = 2838393^8 by squaring the previous result
... this produces all powers of 2 we need (2, 4, 8, 16, 32, ... 1024)

x^1087 = x^1024 * x^32 * x^16 * x^8 * x^4 * x^2 * x and all these factors were calculated previously (here for x=2838393).

You only need to square numbers, and at the end multiply a few numbers with each other. The computer stores numbers in binary anyway (so 1087 is 1024+32+16+8+4+2+1 for a computer), no extra steps needed to find the right factors.

(actually, for OP's original problem, a computer would directly use 72829 = 65536 + 4096 + ...)

Schnutzel t1_j23vg43 wrote on December 29, 2022 at 1:50 PM

Also, by using floating point numbers, you can make the calculations a lot faster by sacrificing precision. Instead of storing 2838393^1024 (which is a huge number) you only store the most significant digits and how many digits it has.

mfb- t1_j241eji wrote on December 29, 2022 at 2:38 PM

It depends on the application. 2838393^1024 has 6600 digits, which is no problem for modern computers to calculate exactly in well under a second.

Schnutzel t1_j24265s wrote on December 29, 2022 at 2:43 PM

True, but when the exponent is 76000 and you start multiplying numbers with tens of thousands of digits, it starts to rack up.