1
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ One question at a time, please. Also, help us to help you by telling what you've tried before or what seems to be puzzling. We're not a do-my-homework-for-me site. $\endgroup$ May 12, 2022 at 23:32
  • $\begingroup$ You've probably heard of modular exponentiation, which calculates values in approximately $O(\log{n})$. There are also multiple-base number systems (see Dual Base Number Systems or DBNS or related) which try to construct an exponent, say $c^n$ by exponents larger than 2, for example $c^{5^0} \cdot c^{5^2} \cdot c^{5^3}$. I'm not an expert on this, but this may be a good place to start. These multiple base number systems are primarily used when $n$ is a fixed constant known ahead of time, and $c$ is more like a variable number that changes for each function call. $\endgroup$
    – Matt Groff
    May 13, 2022 at 2:22
  • $\begingroup$ As far as I know, modular exponentiation is generally the fastest method if $n$ is unknown, but the others can work well if $n$ is known. Of course, the other methods can get NP-hard, and I think are still an area of active research. There are also plenty of specialized methods, such as the cases when $c$ and $n$ are both integers. The Chinese remainder theorem is useful for this, for example. $\endgroup$
    – Matt Groff
    May 13, 2022 at 2:25
  • 2
    $\begingroup$ You cannot exponentiate in time $O(1)$ in the RAM model, for the simple reason that the output doesn't fit a single machine word. $\endgroup$ May 13, 2022 at 12:10
  • 1
    $\begingroup$ In any reasonable definition of the RAM machine, in $O(1)$ time you can only modify $O(1)$ machine words. The result of exponentiating two machine words fits in exponentially many machine words, so no reasonable definition of the RAM machine would allow it. I suggest ignoring your link. $\endgroup$ May 13, 2022 at 14:48

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Just as an aside, I may have more information regarding Dual-Base Number Systems (DBNS), but it may take awhile to collect my information. $\endgroup$
    – Matt Groff
    May 14, 2022 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.