[FIXED] Why is exponentiation not atomic?

Issue

In calculating the efficiency of algorithms, I have read that the exponentiation operation is not considered to be an atomic operation (like multiplication).

Is it because exponentiation is the same as the multiplication operation repeated several times over?

Solution

In principle, you can pick any set of "core" operations on numbers that you consider to take a single time unit to evaluate. However, there are a couple of reasons, though, why we typically don't count exponentiation as one of them.

Perhaps the biggest has to do with how large of an output you produce. Suppose you have two numbers x and y that are each d digits long. Then their sum x + y has (at most) d + 1 digits - barely bigger than what we started with. Their product xy has at most 2d digits - larger than what we started with, but not by a huge amount. On the other hand, the value x^y has roughly yd digits, which can be significantly bigger than what we started with. (A good example of this: think about computing 100¹⁰⁰, which has about 200 digits!) This means that simply writing down the result of the exponentiation would require a decent amount of time to complete.

This isn't to say that you couldn't consider exponentiation to be a constant-time operation. Rather, I've just never seen it done.

(Fun fact: some theory papers don't consider multiplication to be a constant-time operation, since the complexity of a hardware circuit to multiply two b-bit numbers grows quadratically with the size of b. And some theory papers don't consider addition to be constant-time either, especially when working with variable-length numbers! It's all about context. If you're dealing with "smallish" numbers that fit into machine words, then we can easily count addition and multiplication as taking constant time. If you have huge numbers - say, large primes for RSA encryption - then the size of the numbers starts to impact the algorithm's runtime and implementation.)

Answered By - templatetypedef

Answer Checked By - Timothy Miller (PHPFixing Admin)