(C) 2009 - 2014 by Mourad Louha · All rights reserved

Calculation of very large numbers in Excel – Part 4 – Exponentiation

This fourth part of my article series about the calculation of very large numbers in Excel talks about the exponentiation of two large numbers. If we consider the original problem (see my first article) which was the calculation of 80 ^200 in Excel, we will need at least from 80 ^ 160 an own algorithm.

The calculation of 80 ^200 is equivalent to a total of 200 – 1 = 199 times multiplying the number 80 by itself. We already have a function for multiplying large numbers; see my third article. However the large number of multiplications could lead to a performance problem; so we will check if it is possible to reduce this number.

Binary exponentiation

Exponentiation by squaring (or binary exponentiation) is, according to the Wikipedia, a general method for fast computation of large integer powers of a number. This algorithm has already been discovered around 200 BC in India and can be seen as a standard method for reducing the number of multiplication needed for the calculation of the power of an integer value.

VBA Large Numbers

The principle of the algorithm is quite simple: firstly, the exponent is transformed to its binary representation. Then, all ones are replaced by “QM” and all zeros are replaced by “Q”, where “Q” stands for squaring and “M” for multiplying the intermediate result by the original number. The sequence of Q’s and M’s then yields an arithmetic rule. And, the first “QM” can be omitted.

Let’s have a closer look to the figure above, which shows the method for the calculation of 3 ^ 200. The binary representation of the exponent equals to “11001000”. We score out the first 1 and after replacing the 1 and 0 by QM and Q, we get the sequence “QMQQQMQQQ”.

This means that we have to square the number 3 in a first step; the result is 3 * 3 = 9. The next step is “M”, so we have to multiply the previous result 3 and we get: 9 * 3 = 27. A “Q” follows in the next step, so we get: 27 * 27 = 729. And the next “Q” leads to 729 * 729 = 531441. If we continue to follow the sequence, we will get the result shown in the figure above.

Addition Chains for reducing the number of multiplications

While I was searching the net for algorithms to reduce the number of multiplications, I discovered an English article on the Wikipedia talking about “Addition Chains”. If you explicitly search for the term “Addition Chains”, you will quickly find the Bachelor Project from Sander van der Kruijssen, who presents methods for computing Addition Chains.

But what are “Addition Chains”? Well, in mathematics, an addition chain usually starts with one and each subsequent member corresponds to the sum of two previous members. For example we can represent {1, 2, 3, 6} as {1, 2 = 1 + 1, 3 = 2 + 1 and 6 = 3 + 3}.

Each exponent of an exponentiation can be represented by an addition chain; so if we could retrieve the shortest addition chain (the smallest count of members), we would have found the smallest number of multiplications needed. If we take the sample above for calculating N ^ 6, then the calculation will be X = N ^ 2, Y = N * X and Z = Y ^ 2; Z is the final result.

For a specified number, it is possible to retrieve different addition chains, as you can see in the figure below.

VBA Large Numbers

Both chains are decomposing the number 200 in a addition chain. However the sample on the left contains one more member in the chain. Both chains can be used for the calculation of X ^ 200; the second chain will reduce the multiplication by one in relation to the first chain. And, the second chain corresponds to the chain shown in the first figure of this article and therefore to the chain retrieved by the binary exponentiation.

However, this does not mean that the binary exponentiation always permits to retrieve the shortest addition chains. The binary exponentiation only retrieves a sufficient short chain. Sander van der Kruijssen describes more algorithms for getting shorter chains, like the “Factor Method”, the “Window Method” or the “Power Tree Method”. You can find a link to his work at the end of this article; in my opinion a really interesting project.

However, until now, there is no way to get the shortest chain of a given number using simple algorithms; that’s for example why some databases can be found on the net with pre-calculated shortest chains.

Exponentiation of large numbers in Excel

After the small excursion into the mathematics, I asked myself which algorithm I may use to implement a VBA function for calculation the power of an integer represented by a string. Maintaining a list of possible addition chains seemed a little bit complicated and not every exponent will be covered. As the binary exponentiation is relatively simple to implement and quite sufficient regarding the calculation speed; I opted for this algorithm. Firstly we need a help function for converting the exponent to its binary representation. This is done in the function “mlfhConvertToBinary(…)” shown below. VBA includes a function for converting a number in its hexadecimal representation and convert these digits in a binary form is not very difficult.

The function „mlfhPower(…)“ implements the exponentiation. In a first step, we check, if the exponentiation can be done by using the classic calculation. If this is not possible or leads to an error, then the exponent is converted to its binary representation.

Then the digits are replaced by Q’s and M’s, as described in the upper part of this article. The loop then executes the arithmetic rule and uses for the multiplications the function which I created in my third article of this series. That’s all. Please note, that we do not need any recursion for calculation the exponentiation.

Finally, now we have created VBA function for the addition, subtraction, multiplication and exponentiation of large numbers in Excel. At this moment, I am not sure, if I may publish the first version of my Add-In in the next article or continue with the division of large numbers; let’s see. In the following some links with more information about the topics mentioned before.