AquaRegia

AquaRegia t1_j23vf57 wrote

2838393^(72829) is 72,828 multiplications resulting in a number with 469,965 digits. A 64-bit processor can't directly work with numbers larger than 20 digits, which means it'll have to perform multiple operations for a single multiplication.

All in all, it's not enough that modern computers are really fast, if it just tried to brute-force the calculation it'd still take a lot of time.

1

AquaRegia t1_j23slck wrote

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.

6