Time Complexity of Exponentiation Operation as per RAM Model of Computation

Question

Now, $\color{blue}{\text{Exponentiation}}$ is defined as

Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and pronounced as "$b$ raised to the power of $n$".
$$b^n = \underbrace{b\times b\times\cdot \cdots \times b}_{n\text{ times}}$$

---

Now, my primary question is that What is the Time Complexity of Exponentiation Operation as per RAM Model of Computation?

• As per this, RAM Model assumes a computer can do Exponentiation in a single unit-cost instruction. $(\mathcal{O}(1))$
• Intuitively, it appears to be of $\mathcal{O}(n)$
• Now, What is the time complexity of in-built pow functions in many programming languages? One comment claims it be of $\mathcal{O}(\log n)$. And does ** operator in Python has the same complexity as that of pow?

---

Adding to this, the $n^{th}$ Fibonacci Number can be computed in atleast four ways

• Using $F(n)=F(n-1)+F(n-2)$, Time Complexity of this is essentially $\mathcal{O}(2^n)$ [using Master's Theorem]
• Using Memoization, Time Complexity of this is essentially $\mathcal{O}(n)$
• Using Matrix Exponentiation, this they claim is $\mathcal{O}(\log n)$
• Solving Recurrence to get a Formula [often called as Binet's Formula]. $$F_n=\frac{1}{\sqrt{5}}\bigg[{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}\bigg]$$
  Now, will the Time Complexity using this formula be $\mathcal{O}(1)$?

---

TL;DR: The three inter-related question are formatted using Bold. Since, the question is more of a convention, all relevant links are attached.

Answer 1

I just want to say first that I'm not an expert, but I find this question interesting. I will focus on integer exponentiation.

Like the OP says, intuitively, exponentiation of integers should cost $O(n)$, since each multiplication should add a constant number of bits to the result. For example, $8 \cdot 8$ in binary is $1000 \cdot 1000 = 1000000$ and any further multiplication by $8$ adds another 3 bits to the result.

If we use a unit-cost RAM model, we essentially assume that we can access any number in constant time, or $O(1)$. Many scientists believe this model is unreasonable, because in this model it's easy to create giant numbers, and solve problems like multiplication in linear time or $O(n)$. If you're curious about this, see Martin Fürer's paper "How Fast Can We Multiply Large Integers on an Actual Computer?". In this paper, however, Dr. Fürer talks about other possible models, such as the log-cost RAM. This model basically assumes it takes $O(\log{n})$ time to do an operation on an integer of size $n$. This model seems to predict real life much better than the unit-cost RAM. But remember, these are times for multiplication, not exponentiation.

---

So to make life easier, we can say multiplying a number $x$ takes time $M(x)$, where we replace the function $M(x)$ with either $O(1)$ or $O(\log{x})$, depending on the model.

Now we can focus more on exponentiation. The simplest method that is better than naïve multiplication is modular exponentiation. The idea is to break the exponent into powers of 2. The reason we do this is because it's easy to find $x^{2y}$ after we have found $x^y$. Just square $x^y$ and you get $x^{2y}$. This allows us to go through each power of 2 in the number $y$. This will take time $\Theta(\log{y})$, and if we want to include the time to multiply, we'd write $O(M(x^y)\log{y})$.

---

EDIT 8/7/2022

I made a mistake in the time to multiply. At each step, the time to multiply the $y^\text{th}$ Fibonacci number is $ M \left(x^{2^y} \right)$. The time for all other algebraic activities is less than this, asymptotically. It should be noted that the total time of modular exponentiation is

$$\begin{align} \tag{1} \sum_{y=1}^n{ M(x^{2^y}) } &= M(x) + M(x^{2^1}) + M(x^{2^2}) + \dots + M(x^{2^n}) \\ \tag{2} &= \underbrace{M(x) + M(x^{2^1})}_{\le 2 M(x^{2^1})} + M(x^{2^2}) + \dots + M(x^{2^n}) \\ \tag{3} &\le \underbrace{2 M(x^{2^1}) + M(x^{2^2})}_{\le 2 M(x^{2^2})} + \dots + M(x^{2^n}) \\ \tag{4} &\le 2 M(x^{2^n}) \\ \end{align}$$

So, to summarize, the total time to calculate the $n^\text{th}$ Fibonacci number is proportional to the time it takes to multiply a single number the size of the $n^\text{th}$ Fibonacci number, or $O \left( M(x^{2^n}) \right)$.