Exponentiation with minimum number of multiplication
Exponentiation is known as a power of a number. It is calculated by multiplying the number (a) by itself the power (n) times. If the result of whole calculation fits in computer’s memory, one multiplication can be done in constant time by computer and the final complexity can be taken as linear which means the complexity is only proportional to the power value, n.
The exponent product rule states that the multiplication of two powers with same base equals to power of sum of the exponent values of base. Actually, this is already shown above that multiplying 1st power of the number a, n times results 1+1+1+1+….+1=n th power of a.
As known from the commonly used decimal number system, a base-10 number is basically sum of power of 10s. Generalizing this definition results that a base-x number is sum of some power of x. In computers, base-2 is used and each digit of a base-2 number is called as bits. A 64-bit computer can store a number up to 64 digit in base-2. The power value n can be represented as follows in base-2.
The k coefficient numbers are either 0 or 1 because they are the only elements in base-2 number system. Those numbers actually form the digits of the number from right to left. Replacing n with this representation results the following.
The last representation has two element to be considered. The first one is the k values which are the digits of the number n in base-2 number system. Actually, the k values are easy to calculate on computer since all integers are stored in computer memory as base-2 representation. The other element is power of a for variable i. In the beginning only a is known which is the 1st power of a. Using the same property of exponentiation gives the following.
The above recursion tells that each element can be calculated by taking the square of the previous value. There are logn different values which means whole calculation basically needs only logn squaring operations which are basically multiplication operations. The main element is the kth power of the square values which are very obvious to calculate since the value k is either 0 or 1. All these elements need to be multiplied to get the power value. Thus, the total number of operation needed for the calculation is 2*logn.
For example, 100th power of 2 can be calculated with 2*log(100)=12 multiplications as follows.
It is good to recall that, the number of multiplications can only be taken as the complexity of this algorithm if the expected result is 64 bits. This case limits the number space to 64-bit space and 64-bit computers can calculate any multiplication in constant time. Thus, the complexity of the algorithm will be O(logn). However, a multiplication of two big numbers is more complicated if the numbers become more than 64th power of 2. That’s why the complexity of exponentiation cannot be taken as the number of multiplication.
The example code above calculates 1000th power of 2. According to the conclusion of this article the operation should perform 2*log(1000)=18 multiplications which can be seen in the image. This value is actually the upper bound of the number of multiplications. The result value in the code is being multiplied by 1 for digits with value 0. Performing a multiplication by 1 is not necessary and they can be ignored. Thus, the number of necessary multiplications is equal to the number of 1 digits in the base-2 representaion of a which can be shown as |a|. So the exact number of multiplications is logn+|a|.
I hope you like the article, and thanks for reading.
